Puzzle geser 3 x 2

Jan 30 2021

Mungkinkah memecahkan teka-teki geser seperti ini (x adalah spasi) ?:

1  3  2

4  5  x

Saya belum bisa menyelesaikan ini dan saya bahkan tidak tahu apakah itu mungkin.

Jawaban

8 Randal'Thor Jan 30 2021 at 02:42

Larutan:

tidak, itu tidak mungkin untuk mendapatkan dari posisi yang Anda berikan pada teka-teki "terselesaikan" dengan $1,2,3,4,5$dalam urutan yang benar dan celah di kanan bawah. Hal ini dapat dibuktikan dengan cara yang sama seperti " teka-teki 14,15 " yang asli (terkenal) .

Ini dapat ditunjukkan dengan menggunakan beberapa teori grup dasar, mirip dengan bukti yang ditemukan di sini .

Setiap posisi teka-teki dapat diartikan sebagai permutasi dari $\{1,2,3,4,5,6\}$, dengan kotak kosong diartikan sebagai $6$. Setiap gerakan puzzle kemudian dapat diartikan sebagai transposisi dalam kelompok simetris$S_6$, menukar kotak kosong $6$dengan salah satu ubin yang sebenarnya. Posisi yang Anda berikan berjarak satu transposisi dari posisi terselesaikan, tetapi hanya dapat dicapai dalam jumlah genap$6$-swaps, karena kotak kosong itu $6$harus berakhir di posisi yang sama, jadi gerakan naik-turunnya genap dan gerakan kiri-kanannya genap. Tetapi setiap kombinasi dari jumlah transposisi genap harus berada dalam grup bergantian$A_6$, dan oleh karena itu kami tidak dapat mencapai transposisi tunggal dengan kombinasi seperti itu.

6 Deusovi Jan 30 2021 at 02:41

Jika tujuan Anda adalah mendapatkan "1 2 3" di baris pertama dan "4 5 x" di baris kedua, jawabannya adalah tidak , itu tidak mungkin.

Ini adalah versi yang lebih kecil dari teka-teki 14-15 Sam Loyd . Jika Anda memiliki teka-teki geser dengan satu ruang kosong, Anda dapat memeriksa apakah teka-teki itu dapat diselesaikan berdasarkan paritas - jumlah sakelar yang Anda perlukan untuk mendapatkan solusi tersebut. Secara khusus:

  • Pertama, lakukan gerakan agar ubin kosong berada di tempat yang tepat.
  • Sekarang bayangkan Anda bisa secara ajaib memilih dua ubin untuk bertukar posisi. Berapa banyak swap yang dibutuhkan untuk memecahkan teka-teki ini?

Jika jumlah swap genap, puzzle asli dapat diselesaikan. Jika jumlah swap ganjil, puzzle asli tidak dapat diselesaikan. (Dengan kata lain, mulai dari teka-teki terpecahkan, apa pun gerakan yang Anda buat, Anda akan selalu berada dalam kasus genap - tidak ada cara untuk melompat di antara dua kasus hanya dengan menggeser ubin. Anda harus menipu dengan mengambil ubin keluar.)

Dalam contoh Anda, tepat ada satu pertukaran yang diperlukan untuk memecahkan teka-teki tersebut. Jadi tidak mungkin diselesaikan dengan menggeser.