شرکت «برادران علی‌کوچولو» یک شرکت بزرگ تولید جغجغه‌های رنگی است که ساختمان ان تعداد زیادی اتاق و تعداد زیادی لامپ دارد. این شرکت برای سیم‌کشی لامپ‌های ساختمانش «آوریل دالتون» را استخدام کرده بود. بعد از سیم‌کشی معلوم شد که آوریل نه تنها از تعداد مساوی کلید و لامپ استفاده نکرده٬ بلکه هر کلید را به چند لامپ و هر لامپ را به چند کلید وصل کرده است. به این ترتیب٬ با زدن یک کلید٬ هر یک از لامپ‌های متصل به آن کلید تغییر وضعیت می‌دهد (یعنی از روشن به خاموش یا برعکس تغییر می‌کند.) به این دلیل٬ در پایان هر روز که کارمندان می‌خواهند با زدن کلیدها همه‌ی لامپ‌ها را خاموش کنند با مشکل مواجه می‌شوند. (این تنها راه خاموش کردن لامپ‌هاست. قطع فیوز٬ یا شُل کردن لامپ‌ها یا کارهای مشابه دیگر مجاز نیست!) می‌دانیم که در آغاز هر روز همه‌ی لامپ‌ها خاموش‌اند. پس در پایان روز همیشه می‌توان بعضی از کلید‌ها را زد که همه‌ی لامپ‌ها دوباره خاموش شوند. شرکت برای حل مشکل خاموش کردن لامپ‌ها «لوک خوش‌شانس» را استخدام کرده است تا در پایان هر روز همه‌ی لامپ‌ها را خاموش کند. «لوک» پس از عقد قرارداد و بررسی مشکل٬ کلیدها را از ۱ تا $N$( $N$ تعداد کلیدها) شماره‌گذاری کرد و جدولی با $N$ خانه تهیه کرد تا در خانه‌ی $i$ام بنویسد که کلید $i$ام زده می‌شود یا خیر. او در انتهای هر روز٬ جدول را بر اساس وضعیت فعلی لامپ‌ها پر می‌کرد و بعضی از کلیدها را مطابق آن می‌زد. با این کار همه‌ی لامپ‌ها خاموش می‌شدند.

الف) ثابت کنید که تعداد جدول‌های مختلفی که لوک برای خاموش کردن همه‌ی لامپ‌ها در انتهای هر روز می‌تواند تهیه کند ثابت است و این تعداد بستگی به وضعیت لامپ‌ها در انتهای روز ندارد و فقط به نحوه‌ی سیم‌کشی آوریل وابسته است.

ب) ثابت کنید که این تعداد توانی از ۲ است.

• سوال بعد
• سوال قبل