Lampu

Kita menggunakan peluang ini untuk berlatih formalisme matematik dan akan kumpulkan pernyataan ke dalam

Hipotesis (Pernyataan yang dicadang sebagai titik permulaan untuk siasatan lanjut)
Definisi (menerangkan maksud perkataan atau frasa)
Teorem (pernyataan jelas)
Lemma (kenyataan kecil)
Pembuktian (pernyataan yang menunjukkan tanpa ragu-ragu bahawa satu teorem atau lemma adalah betul. Simbol □ akan menunjukkan keakhiran satu pembuktian.)
Kololari (Pernyataan yang mengikuti terus dari satu teorem atau lemma)

Tidak. Status lampu bergantung hanya pada bilangan klik yang dibuat pada lampu tersebut dan sekitarnya, bukan pada susunan klik. Jika jumlah bilangan klik pada lampu dan lampu sekitarnya adalah genap, maka lampu tidak mengubah statusnya. Jika jumlah bilangan klik adalah ganjil maka statusnya berubah, bebas daripada susunan klik.

Contoh:

Pilih dua lampu bersebelahan yang berbeza, andaikan A dan B. Kemudian, klik mengikut susunan A, B, B, A. Apakah hasilnya? ↠ Tiada perubahan, kerana B, B tidak terjejas dan A, A juga tidak terjejas.

Sekarang mari kita terbalikkan susunan dua klik terdahulu dan klik mengikut susunan B, A, B, A. Apakah hasilnya? ↠ Sekali lagi, tiada perubahan. Susunan dua klik terdahulu tidak penting. Begitu juga halnya, jika kita klik dua lampu tersebut dalam sebarang susunan. Susunan klik tidak penting.

Salah satu cara untuk mengurangkan bilangan klik adalah seperti berikut.

Semasa menyelesaikan soalan tersebut, seseorang akan merekod bilangan klik yang dibuat pada lampu ini. Kemudian, seseorang menetapkan setiap bilangan klik genap pada lampu kepada sifar dan setiap bilangan klik ganjil kepada 1. Susunan baru mempunyai kesan yang sama dan juga merupakan satu penyelesaian.

Definasi:Susunan klik dipanggil dikurangkan jika setiap lampu diklik paling banyak sekali. Proses di atas dipanggil pengurangan.

t

l

t

l

t

l

Kerana susunan klik tidak penting, ia cukup untuk mengetahui untuk setiap lampu sama ada ia diklik dalam penyelesaian atau tidak. Oleh itu, ia sudah memadai untuk satu pencarian kekerasan yang lengkap untuk mencuba klik semua kombinasi lampu.

Jika papan tersebut terdapat t×l lampu maka ada 2^t×l kombinasi (2 pilihan untuk setiap lampu sama ada ia diklik dalam kombinasi itu atau tidak). Pencarian kekerasan sedemikian akan mengambil masa terlalu lama. Namun begitu, jika “Nota Bantuan” telah diaktifkan (tidak tersedia dalam pertandingan) maka seseorang boleh mengklik semua lampu satu demi satu dan semak sama ada klik ini membawa anda lebih dekat kepada penyelesaian. Jika betul, biarkan ia, jika tidak, klik sekali lagi.

Lemma:

Jika pada grid segi empat tepat, semua lampu telah BERNYALA dan semua lampu diklik sekali kemudian lampu di sudut DIPADAMKAN (O), lampu lain di bahagian tepi BERNYALA (#) dan lampu yang lain adalah DIPADAMKAN (O), seperti yang ditunjukkan dalam papan 4 x 4 ini.

            # # # #      O # # O
            # # # #      # O O #
            # # # #      # O O #
            # # # #      O # # O

            before       after

Pembuktian

Bermula dengan, setiap lampu diklik dan oleh itu berubah sekali. Setiap lampu juga berubah apabila lampu bersebelahan diklik.

Oleh itu, jika nombor lampu bersebelahan adalah genap, maka lampu tersebut akan diubah dengan bilangan klik genap tambahan, jadi dalam jumlah bilangan ganjil. Oleh itu, ia masih DIPADAMKAN jika pada mulanya ia BERNYALA.

Begitu juga, jika numbor lampu bersebelahan adalah ganjil, maka lampu tersebut akan diubah lebih banyak kali ganjil, jadi dalam jumlah genap bilangan kali. Oleh itu, ia masih BERNYALA jika pada mulanya BERNYALA.

Dengan mengira bilangan jiran setiap lampu, seseorang akan mendapat pernyataan lemma. □

Jika setiap lampu diklik genap bilangan kali, maka kekurangan (telah dijelas sebelum) sifar kali klik kepada setiap lampu, dan ia bukan sesuatu yang mengejutkan bahawa semua lampu kekal BERNYALA. Tetapi adakah terdapat susunan yang dikurangkan dengan klik yang bermula dan berakhir dengan semua lampu BERNYALA?

Definisi:

Satu susunan kekurangan yang merangkumi sekurang-kurangnya satu klik dipanggil kitaran jika semua lampu mempunyai status yang sama sebelum dan selepas susunan tersebut.

Kami akan mencari kitaran dengan bermula dengan semua lampu BERNYALA dan berakhir dengan semua lampu BERNYALA. Kitaran sedemikian kemudiannya akan juga meninggalkan setiap keadaan awal yang lain tidak berubah, i.e. jika kami mulakan dengan papan dengan beberapa lampu BERNYALA dan beberapa DIPADAMKAN, dan kami melakukan kitaran ini, lampu yang sama akan BERNYALA dan DIPADAMKAN. Boleh anda mengetahui sebabnya?

Satu kemungkinan untuk mencari satu kitaran adalah untuk

bermula dengan semua lampu BERNYALA
mempunyai dua susunan kekurangan berbeza yang kedua-duanya lampu yang sama DIPADAMKAN, contohnya, semua lampu DIPADAMKAN
menggabungkan kedua-dua susunan kepada satu susunan yang, jika bermula dengan semua lampu BERNYALA, akan berakhir dengan semua lampu BERNYALA.
Kurangkan gabungan susunan tersebut untuk mendapat satu kitaran. Kitaran berkurangan ini mengandungi klik kerana kedua-dua susunan gabungan adalah berbeza, jadi mesti ada sekurang-kurangnya satu klik dalam satu susunan yang bukan dalam susunan asal yang lain. Susunan gabungan yang dikurangkan akan mempunyai klik ini.

Untuk saiz papan yang manakah ini kemungkinan? Untuk saiz papan tertentu, seseorang boleh menjawab soalan ini dengan merumuskan sistem persamaan algebra linear dan menyiasatinya. Lebih lanjut mengenai itu boleh dibaca dalam rujukan yang diberikan di bawah.

            O # # O
            # O O #
            # O O #
            O # # O

Kerana kita sedang mencari kitaran, i.e. bermula dan berakhir dengan semua lampu BERNYALA, kita mencuba dan klik semua lampu yang DIPADAMKAN (ditunjukkan dengan O) sekali yang bukan hanya klik MENYALAKAN lampu tersebut tetapi semua lampu BERNYALA sekali. Sila sahkannya sendiri.

Untuk mengingatkan diri kita: Pada mulanya, kami klik semua lampu dan kemudian klik sekali lagi pada lampu pada kedua-dua pepenjuru. Dengan mengurangkan keseluruhan susunan ini, semua klik dua kali pada lampu pepenjuru akan dibuang dan hanya klik pada lampu # di papan di atas akan dikekalkan. Jadi, kami bermula dengan semua lampu BERNYALA dan berakhir dengan semua lampu BERNYALA. Oleh itu, 8 klik pada # dalam papan di atas membentuk satu kitaran. Hurray, Kita dapat cari satu kitaran! 🥳

Jika satu kitaran diketahui maka ini mungkin boleh digunakan untuk mengurangkan susunan klik dengan lebih lanjut.

Lemma:

Jika satu kitaran dengan klik sebanyak c diketahui dan satu susunan diberi n klik tergolong dalam kitaran tersebut, maka menggantikan n klik ini dengan c−n klik tidak dalam kitaran memberikan susunan yang setara.

Pembuktian:

Pembuktian ini adalah satu pembinaan, I.e. ia menunjukkan bagaimana untuk membina susunan sedemikian.

Jika kita tambahkan susunan dengan kitaran maka susunan gabungan baharu akan menjadi setara kerana kita menambahkan satu kitaran. Dalam susunan gabungan, n klik dilakukan dua kali, sekali di susunan asal dan sekali di dalam kitaran. Dengan pengurangan, i.e. memadamkan klik dua kali ini, susunan baharu masih akan setara (kerana pengurangan menghasilkan susunan yang setara), bukannya n klik, c-n klik tergolong dalam kitaran.

Kololari:

Jika c−n < n maka susunan baru adalah lebih pendek. Ini adalah kejadiannya jika dan hanya jika n > c/2. Dalam ayat: Jika susunan mengandungi lebih daripada separuh daripada klik kitaran, maka susunan itu boleh dipendekkan dengan menambahkan kitaran dan memadam klik dua kali.

Contohnya:

Membuat satu senarai dengan 13 lampu di atas papan 4x4 (dengan pensel pada kertas), bermula dengan semua lampu BERNYALA dan klik 13 lampu, kemudian melukis satu gambar hasil. (Kenapa 13 dan bukan, andaikan 12? Kita akan lihat lebih lanjut di bawah. :-) ) Sekarang semak yang mana antara 13 klik tergolong dalam kitaran dan buat senarai klik baharu (dengan pensel di atas kertas) di mana klik kitaran ini digantian dengan klik lain dalam kitaran. Mulakan semula dengan semua lampu BERNYALA dan lakukan susunan klik yang lebih pendek ini.

Apakah hasilnya?

Teorem:

Susunan klik pada papan 4x4 boleh dikurangkan kepada maksimum 12 klik.

Pembuktian:

Kami mempelajari yang susunan yang dikurangkan pada papan 4x4 hanya boleh mempunyai 4x4=16 klik. Kami tahu kitaran 8 klik untuk papan 4x4. Oleh itu, susunan boleh mempunyai paling banyak 16-8=8 klik yang bukan milik kitaran. Kami juga mendapati bahawa jika susunan mempunyai lebih daripada separuh daripada klik kitaran, maka ia boleh dipendekkan. Oleh itu, susunan yang dikurangkan dan dipendekkan boleh mempunyai paling banyak:
8 (klik bukan milik kitaran)
+ 8/2 (separuh klik daripada kitaran)
= 12 klik
pada satu papan 4x4. □

Kololari:

Semua soalan kemungkinan papan 4x4 untuk membuat semua lampu BERNYALA boleh diselesaikan dengan paling banyak 12 klik.

Penjelasan:

Teorem tidak menyatakan sama ada wujub susunan sepanjang 12 yang tidak boleh dipendekkan dengan kitaran. Mungkin panjang maksimum ialah 12, 10 atau 8. Teorem hanya mengatakan bahawa ia tidak boleh mempunyai lebih daripada 12 klik.

Kami klik semua lampu yang tiada dalam kitaran, jadi kesemua 8 lampu pada pepenjuru. Kemudian, kami memilih 4 lampu dari kitaran, contohnya, satu pada setiap sisi mengikut arah jam. Dengan © menunjukkan klik, kami membuat 12 klik ini:

            © · © ©
            © © © ·
            · © © ©
            © © · ©

menghasilkan di papan

            # O O #
            O # # O
            O # # O
            # O O #

Tidak. Dengan hanya 4 klik ini

            · © · ·
            © · · ·
            · · · ©
            · · © ·

            # O O #
            O # # O
            O # # O
            # O O #

Ini bermakna kita mempunyai kitaran baharu 12+4=16, HURRAY! 🥳 Jika kita membuang klik dua kali ((© + © = ·), kitaran baharu 12 klik ini kekal:

            © · © ©       · © · ·       © © © ©
            © © © ·   +   © · · ·   =   · © © ·
            · © © ©       · · · ©       · © © ·
            © © · ©       · · © ·       © © © ©

Jumlah dua kitaran mestilah kitaran, i.e. ia tidak mengubahkan papan tersebut:

            © © © ©       · © © ·       © · · ©
            · © © ·   +   © · · ©   =   © © © ©
            · © © ·       © · · ©       © © © ©
            © © © ©       · © © ·       © · · ©

Memberikan versi pusingan 90° bagi kitaran 12 klik, yang merupakan kitaran ke-3 baru kami. Sila sahkan bahawa ini adalah kitaran juga.

Susunan

            © · © ©         · · © ·
            © · · ·   and   © © © ·
            · · · ©         · © © ©
            © © · ©         · © · ·

mempunyai 8 klik masing-masing.

Bolehkan mereka dipendekkan dengan 3 kitaran?

Kami membuat andaian yang tidak terbukti ini:

Hipotesis:

Panjang maksimum susunan klik pada papan 4x4 yang tidak boleh dipendekkan dengan kitaran ialah 8.

Anda dialu-alukan untuk membuktikannya. Pertama, seseorang perlu meunjukkan bahawa tiada kitaran bebas lain.

Sama seperti papan 4x4, kami

bermula dengan semua lampu BERNYALA

klik setiap lampu sekali dan

Klik semua lampu pepenjuru sekali, dan juga klik sekali pada lampu di tengah . Hasilnya ialah semua lampu adalah BERNYALA.

mengurangkan susunan dengan membuang semua klik dua kali di pepenjuru meninggalkan 25-9=16 klik seperti ditunjukkan di ©:

                    · © © © ·
                    © · © · ©
                    © © · © ©      (1)
                    © · © · ©
                    · © © © ·

dan meraikan, kami telah mencarikan satu kitaran, HURRAY! 🥳

Sila mancuba dan menyakinkan sendiri anda bahawa klik 16 lampu bertanda © itu tidak mengubahkan lampu pada papan 5x5. Ini paling mudah dilihat apabila bermula dengan semua lampu BERNYALA.

Teorem:

Susunan klik pada papan 5x5 tidak boleh mempunyai lebih daripada 17 klik.

Pembuktian:

Kami mengetahui bahawa susunan yang dikurangkan pada papan 5x5 hanya boleh mempunyai 5x5=25 klik. Kami mengetahui kitaran 16 klik untuk papan 5x5.Oleh itu, susunan boleh mempunyai paling banyak 25-16=9 klik yang bukan milik kitaran. Kami juga mendapati bahawa jika susunan mempunyai lebih daripada separuh daripada klik kitaran, maka ia boleh dipendekkan. Oleh itu, susunan yang dikurangkan dan dipendekkan boleh mempunyai paling banyak:
9 (klik yang bukan milik kitaran)
+ 16/2 (separuh klik daripada kitaran)
= 17 klik
pada satu papan 5x5. □

Kalolari:

Jika satu soalan papan 5x5 untuk membuat semua lampu BERNYALA mempunyai penyelesaian, maka terdapat penyelesaian dengan paling banyak 17 klik.

Penjelasan:

Adakah ini bermakna terdapat susunan 17 klik yang tidak boleh dipendekkan?

Jawapan:

Tidak. Setakat ini kita tidak tahu.

Kerana papan itu berbentuk segi empat tepat, corak lampu yang BERNYALA/DIPADAMKAN mungkin membuat putaran simetri sebanyak 900 atau 1800 atau ia mungkin mempunyai cermin simetri di sepanjang garis simetri mendatar atau menegak. Jika papan itu berbentuk segi empat sama, ia mungkin juga mempunyai cermin simetri sepanjang pepenjuru atau kedua-dua pepenjuru.

Seterusnya, ideanya ialah penyelesaiannya terdiri daripada beberapa klik yang mempunyai simetri itu dan klik lain yang tidak mempunyai simetri itu.

Bagaimana kita boleh membuat kemajuan?

Kita mungkin terjumpa papan seperti ini:

            O O O O O         
            # O # O #         
            O O # O O      (2)
            # O # O #         
            O O O O O

dan telah lupa bagaimana kita mencapainya. Ini mudah untuk diketahui dengan memilih “BUKA Nota Bantuan” dan klik setiap tempat. Jika nombor yang ditunjukkan dalam “Nota Bantuan: Anda boleh menang dengan sekurang-kurangnya XX klik adalah lebih rendah, kita mengambill nota pada tempat tersebut, dan jika tidak, kita klik semula. Kitai mencari penyelesaian ini di mana © menunjukkan klik:

            · · · · ·
            © © © © ©
            · · © · ·      (3)
            · © · © ·
            © · © · ©

Sekarang kita sepatutnya terkejut dan sangat ingin tahu!

Mengapa?

Apa sekarang?

Oleh itu, kami menulis (3) sebagai hasil tambah bahagian simetri dan bukan simetri:

        · · · · ·     · · · · ·     · · · · ·
        © © © © ©     · © · © ·     © · © · ©
        · · © · ·  =  · · © · ·  +  · · · · ·
        · © · © ·     · © · © ·     · · · · ·
        © · © · ©     · · · · ·     © · © · ©

Sama seperti pemburu harta karun mencari permata, kami dalam matematik juga mencari objek yang unik. Penguraian di atas bukanlah unik. Terdapat banyak cara untuk menulis bahagian tidak simetri sebagai hasil tambah bagi bahagian simetri dan satu lagi bahagian tidak simetri.

Adakah terdapat perpecahan yang unik?

Kami guna © + © = · dan oleh itu tulislah sekarang

           · · · · ·     · · · · ·     · · · · ·     · · · · ·
           © © © © ©     · © · © ·     © · © · ©     · · · · ·
           · · © · ·  =  · · © · ·  +  · · · · ·  +  · · · · ·
           · © · © ·     · © · © ·     © · © · ©     © · © · ©
           © · © · ©     · · · · ·     · · · · ·     © · © · ©

           · · · · ·     · · · · ·
           © © © © ©     · · · · ·
        =  · · © · ·  +  · · · · ·
           © © © © ©     © · © · ©
           · · · · ·     © · © · ©

Mengetahui bahawa kita sedang melakukan sesuatu, kami kini ingin mengetahui semua tentangnya.

Kerana papa nasal adalah simetri dan bahagian simetri mesti membuat papan simetri, oleh itu susunan tidak simetri juga mesti membuat papan simetri.

Apa itu?

Kita akan melihat bahawa terdapat sangat sedikit penyelesaian tidak simetri yang menghasilkan papan simetri dan mempunyai semua klik pada satu sisi garis simetri.

Apa akan terjadi jika seseorang tertanya-tanya di sekeliling papan (5) dan melihat padanya dan penyelesaian (4) dari sudut lain?

Jadi (6) ialah satu lagi susunan bukan simetri yang menghasilkan papan simetri yang sama (5). Adakah itu satu kebetulan atau adakah itu secara umum?

Ini adalah kenyataan umum:

Jika soalan (di sini (5), mempunyai simetri 1800) dihasilkan oleh susunan tidak simetri, kemudian melakukan operasi simetri (di sini putaran 180°) pada susunan ini menjana susunan bukan simetri baharu (di sini (6)) yang mencipta papan yang sama (di sini (5)).

Apa akan berlaku apabila seseorang melaksanakan kedua-dua susunan tidak simetri?

Untuk apa kita boleh menggunakan kitaran baharu ini?

Bolehkah seseorang memendekkan kitaran 16 klik dengan kitaran 12 klik? Hasilnya mestilah kitaran kerana kitaran + kitaran + = kitaran.

Adakah kitaran 16-klik juga merupakan jumlah dua penyelesaian tidak simetri bagi soalan simetri?

Bagaimanakah ia membantu menyelesaikan papan simetri?

Kami tidak menjawab soalan ini, tetapi kamu mempunyai dua cadangan.

Hipotesis:

Tiada kitaran lain untuk papan 5x5 yang bukan gabungan 3 kitaran dengan 12, 12 dan 16 klik.

Hipotesis:

Panjang maksimum susunan klik yang dipendekkan pada papan 5x5 ialah 13.

Kami menyerahkan kepada anda untuk memikirkan bukti atau contoh balas dalam bentuk kitaran bebas yang lain atau susunan dengan lebih daripada 13 klik yang tidak boleh dipendekkan dengan 3 kitaran (7), (8) dan (1) mempunyai 12, 12 dan 16 klik.Hipotesis pertama boleh disemak menggunakan algebra linear (lihat lebih lanjut di bawah), tetapi alangkah baiknya jika ada satu pembuktian ringkas atau kitaran yang berbeza. Contoh susunan dengan 13 klik yang tidak boleh dikurangkan dengan 3 kitaran ialah

            © · © · ©
            · © · © · 
            © · © · ©
            · © · © · 
            © · © · ©

Berseronoklah dalam mencari (semula) dan membuktikan!

Dengan t x l lampu, mempunyai 2 t x l corak lampu BERNYALA/DIPADAMKAN. Seperti yang kita ketahui sebelum ini, ada juga s t x l susunan klik kemungkinan.

Tetapi terdapat susunan yang menghasilkan corak papan yang sama, iaitu sebarang susunan dan susunan + kitaran ini. Oleh itu, kami mempunyai lebih banyak susunan daripada corak papan yang boleh dicapai, jadi mesti ada corak papan yang tidak dapat dicapai.

Dalam matematik, terdapat perkataan untuk situasi sedemikian. Jika setiap susunan klik akan menghasilkan corak yang berbeza, maka peta susunan kepada corak akan dipanggil injektif. Jika setiap corak adalah hasil daripada beberapa susunan klik, maka peta susunan kepada corak akan dipanggil surjektif. Oleh itu, peta susunan klik pada corak kami adalah bukan injektif dan bukan surjektif.

Latihan persediaan

Apakah yang perlu dicuba dahuli jika terdapat sekumpulan kecil lampu berdekatan yang DIPADAMKAN?

Bagaimana jika corak papan mempunyai simetri?

Papan permulaan mungkin cerminkan simetri berkenaan dengan satu atau kedua-dua pepenjuru atau dengan garis simetri mendatar dan/atau menegak yang berkenaan. Simetri lain mungkin adalah simetri putaran 90° atau 180°. Dalam bahagian, peranan apakah yang dimainkan oleh simetri dalam permainan ini? Kami memperoleh strategi berikut.

Seseorang melakukan kumpulan klik simetri yang mengekalkan simetri sehingga sama ada semua lampu BERNYALA, atau apabila mempunyai papan bersaiz 5x5 sehingga seseorang mencapai salah satu papan ini:

                    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 #

(atau putaran 90° mereka) dan kemudian seseorang melaksanakan susunan sahaja:

                    · · · · ·            · · · · ·             · © © © ·
                    · · · · ·            © · · · ·             © · © · ©
                    · · · · ·  (4) resp  © © · · ·  (13) resp  © © · © ©  (1)
                    © · © · ©            © · © · ·             © · © · ©
                    © · © · ©            · © © © ·             · © © © ·

(masing-masing 90° putaran mereka).

Apakah maksud “bermain simetri”?

Bagaimana jika corak papan tidak mempunyai simetri?

Sejarah permainan ini dan garis besar penyelesaian umum telah diberikan di Wikipedia. Satu lagi penerangan matematik dengan lebih banyak rujukan diberikan pada Wolfram MathWorld. Anda mungkin ingin menyemak sama ada penemuan kami terkandung dalam penerbitan ini atau tidak.

Soalan-soalan ini boleh dijawab dengan merumus dan menyiasat sistem persamaan algebra linear. Lebih lanjut mengenai itu boleh dibaca dalam rujukan yang diberikan di atas.

Lampu ungu mengubah segala-galanya secara potensi. Seseorang perlu menyemak setiap pernyataan di atas sama ada ia masih sah dengan kehadiran lampu ungu atau cara mengubah suai kenyataan untuk memastikan ia benar. Algebra linear akan menjadi fleksibel dan cukup umum untuk menutup papan dengan lampu ungu.