روی یک خط، $n$ چراغ با شماره‌های ۱ تا $n$ قرار دارند که تعدادی از آن‌ها خاموش و بقیه روشن هستند. دو نفر به نام‌های $A $و $B$ این بازی را با هم انجام می‌دهند. از ابتدا و در تمام مراحل بازی، چشم $B$ بسته است و او وضعیت لامپ‌ها را نمی‌داند. در هر مرحله از بازی، $B$ مجموعه‌ای از اعداد ۱ تا $n$ را انتخاب می‌کند و به $A$ می‌گوید. $A$ لامپ‌هایی که شماره‌ی آن‌ها در آن مجموعه است را تغییر وضعیت می‌دهد؛ یعنی اگر لامپ خاموش بود، آن را روشن و اگر روشن بود آن را خاموش می‌کند. مثلاً اگر ۳ لامپ داشته باشیم و لامپ‌های ۱ و ۳ خاموش باشند و لامپ ۲ روشن باشد و $B$ مجموعه‌ی {۱,۲} را انتخاب کند، در مرحله‌ی بعد لامپ ۱ روشن و لامپ‌های ۲ و ۳ خاموش خواهند شد.

در هر مرحله‌ای که تمام لامپ‌ها خاموش شوند بازی به نفع $B$ تمام می‌شود. مثلاً اگر $n=2$ و $B$ به ترتیب مجموعه‌های {۱,۲},{۱},{۱,۲} را انتخاب کند، به هر ترتیب $B$ برنده‌ی بازی خواهد شد. ثابت کنید برای هر $n$، $B$ می‌تواند طوری بازی کند که ببرد. یعنی می‌تواند دنباله‌ای از زیرمجموعه‌های {$1,2,…,n$} را انتخاب کند که برای هر وضعیت اولیه‌ی دل خواه از چراغ‌ها در حین انجام عمل به جایی برسیم که همه‌ی چراغ‌ها خاموش باشند.

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