Tugas puzzle "tag" adalah mengatur ubin bernomor. Saat ini, matematikawan telah memecahkan masalah terbalik - bagaimana mencampur puzzle.Anda mungkin memainkan tag. Ini adalah permainan yang membuat frustasi tetapi adiktif yang terdiri dari 15 ubin dan satu ruang kosong, disusun dalam kotak 4 oleh 4. Tugasnya adalah memindahkan ubin dan mengaturnya dalam urutan angka atau, dalam beberapa versi, mengumpulkan gambar dari mereka.
Setelah kemunculannya di tahun 1870-an, ia memasuki set standar permainan. Selain itu, itu menarik perhatian matematikawan yang telah mempelajari solusi puzzle dari berbagai ukuran dan konfigurasi awal selama lebih dari satu abad.
Saat ini
ada bukti baru dari solusi untuk "game at 15" , tetapi dalam urutan terbalik. Matematikawan Yoon Chu dan
Robert Howe dari Stony Brook University menentukan jumlah gerakan yang diperlukan untuk mengubah bidang yang dipesan menjadi acak.
Versi "tag" masalah dengan pengacakan diusulkan oleh
Percy Deaconess pada tahun 1988. Dia menyarankan bahwa mengacak teka-teki dengan ukuran berapa pun diperlukan sekitar
n 3 gerakan. Yaitu, untuk bidang 4 dengan 4, 4
3 , atau 64 gerakan akan diperlukan, dan untuk bidang 10 dengan 10, 10
3 , atau 1.000 gerakan. (Meskipun mereka masih disebut sebagai "Lima Belas," bidang dapat memiliki sejumlah ruang yang membentuk kuadrat yang benar.)
Ahli matematika di Universitas Stanford, Deaconess, menyarankan bahwa versinya tentang masalah “15-permainan” mewakili kelas besar masalah pengacakan yang serupa. Banyak dari tugas-tugas ini dihubungkan dengan ciri-ciri dasar alam, misalnya, dengan perubahan tempat pasangan basa DNA yang menyebabkan mutasi genetik, dan dengan bagaimana molekul dipisahkan satu sama lain dan menjadi tidak teratur - ini terjadi ketika es mencair.
Diakones berharap bahwa setelah memahami masalah keterikatan "bintik-bintik", kita akan dapat memahami bagaimana sistem yang tertata secara keseluruhan berubah menjadi keadaan campuran yang seragam.
Dalam situasi seperti "tag", keacakan berkembang satu langkah pada satu waktu. Bayangkan bidang yang dipesan sepenuhnya, dengan unit di kiri atas dan ruang kosong di kanan bawah. Kami memindahkan ubin sehingga ruang kosong bergerak satu kotak di salah satu dari empat arah yang mungkin: naik, turun, kiri atau kanan. (Demi keanggunan matematis, Chu dan Howe dianggap sebagai bidang yang ujung-ujungnya terhubung satu sama lain dalam sebuah cincin, sehingga ubin tidak pernah tersangkut di sudut-sudut.) Mari kita membuat pilihan acak. Sekarang bidang ini dalam konfigurasi baru - tidak cukup dalam urutan, tetapi tidak jauh dari itu. Ulangi proses ini. Jika Anda terus memindahkan kotak kosong, bidang akan semakin menjauh dari lokasi yang dipesan semula.
Fitur penting dari proses ini adalah bahwa pada setiap langkah konfigurasi bidang selanjutnya hanya bergantung pada konfigurasi saat ini. Ini mengingatkan kita pada permainan di Monopoly: probabilitas melempar dadu dan memindahkan dua kotak dari Park Place ke Boardwalk tidak tergantung pada gulungan yang membawa kita ke kandang Park Place.
Lima belas Creep merayap menuju kekacauan itu secara bertahap, selangkah demi selangkah. Banyak sistem lain, seperti es yang mencair, diacak dengan cara yang sama. Matematikawan mempelajari fenomena ini menggunakan model yang disebut "rantai Markov". Rantai Markov adalah cara formal mempelajari proses pengacakan di mana konfigurasi sistem selanjutnya hanya bergantung pada konfigurasi saat ini. Mereka berada di garis depan pemahaman matematis tentang peluang.
"Rantai Markov berada di mean emas - di satu sisi, kita masih dapat menganalisisnya, di sisi lain, mereka menggambarkan banyak fenomena yang menarik bagi kita," kata ahli matematika Yuval Perez, yang melakukan pekerjaan penting dalam teori probabilitas.
Dalam karya baru mereka, Chu dan Howe bekerja dengan pengacakan "tag" seperti rantai Markov. Secara khusus, mereka menganggap seperangkat angka yang disebut "matriks transisi" dari rantai Markov. Matriks transisi adalah serangkaian angka yang menentukan kemungkinan bahwa "game at 15" akan berpindah dari satu konfigurasi ke konfigurasi lainnya jika kita memutuskan untuk memindahkan ruang kosong secara acak.
Memahami matriks transisi adalah kunci untuk menghitung jumlah gerakan yang diperlukan untuk mengacak atau mengacak bidang yang dipesan. Secara khusus, Chu dan Hou fokus pada mendefinisikan himpunan bilangan yang mencirikan matriks transisi - bilangan yang disebut "nilai eigen."
“Dengan mengumpulkan informasi yang cukup tentang nilai eigen, kita bisa mendapatkan informasi pencampuran yang sangat akurat,” kata Howe.
Matriks transisi untuk "bintik-bintik" berisi sejumlah besar informasi yang mencerminkan triliunan konfigurasi berbeda yang bahkan dapat dibuat oleh bidang kecil berukuran 4 hingga 4. Ini lebih banyak informasi daripada yang bisa diproses langsung oleh ahli matematika. Oleh karena itu, alih-alih menganalisis matriks transisi pada setiap langkah jalur lapangan ke pengacakan, Chu dan Howe menemukan cara untuk mengkarakterisasi perilaku rata-rata dari seluruh matriks transisi selama perjalanan.
Pendekatan mereka mirip dengan bagaimana Anda dapat menemukan di mana kami kemungkinan besar akan berakhir di bidang Monopoli setelah 1000 gulungan dadu: Anda benar-benar dapat melempar dadu berkali-kali, atau hanya mengambil rata-rata beberapa gulungan dan memperkirakannya.
Dengan menggunakan teknik ini, Chu dan Howe menghitung nilai eigen dari matriks transisi, yang memberi tahu mereka berapa banyak gerakan yang perlu dilakukan untuk mengacak "titik-titik". Mereka bahkan menerima dua jawaban berdasarkan dua definisi keacakan yang berbeda.
Pertama, mereka dianggap sebagai bidang acak, di mana setiap ubin dengan probabilitas yang sama dapat berada di kuadrat bidang mana pun. Dengan definisi ini, mereka menemukan bahwa untuk mengacak suatu bidang
n ke
n, diperlukan 4 gerakan (mis. 256 langkah untuk bidang 4 dengan 4 dan 10.000 langkah untuk bidang 10 dengan 10). Ini lebih dari yang Diaconis prediksi (seperti yang kita ingat, dia menyarankan
3 langkah).
Definisi kedua dari kesempatan oleh Chu dan Hou lebih tegas. Mereka menganggap bidang acak, yang dengan probabilitas yang sama bisa dalam salah satu dari banyak konfigurasi yang mungkin. Mereka membuktikan bahwa sedikit langkah lagi diperlukan untuk mencapai definisi keacakan seperti itu - tidak lebih dari sekitar
4 log
dan gerakan.
Chu dan Howe menunjukkan bahwa mengacak "permainan 15" lebih sulit dari yang diprediksi Diaconis; dalam arti tertentu, ini menunjukkan bahwa dibutuhkan lebih banyak waktu dari yang diharapkan untuk sepenuhnya menghilangkan keteraturan dalam sistem. Berkat pekerjaan mereka, "tag" sekarang telah menjadi salah satu dari beberapa tugas pengacakan di mana, menurut Howe, "pada kenyataannya, jumlah langkah yang diperlukan untuk pengacakan diketahui."
Howe dan Perez sekarang bekerja untuk memperluas bukti. Di antara hal-hal lain, mereka tertarik pada apakah bidang mencapai kondisi acak dengan peningkatan ukuran dengan lompatan yang tajam. Sistem dengan perilaku ini tidak terlihat acak sama sekali, dan setelah hanya satu langkah mereka tiba-tiba berubah menjadi begitu.
"Kami tidak sepenuhnya memahami rantai Markov mana yang mendemonstrasikan tiba-tiba seperti itu," kata Perez. "Ini adalah salah satu misteri terbesar di daerah ini."