300000
English | Français | فارسی | 中文 | Українська | Azerbaijani | ខ្មែរ | Tiếng Việt | Bahasa Melayu | Deutsch | O'zbek | РусскийLights©
Якщо вас цікавить лише розв’язування задач конкурсу Lights, перейдіть до підказок, щоб грати в гру нижче. підказок, щоб грати в гру нижче.
Перш ніж почати, давайте введемо деякі математичні терміни.
Математична мова
Ми використовуємо цю можливість, щоб практикувати математичний формалізм і класифікувати твердження
- Гіпотеза (пропоноване твердження як відправна точка для подальшого дослідження)
- Визначення (пояснення значення слова або фрази)
- Теорема (важливе твердження)
- Лема (незначне твердження)
- Доведення (твердження, які безсумнівно показують, що теорема або лема правильна. Символ □ вказує на кінець доведення.)
- Наслідок (твердження, яке випливає безпосередньо з теореми або леми)
Хороший спосіб дослідити тему — задати собі прості запитання та спробувати на них відповісти. Ми зараз це зробимо. Ви можете розглядати цю сторінку як посібник для проведення досліджень, особливо розділ, що досліджує симетрії. По дорозі ми знайдемо підказки, як грати в гру.
Чи має значення, в якому порядку здійснюються кліки?
Ні. Статус вогника залежить лише від кількості клацань, зроблених на самому вогнику та на сусідніх вогниках, а не від порядку клацань. Якщо загальна кількість клацань на вогнику та на його сусідах парна, то вогник не змінює свого статусу. Якщо число непарне, статус змінюється незалежно від порядку клацань.
приклад:Виберіть два різних сусідніх вогні, скажімо, A і B. Потім клацніть їх у порядку A, B, B, A. Який результат? ↠ Нічого не змінилося, тому що B, B не тягне змін, і A, A також не тягне змін.
Давайте тепер змінимо порядок перших двох кліків і клацніть їх у порядку B, A, B, A. Який результат? ↠ Знову нічого не змінилося. Порядок перших двох кліків не мав значення. Те ж саме відбувається, якщо ми натискаємо дві кнопки кожну двічі в будь-якому порядку. Порядок клацань значення не має.
Якщо порядок клацань не має значення, то як можна зменшити кількість клацань довгої послідовності?
Один із способів зменшення кількості кліків полягає в наступному.
Під час розв’язування головоломки записувати для кожного вогника кількість кліків, зроблених на цьому вогні. Після цього кожна парна кількість клацань на лампочці встановлюється на нуль, а кожна непарна — на 1. Нова послідовність має той самий ефект і також є рішенням.
Визначення: Послідовність клацань називається скороченою, якщо кожен вогник натискається не більше одного разу. Наведений вище процес називається скороченням.
Що таке верхня межа довжини зменшеної послідовності клацань?
- Послідовність може мати стільки клацань, скільки світильників, тому що в скороченій послідовності кожен вогник клацається не більше одного разу. Отже, якщо дошка має висоту h і ширину w, то є вогні h×w і зменшена послідовність може мати щонайбільше h×w багато кліків.
Якщо порядок ходів не має значення, як можна виконати повний пошук (перебір) рішення, тобто послідовність клацань, яка вмикає всі індикатори?
Оскільки порядок клацань не має значення, для кожного вогника достатньо знати, чи натиснуто його зрештою чи ні. Тому було б достатньо для повного перебору спробувати клацнути всі комбінації всіх вогнів.
Якщо на дошці є h×w індикатори, то існує 2h×w їх комбінації (2 варіанти для кожного індикатора, незалежно від того, чи натиснути його в це поєднання чи ні). Такий пошук грубої сили займе занадто багато часу. Однак, якщо «Довідкові примітки» увімкнено (недоступно в конкурсах), можна просто клацнути всі вогні один за одним і перевірити, чи це клацання наблизило вас до рішення. Якщо так, залиште його, інакше натисніть його ще раз.
Наступні запитання допоможуть ще більше скоротити послідовності кліків.
Якщо всі індикатори увімкнені і кожен вогник натискається рівно один раз, який результат?
-
Лема:
Якщо на прямокутному полі всі індикатори увімкнені і кожен вогник клацається один раз, то отримаємо вимкнені кутові вогники (O), всі інші вогні по краях увімкнені (#), а всі інші вогні вимкнені (O), як показано на цьому полі 4х4:
# # # # O # # O
# # # # # O O #
# # # # # O O #
# # # # O # # O
before after
Доведення:
Почнемо з того, що кожен вогник клацається і, отже, перемикається один раз. Кожен вогник також перемикається, коли натискається його сусід.
Отже, якщо кількість сусідніх світильників парна, то світло буде перемикатися додаткову парну кількість разів, тобто загалом непарну кількість разів. Тому він все одно буде ВИМКНЕНИМ, якщо спочатку був УВІМКНЕНИМ.
Аналогічно, якщо кількість сусідніх вогнів непарна, то світло буде перемикатися додаткову непарну кількість разів, тобто в цілому парну кількість разів. Тому він все одно буде УВІМКНЕНИМ, якщо спочатку був УВІМКНЕНИМ.
Підраховуючи кількість сусідів кожного вогника, можна отримати твердження леми. □
Чи є скорочені послідовності клацань, коли на початку та в кінці послідовності всі індикатори увімкнені? Таку послідовність будемо називати циклом.
- почати з всіма увімкненими вогниками
- знайти дві різні скорочені послідовності, які вимикають одні й ті самі вогники, наприклад, вимикають усі вогники
- об’єднати обидві послідовності в одну послідовність, яка, якщо почати з увімкненими всіма індикаторами, закінчиться з увімкненими всіма індикаторами
- скоротити цю комбіновану послідовність, щоб отримати цикл. Цей скорочений цикл містить клацання, оскільки обидві комбіновані послідовності були різними, тому в одній послідовності має бути принаймні один клік, якого немає в іншій вихідній послідовності. Скорочена комбінована послідовність матиме цей клік.
Якщо клацати кожною лампочкою парну кількість разів, то скорочення (пояснено раніше) дає нульові клацання кожного індикатора, і тоді не дивно, що всі індикатори залишаються увімкненими. Але чи існує скорочена послідовність клацань, яка починається і закінчується, коли всі індикатори увімкнені?
Визначення:Скорочена послідовність, яка включає принаймні один клік, називається циклом, якщо всі індикатори мають однаковий статус до та після цієї послідовності.
Ми будемо шукати цикли, починаючи з всіх увімкнених вогників і закінчуючи з всіма увімкненими вогниками. Такий цикл також залишить без змін будь-який інший початковий стан, тобто якщо ми почнемо з поля з деякими індикаторами, які увімкнені, а деякими вимкненими, і ми виконаємо цей цикл, ці самі індикатори будуть увімкненими і вимкненими. Ви бачите чому?
Однією з можливостей знайти цикл є
Для яких розмірів полів це можливо? Для певного розміру поля можна відповісти на це питання, склавши систему лінійних рівнянь і дослідивши її. Детальніше про це можна прочитати в посиланнях, наведених нижче.
Як ми можемо знайти цикл для дошки 4×4?
-
Давайте почнемо з увімкненими всіма індикаторами (#) і клацніть кожен вогник рівно один раз. Знаємо, отримуємо
O # # O
# O O #
# O O #
O # # O
Оскільки ми шукаємо цикл, тобто починаючи і закінчуючи з увімкненими всіма індикаторами, ми намагаємося клацнути всі індикатори, які вимкнені (показано як O), один раз, що не тільки увімкне їх, але й залишить увімкненими всі інші. Будь ласка, перевірте це самі.
Щоб нагадати собі: спочатку ми клацнули всі вогні, а потім знову натиснули на вогні по обох діагоналях. Тож ми двічі клацнули світлом по діагоналях. Зменшивши всю цю послідовність, усі подвійні клацання на діагональних ліхтарях будуть відкинуті, і залишаться лише клацання # вогнів на дошці вище. Отже, ми почали з всіма увімкненими вогниками, а закінчили з всіма увімкненими вогниками. Тому 8 клацань по # на дошці вище утворюють цикл! УРА, ми знайшли цикл! 🥳
Будь ласка, спробуйте і переконайтеся, що натискання на 8 індикаторів, позначені # вище, не змінює освітлення дошки 4×4. Це найлегше помітити при запуску з увімкненими всіма індикаторами.
Як можна використовувати цикл, щоб ще більше скоротити послідовність клацань?
Якщо цикл відомий, це можна використовувати, щоб ще більше скоротити послідовності клацань.
Лема:Якщо відомий цикл з c кліків і вказано послідовність, з яких n кліків належать до циклу, то заміна цих n кліків на c−n кліків, які не входять у цикл, дає еквівалентну послідовність.
Доведення:Це доведення є конструктивним, тобто показує, як побудувати таку послідовність.
Якщо ми додамо послідовність із циклом, то нова комбінована послідовність буде еквівалентною, оскільки ми додали цикл. У комбінованій послідовності n кліків виконується двічі, один раз у вихідній послідовності і один раз у циклі. При зменшенні, тобто видаленні цих подвійних клацань, нова послідовність все одно буде еквівалентною (оскільки скорочення генерує еквівалентні послідовності) і тепер матимемо замість n кліків c−n кліків, що належать до циклу. □
Наслідок:Якщо c−n < n, то нова послідовність коротша. Це відбувається тоді і тільки тоді, коли n > c/2. Словами: якщо послідовність містить більше половини кліків циклу, то послідовність можна скоротити, додавши цикл і видаливши подвійні кліки.
приклад:Складіть (олівцем на папері) список з 13 вогнів на дошці 4×4, почніть з увімкненими всіма вогнями, натисніть на 13 вогнів і намалюйте результат. (Чому 13, а ні, скажімо, 12? Нижче ми розглянемо далі. :-) ) Тепер перевірте, які з 13 клацань належать до циклу та створіть новий список клацань (олівцем на папері), де ці клацання циклу замінюються на інші клацання в циклі. Почніть знову, увімкнувши всі індикатори, і виконайте цю коротшу послідовність клацань.
Який результат?
Результат цієї зменшеної послідовності повинен бути таким же, як і раніше.
Яка верхня межа довжини скороченої послідовності клацань на дошці 4×4?
-
Теорема:
Послідовність клацань на дошці 4×4 можна скоротити до 12 клацань.
Доведення:Ми дізналися, що скорочена послідовність на дошці 4×4 може мати лише 4×4=16 клацань. Ми знаємо цикл із 8 кліків для дошки 4×4. Тому послідовність може мати не більше 16−8=8 клацань, які не належать до циклу. Ми також з’ясували, що якщо послідовність містить більше половини клацань циклу, її можна скоротити. Отже, зменшена та скорочена послідовність може мати щонайбільше:
8 (клацання, які не належать до циклу)
+ 8/2 (половина кліків з циклу)
= 12 кліків
на дошці 4×4. □
Усі можливі задачі з полем 4×4, щоб увімкнути все освітлення, можна вирішити не більше ніж за 12 кліків.
Пояснення:Теорема не говорить, чи існує послідовність довжиною 12, яку не можна зменшити за допомогою циклів. Можливо, максимальна довжина становить 12, 10 або 8. Теорема говорить лише про те, що вона не може мати більше 12 кліків.
Дотримуючись наведених вище висновків, що може бути прикладом проблеми 4×4, яка вимагає найбільшої кількості клацань, щоб увімкнути всі вогники?
Клацаємо всі вогники не в циклі, тому всі 8 вогників по діагоналях. Потім вибираємо 4 вогники з циклу, наприклад, по одному з кожного боку за годинниковою стрілкою. Ми зробили ці 12 кліків із зазначенням клацання ©:
© · © ©
© © © ·
· © © ©
© © · ©
в результаті маємо дошку
# O O #
O # # O
O # # O
# O O #
Чи є ця послідовність із 12 кліків максимальної довжини, яку не можна скоротити?
Ні. Вже ці 4 кліки
· © · ·
© · · ·
· · · ©
· · © · дають той самий результат:
# O O #
O # # O
O # # O
# O O #
Що це означає?
Це означає, що у нас новий цикл 12+4=16 кліків, УРА! 🥳 Якщо ми відмовимося від подвійних клацань (© + © = ·), цей новий цикл із 12 кліків залишиться:
© · © © · © · · © © © ©
© © © · + © · · · = · © © ·
· © © © · · · © · © © ·
© © · © · · © · © © © ©
Будь ласка, переконайтеся, що це цикл.
Що виходить, коли ми додаємо цикл із 12 клацань і цикл із 8 клацань і починаємо зменшувати?
Сума двох циклів повинна бути циклом, тобто вона не змінює дошку:
© © © © · © © · © · · ©
· © © · + © · · © = © © © ©
· © © · © · · © © © © ©
© © © © · © © · © · · ©
дає повернуту на 90° версію циклу з 12 клацаннями, який є нашим новим 3-м циклом. Будь ласка, переконайтеся, що це також цикл.
Що це означає для максимальної довжини послідовності клацань на дошці 4×4?
Послідовності
© · © © · · © ·
© · · · and © © © ·
· · · © · © © ©
© © · © · © · ·
кожен має 8 кліків.
Чи можна їх скоротити за допомогою 3 циклів?
Кожен з них перекривається з циклом з 8 кліків рівно на 4 кліки і з кожним циклом з 12 клацань точно на 6 кліків. Будь ласка, перевірте ці 6 тверджень. Вони не перекриваються з кожним циклом більш ніж на половину кліків циклу. Таким чином, ці послідовності не можна зменшити за допомогою цих 3 циклів, але додавання до них лише одного клацання дало б можливість їх зменшити.
Ми робимо це недоведене припущення:
Гіпотеза:Максимальна довжина послідовності клацань на дошці 4×4, яку неможливо скоротити циклом, становить 8.
Ви можете це довести. Спочатку потрібно було б показати, що інших незалежних циклів не існує.
Далі ми розглянемо дошки 5×5 і дослідимо більше симетрій.
А як щодо дощок 5×5? Чи можете ви знайти цикл для цієї дошки?
- почніть з усіма увімкненими вогниками
- клацніть кожен вогник один раз і отримайте
O # # # O # O O O # # O O O # # O O O # O # # # O - клацніть усі вогні по діагоналях один раз, а також один раз центральне світло. В результаті всі індикатори горять.
- зменшіть послідовність, відкинувши всі подвійні клацання по діагоналях, залишивши 25−9=16 клацань, показаних як © в:
· © © © · © · © · © © © · © © (1) © · © · © · © © © · - і святкуємо, ми знайшли цикл, УРА! 🥳
Як і з дошкою 4×4
Будь ласка, спробуйте і переконайтеся, що натискання на 16 індикаторів, зазначених © вище, не змінює освітлення дошки 5×5. Це найлегше помітити при запуску з увімкненими всіма індикаторами.
Яка верхня межа для довжини скороченої послідовності клацань на дошці 5×5?
-
Теорема:
Послідовність клацань на дошці 5×5 не може мати більше 17 клацань.
Доведення:Ми дізналися, що скорочена послідовність на дошці 5×5 може мати лише 5×5=25 клацань. Ми знаємо цикл із 16 кліків для дошки 5×5. Тому послідовність може мати не більше 25−16=9 клацань, які не належать до циклу. Ми також з’ясували, що якщо послідовність містить більше половини клацань циклу, її можна зменшити. Отже, зменшена та скорочена послідовність може мати щонайбільше:
9 (клацання, які не належать до циклу)
+ 16/2 (половина клацань циклу)
= 17 кліків
на дошці 5×5. □
Якщо завдання з полем 5×5, щоб увімкнути всі лампи, має рішення, то є рішення з не більше ніж 17 кліками.
Пояснення:Чи означає це, що є послідовності з 17 кліків, які не можна скоротити?
відповідь:Ні. Поки що ми не знаємо.
Яку роль у цій грі відіграє симетрія?
Оскільки дошка має прямокутну форму, візерунок увімкнених/вимкнених вогників може бути симетричним на 90° або 180° або він може мати дзеркальну симетрію вздовж горизонтальної або вертикальної лінії симетрії. Якщо дошка квадратна, вона також може мати дзеркальну симетрію вздовж діагоналі або навіть обох діагоналей.
Далі ідея полягає в тому, що рішення складається з кількох клацань, які мають таку симетрію, та інших клацань, які не мають такої симетрії.
Як ми можемо досягти прогресу?
Нам потрібне натхнення, і ми отримуємо його, граючи в гру та клацаючи випадковим чином вогники, доки не отримаємо дошку, яка виглядає дивно або має гарну симетрію. А потім дивимось, чи послідовність клацань теж особлива.
Ми можемо натрапити на таку дошку:і забути, як ми до неї дійшли. Це легко дізнатися, вибравши «Довідкові примітки: УВІМКНЕНО» та натиснувши кожну позицію. Якщо число, зазначене в розділі «Примітки довідки: ви можете виграти не більше ніж XX кліків», було знижено, ми фіксуємо позицію, а якщо ні, клацаємо її знову. Ми знаходимо таке рішення, де © вказує на клацання:
· · · · ·
© © © © ©
· · © · · (3)
· © · © ·
© · © · ©
Тепер ми маємо бути дуже здивовані та дуже зацікавлені!
Чому?
Оскільки дошка (2) має дзеркальну симетрію із середньою горизонтальною лінією як лінією симетрії, але рішення не має такої симетрії. Рідко в математиці симетрична задача має несиметричний розв’язок.
Що тепер?
Нам слід дослідити це шляхом виділення симетричної та несиметричної частини (3).
Тому запишемо (3) як суму симетричної та несиметричної частин:
· · · · · · · · · · · · · · ·
© © © © © · © · © · © · © · ©
· · © · · = · · © · · + · · · · ·
· © · © · · © · © · · · · · ·
© · © · © · · · · · © · © · ©
Так само, як мисливці за скарбами шукають дорогоцінні камені, ми в математиці також шукаємо унікальні предмети. Наведене вище розкладання не є унікальним. Існує багато способів записати несиметричну частину як суму симетричної та іншої несиметричної частини.
Чи існує унікальний поділ?
Ми можемо зробити його унікальним, вимагаючи, щоб несиметричні клацання були лише з одного боку лінії симетрії.
Ми використовуємо © + © = · і тому пишемо зараз
· · · · · · · · · · · · · · · · · · · ·
© © © © © · © · © · © · © · © · · · · ·
· · © · · = · · © · · + · · · · · + · · · · ·
· © · © · · © · © · © · © · © © · © · ©
© · © · © · · · · · · · · · · © · © · ©
· · · · · · · · · ·
© © © © © · · · · ·
= · · © · · + · · · · ·
© © © © © © · © · ©
· · · · · © · © · ©
Ми сконцентрувалися і хочемо дослідити всі аспекти.
Оскільки початкова дошка була симетричною, а симетрична частина повинна складати симетричну дошку, отже несиметрична послідовність також має бути симетричною дошкою.
Що це?
· · · · · O O O O O
· · · · · O O O O O
· · · · · (4) generates the board # O # O # (5)
© · © · © O O O O O
© · © · © O O O O O
Будь ласка, перевірте це!
Ми побачимо, що існує дуже мало несиметричних рішень, які генерують симетричну дошку і мають усі клацання з одного боку лінії симетрії.
Що робити, якщо хтось огляне дошку (5) і подивиться на неї та на рішення (4) з іншого боку?
Дошка виглядає так само (оскільки вона має симетрію 180°), але рішення стає таким же:
© · © · ©
© · © · ©
· · · · · (6)
· · · · ·
· · · · ·
Отже (6) є іншою несиметричною послідовністю, яка створює таку ж симетричну дошку (5). Це випадковість чи так завжди?
Це загальне твердження:
Якщо симетрична задача (тут (5), що має симетрію 180°), створена несиметричною послідовністю (тут (4)), то виконання операції симетрії (тут поворот на 180°) над цією послідовністю генерує нову несиметричну послідовність (тут (6)), яка створює ту саму дошку (тут (5)).
Що станеться, якщо виконати обидві несиметричні послідовності?
Після першої послідовності (4) три вогника вимикаються (на дошці (5)), а після другої послідовності (6) знову вмикаються. Це означає (4) + (6)
© · © · ©
© · © · ©
· · · · · (7)
© · © · ©
© · © · ©
це цикл з 12 кліків! УРА!! 🥳 Будь ласка, переконайтеся в цьому, виконавши ці 12 кліків.
Для чого можна використовувати цей новий цикл?
Як і інший цикл із 16 натисканнями, його можна використовувати для зменшення послідовності клацань.
Чи можна скоротити цикл із 16 клацань за допомогою циклу з 12 клацань? Результатом має бути цикл, оскільки цикл + цикл = цикл.
Виконання обох циклів дає (через © + © = · )
· © © © · © · © · © © © · © ©
© · © · © © · © · © · · · · ·
© © · © © + · · · · · = © © · © © (8)
© · © · © © · © · © · · · · ·
· © © © · © · © · © © © · © ©
який має бути циклом, і так, це просто цикл (7), повернутий на 90°.
Чи цикл із 16 клацаннями також є сумою двох несиметричних розв’язків симетричної задачі?
У нас є 2 способи записати цикл із 16 кліків у вигляді суми:
· © © © · · · · · · · © © © ·
© · © · © © · · · · · · © · ©
© © · © © = © © · · · + · · · © © (9)
© · © · © © · © · · · · · · ©
· © © © · · © © © · · · · · ·
· © © © · · · · · · · © © © ·
© · © · © © · · · © · · © · ·
© © · © © = © © · © © + · · · · · (10)
© · © · © © · · · © · · © · ·
· © © © · · · · · · · © © © ·
Кожна з двох послідовностей у правій частині (9) є несиметричною послідовністю, що призводить до симетричної дошки
# O O O O
O O O O O
O O O O O (11)
O O O O O
O O O O #
Кожна з двох послідовностей у правій частині (10) є несиметричною послідовністю, що призводить до симетричної дошки
# O O O #
O O O O O
O O O O O (12)
O O O O O
# O O O #
Отже, цикл із 16 кліків — це сума двох несиметричних розв’язків симетричної задачі, навіть двома способами.
Якщо потрібно звести до мінімуму кількість послідовностей для запам’ятовування, цього достатньо запам’ятати
· · · · ·
© · · · ·
© © · · · (13)
© · © · ·
· © © © ·
оскільки інша послідовність праворуч від (9) має той самий ефект, а послідовності праворуч від (10) є лише сумами (13) та поворотів на 90° (13).
How does that help to solve symmetric boards?
If it is true that for 5×5 boards the sequences (4), (13) and their 90° rotations are the only non-symmetric sequences that produce mirror symmetric boards (apart from symmetric clicks that yield other non-symmetric sequences) then to solve a mirror symmetric board one only needs to perform symmetric moves until either all lights are ON, or until one has reached one of boards (5) or (11) (or 90° rotations of them) and then one simply executes sequences (4) or (13) (or 90° rotations of them).
In other words, to solve a mirror symmetric 5x5 board, one only has to try out symmetric combinations of clicks which require fewer such symmetric clicks and thus result in a smaller search tree.
What is the maximal length of a shortened sequence of clicks on a 5×5 board?
We are not answering this question, but we have two suggestions.
Hypothesis:There are no other cycles for a 5×5 board that are not a combination of the 3 cycles with 12, 12 and 16 clicks.
Hypothesis:The maximal length of a shortened sequence of clicks on a 5×5 board is 13.
We leave it to you to think about a proof or a counterexample in form of another independent cycle or of a sequence with more than 13 clicks which cannot be shortened with the 3 cycles (7), (8) and (1) having 12, 12 and 16 clicks. The first hypothesis can be checked using linear algebra (see further below), but a simple proof or a different cycle would be nice to have. An example of a sequence with 13 clicks that cannot be reduced with the 3 cycles is
© · © · ©
· © · © ·
© · © · ©
· © · © ·
© · © · ©
Have fun in (re-)searching and proving!
Can all patterns of ON/OFF lights on the board be reached?
With h×w lights there are 2h×w pattern of ON/OFF lights. As we found out before, there are also 2h×w possible sequences of clicks.
But there are sequences which result in the same board pattern, namely any sequence and this sequence + cycle. Therefore we have more sequences than reachable board pattern, so there must exist board pattern that cannot be reached.
In mathematics there are words for such situations. If each sequence of clicks would result in a different pattern, then the map of sequences to pattern would be called injective. If each pattern would be the result of some sequence of clicks then the map of sequences to pattern would be called surjective. Our map of sequences of clicks to pattern is therefore non-injective and non-surjective.
Hints for playing the game
Preparation practice
To prepare for playing the game in a contest it is helpful to start with a board with all lights being ON. To get this board one lowers the number of 'Initial Clicks' and 'Purple Lights' to 0 and increases the size of the board. Then do 2 clicks either on direct neighbours or diagonal neighbours and remember the resulting pattern so that you recognize them when they come up in a game. Do such tries in a corner, at an edge and in the middle as pattern depend on the location too.
A different kind of practice is to take a 5×5 board with all lights ON and click lights that are symmetric with respect to a diagonal or middle line or that are 90° or 180° rotated versions of each other and see which symmetric pattern you can get.
What should one try first if there is a small group of nearby lights that are OFF?
In this case moves in the center of such small groups should be tried first because clicks on the edge of such groups would only switch OFF more lights further away and enlarge the group of lights that are OFF. If unsuccessful one has to click more lights further away and end up having to make clicks all over the board.
What if the board pattern has a symmetry?
The initial board may be mirror symmetric with respect to one or both diagonals or with respect to the horizontal and/or vertical line of symmetry. Other symmetries may be the 90° or 180° rotational symmetry. In section Which role does symmetry play in this game? we derived the following strategy.
One performs groups of symmetric clicks which preserve the symmetry until either all lights are ON, or when having a board of size 5×5 until one reaches one of these boards:
O O O O O # O O O O # O O O #
O O O O O O O O O O O O O O O
# O # O # (5) or O O O O O (11) or O O O O O (12)
O O O O O O O O O O O O O O O
O O O O O O O O O # # O O O #
(or 90° rotations of them) and then one simply executes sequences:
· · · · · · · · · · · © © © ·
· · · · · © · · · · © · © · ©
· · · · · (4) resp © © · · · (13) resp © © · © © (1)
© · © · © © · © · · © · © · ©
© · © · © · © © © · · © © © ·
(respectively 90° rotations of them).
What does it mean to 'Play symmetric'?
If any light on the symmetry line is OFF then this light itself needs to be clicked. Reason: If one would not click it and only click a neighbouring light then the other neighbouring light symmetric to the symmetry line should also be clicked and then the light on the symmetry line would be switched twice and stay OFF.
For the same reason, if any light on this diagonal is ON then this light must NOT be clicked.
If the position is symmetric with respect to two symmetry lines (2 diagonals or horizontal and vertical middle line) then the above rules apply to both lines. Any light on these lines that is OFF needs to be clicked and any light on these diagonals that is ON must NOT be clicked to have all lights ON and to have a symmetric solution.
If the board is not mirror symmetric but rotational symmetric then one makes groups of clicks with the same rotational symmetry to preserve this symmetry.
Whatever the symmetry is, when you click a light then click the symmetry related light(s) as well. In other words, if it is a 90° symmetry (4-fold rotational symmetry) then click the other 3 lights as well, if it is a 180° symmetry (2-fold rotational symmetry) then click the other one light as well. If it is a mirror symmetry then click the mirror symmetric light as well. If a light is its own symmetric light then click it only once. Examples for lights to be clicked once are the center light under any symmetry or a light on a diagonal under diagonal mirror symmetry or a light on a horizontal or vertical line through the center if that line is the symmetry line.
If after clicking a light and all its symmetric lights the symmetry increases (e.g. 2 mirror symmetries instead of one mirror symmetry) then use the increased symmetry from now on.
What if the board pattern has no symmetry?
If the board has no symmetry then one can try making clicks that switch more lights ON than OFF. Then one can make moves that bring OFF lights closer together. Sooner or later a symmetric position results and then one continues with symmetric clicks.
The last three questions concern more general cases.
What is a general solution strategy for finding a sequence of clicks that result in some given board pattern?
The history of this puzzle and the outline of a general solution is given on Wikipedia. Another more mathematical description with more references is given on Wolfram MathWorld. You might want to check whether our findings are contained in these publications or not.
Can every initial position of some lights being ON and the rest being OFF be changed into all lights being ON? If not, how can one tell? How can one find out whether the board of a given size has a cycle and if it exists, find the cycle?
These questions can be answered by formulating and investigating a linear algebraic system of equations. More about that can be read in references given above.
Would the above theory still hold if purple lights are present?
Purple lights potentially change everything. One has to check each statement above whether it is still valid in the presence of purple lights or how to modify the statements to keep them true. Linear algebra would be flexible and general enough to cover boards with purple lights.
Слідкуйте за оновленнями або підписуйтесь на них: