Loading [MathJax]/jax/output/HTML-CSS/jax.js

چراغ‌ها

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

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