Boggle Numerik Dasar
Dalam posting ini , kami diperkenalkan dengan permainan Numerical Boggle di a$6 \times 6$ papan, aturannya adalah sebagai berikut
- Setiap sel harus berisi satu digit dari $0$ untuk $9$.
- Mulai dalam satu sel Anda mengumpulkan digit saat Anda pindah ke sel tetangga (ke semua 8 arah). Saat digit dikumpulkan, digit tersebut digabungkan dari kiri ke kanan, untuk membentuk satu nomor. Perhatikan bahwa digit awal dikumpulkan juga dan Anda dapat mengunjungi kembali sel.
Tugasnya kemudian adalah membangun kisi semacam itu (dengan ukuran $6 \times 6$) sedemikian rupa sehingga bilangan positif terkecil yang tidak dapat dibangun menjadi sebesar mungkin.
Jelas, game ini dan pengoptimalan selanjutnya dapat digeneralisasikan ke kisi persegi dengan berbagai ukuran, $n \times n$.
Selain itu, kita tidak perlu membatasi diri pada basis$10$. Diberikan bilangan bulat positif$b$, kita dapat memutuskan bahwa setiap sel harus berisi satu digit dari $0$ untuk $b-1$ dan mengajukan pengoptimalan sehubungan dengan basis baru ini (dengan pengecualian unary yang hanya menggunakan $1$).
Dimotivasi oleh generalisasi ini, kita dapat melihat masalah dalam basis yang lebih kecil.
Secara khusus, jika kita melihat kasusnya$n=2$ dan $b=2$, tugas pengoptimalan kami dapat menghasilkan hal seperti berikut ini
Ternyata, untuk kisi ini (atau memang ada $2 \times 2$ grid dengan dua $0$s dan dua $1$s) dimungkinkan untuk membangun setiap bilangan biner sesuai dengan aturan Numerical Boggle (coba sendiri). Kita akan mengatakan bahwa grid seperti itu memiliki basis yang tak terbatas$b$.
Selanjutnya, kami akan mengatakan itu sebagai basis $b$ mengakui kisi dengan luas tak terbatas apakah ada beberapa kisi persegi dengan ukuran terbatas ($n \times n$) yang memiliki jangkauan tak terbatas di basis $b$. Ini membawa kita ke teka-teki kita.
Apa bilangan bulat positif terbesar $b$ yang menerima kisi persegi berhingga dengan luas tak terbatas atau melakukan a $b$ada? Mohon berikan bukti jawaban Anda.
Jawaban
Berikut adalah batas atas untuk mencocokkan batas bawah dari jawaban lain yang saya pikir cocok dengan batas bawah, tetapi saya salah paham dengan aturan Boggle:
Di mana saja $k\times k$ papan, jumlah panjang-$n$ jalur tumbuh secara kasar sebagai $8^n$. Misalnya, itu dibatasi oleh$k^2 \cdot 8^n$: kita punya $k^2$ tempat untuk memulai, dan dari sana, setiap langkah masuk ke salah satu $8$petunjuk arah. (Tidak setiap langkah di setiap arah selalu memungkinkan, tetapi ini adalah batas atas.)
Namun, jumlah $n$-digit angka dalam basis $b$ tumbuh secara kasar $b^n$: ini $(b-1)b^{n-1}$. Jadi untuk$b \ge 9$, jumlah jalur panjang yang mungkin $n$ pada akhirnya akan lebih kecil dari jumlah $n$-digit angka, dan akan ada beberapa angka yang tidak dapat kami temukan. Semakin besar kita membuat papan, semakin nanti malapetaka ini akan terjadi, namun akan terjadi pada akhirnya.
Masih ada celah untuk
$5 \le b \le 8$, di mana solusi mungkin ada, tetapi kami tidak mengetahuinya.
Karena kisi kita terbatas, dan kita harus bisa mewakili urutan panjang tak terhingga, tampaknya tidak ada gunanya menambahkan digit X ke kisi di beberapa persegi yang tidak terhubung ke setiap digit: jika kita pernah menggunakan seperti itu digit, maka pada langkah sebelumnya juga perlu ada kotak lain dengan X yang dapat diakses untuk urutan yang tidak dapat dibuat melalui X yang terhubung dengan buruk. Hal ini tampaknya menyebabkan percabangan tak terbatas (karena kita harus mengakomodasi setiap urutan yang mungkin, kita dapat berasumsi bahwa ada musuh jahat yang selalu memilih jalur yang paling menyebalkan bagi kita), yang tidak dapat kita lakukan di medan permainan yang terbatas.
Saya tidak yakin apakah hal di atas benar-benar benar, tetapi dengan asumsi itu benar, mari kita coba membuat beberapa papan "terhubung dengan baik" di mana setiap digit terhubung ke semua kemungkinan digit, sehingga dengan mudah memberikan "batas tak terbatas" yang diperlukan.
Basis-3 tampak sederhana (pad dengan angka acak jika Anda benar-benar menginginkan persegi):
0 1 1 0
0 2 2 0
atau dengan jumlah digit minimum yang mungkin, yang sesuai dengan kuadrat minimum yang memungkinkan:
0 0 1 2 1 2
Basis 4 agak kurang sepele, tetapi masih bisa dilakukan:
0 0 1 2 3 1 1 3 2 1 0 0
Basis-5 menghadirkan kesulitan:
digit paling kiri yang "terhubung dengan baik" di baris atas tidak boleh memiliki 5 tetangga di sisi bawah dan kanan saja:
0 4 1 2 3
Kami tentu saja dapat memperbaikinya dengan menambahkan nomor lain, tetapi kami masih memiliki masalah itu
tidak boleh ada digit yang sekaligus
1. terhubung dengan baik (di samping semua kemungkinan digit),
2. di baris atas, dan
3. digit paling kiri di barisnya.
Jadi dengan asumsi bahwa dugaan di bab pertama bernilai apa pun (saya sama sekali tidak yakin), maka yang paling bisa kita lakukan adalah
base-4, yang pas di dalam papan boggle 4x4 standar.
Sedikit perbaikan pada jawaban Misha Lavrov.
Jumlah jalur panjang yang berbeda $nk$ yang dapat ditelusuri di file $n\times n$ jaringan paling banyak $n^2(8^n-3^n)^k$. Ini karena masing-masing kelompok$n$ gerakan berurutan tidak bisa semuanya naik, jadi ada paling banyak $8^n-3^n$ urutan petunjuk yang diizinkan untuk setiap grup.
Itu $k$Akar dari ini adalah $n^{2/k}(8^n-3^n)<8^n$ untuk $k$ cukup besar (dalam hal $n$). Dengan demikian, Anda dapat membuat lebih sedikit dari$8^{nk}$ jumlah panjang yang berbeda $nk$ untuk beberapa nilai $k$, jadi kasusnya $b=8$ juga tidak mungkin.
Sayangnya saya rasa ini tidak bisa didorong lebih jauh:
perhitungan back-of-an-envelope menunjukkan bahwa untuk cukup besar $n$ sebenarnya ada lebih dari $7^k$ jalur panjang yang berbeda $k$ untuk setiap $k$, karena berjalan secara acak $8$ pilihan sama sekali tapi $k-O(k/n)$ langkah dengan probabilitas tinggi, dan $8^{1-O(1/n)}>7$ untuk yang besar $n$.
Saya rasa saya memiliki argumen yang lebih kuat yang mendukung jawaban Bass.
1. Jika banyak pulau papan Boggle dapat secara bersama-sama menghasilkan semua urutan, setidaknya satu pulau menghasilkan proporsi bukan nol dari semua urutan.
2. Jika sebuah pulau dapat menghasilkan proporsi bukan nol dari semua urutan, ia sebenarnya dapat menghasilkan semua urutan (dan dengan demikian memiliki jangkauan yang tak terbatas). Rasional: Jika tidak dapat menghasilkan urutan panjang tertentu yang terbatas$k$, proporsi urutan yang dihasilkan untuk panjangnya $\ell+1$ adalah (secara kasar) $1-1/2^k$ kali itu untuk panjangnya $\ell$. Sebab, proporsinya untuk semua$\ell \in [1, \infty)$konvergen ke nol. Kontradiksi.
3. Jika papan berhingga dengan luas tak terhingga memiliki sel yang tidak menghasilkan semua urutan yang dimulai dengan dirinya sendiri, sel itu dapat dihilangkan tanpa merusak batas tak terhingga. Rasional: Asumsikan kesimpulannya salah. Kemudian beberapa urutan dipaksa untuk melewati sel yang dimaksud, dan dengan asumsi, kita dapat membuat urutan yang tidak dapat dihasilkan oleh papan (yang merupakan urutan untuk memaksa ke sel + urutan yang tidak dapat dihasilkan dari sel) . Kontradiksi.
4. Semua papan terbatas untuk $b \ge 5$berisi setidaknya satu sel yang tidak dapat menghasilkan semua urutan yang dimulai dengan dirinya sendiri. Ini sepele seperti yang diamati dalam jawaban Bass, karena sel paling kiri paling atas selalu memiliki derajat keluar 4 atau lebih rendah.
5. Menggabungkan 3 dan 4, tidak ada papan berhingga dengan luas tak terbatas $b \ge 5$.
Dengan asumsi tidak ada lubang logis dalam klaim di atas, jawabannya adalah
Basis maksimum yang memungkinkan papan dengan luas tak terbatas adalah 4 , seperti yang ditemukan oleh Bass.
Saya kira langkah 1 dan 2 tidak terlalu diperlukan untuk kesimpulan (seperti
kumpulan pulau yang terbatas masih merupakan papan yang terbatas
), tapi saya memutuskan untuk menyimpannya karena IMO adalah pengamatan yang menarik.
Sketsa solusi (?) Untuk b = 5. Saya menunjukkan gambar yang belum selesai untuk mengundang beberapa umpan balik.
Ide umum: jalan raya dengan putaran-u:
cetak biru berkode warna. Biru adalah latar belakang. garis putih adalah alat bantu visual untuk memisahkan empat strip dengan arah bolak-balik yang masing-masing memiliki empat "jalur". Perhatikan bahwa ini hanya menampilkan tata letak umum; solusi terakhir mungkin membutuhkan strip yang lebih panjang dan lebih banyak.
Perhatikan bahwa dalam satu strip, setiap persegi memiliki semua tetangga yang diperlukan dalam strip yang sama.
Jadi satu-satunya cara untuk membunuhnya adalah dengan membiaskan gerakan ke satu arah. Di situlah strip tetangga ikut bermain. Kami dapat memutar balik mereka dan kembali jika diperlukan.
Jadi apakah ini menyelesaikan segalanya?
Tidak 100% yakin. Ada dua masalah: 1. kita bisa berputar balik di banyak tempat tetapi tidak di semua tempat. 2. kita tidak selalu bisa memilih strip untuk diubah. Jadi, pada prinsipnya, kita mungkin berakhir di jalur terakhir dan keluar dari jalan raya.
2. mungkin tidak ada masalah karena untuk memaksa ini akan membutuhkan lebih atau kurang selalu gaya gerakan diagonal (gerakan ortogonal hampir pasti memberi kita terlalu banyak ruang gerak) dan memaksa mengubah jalur pada waktu yang tepat. Karena kami mungkin tidak dapat menahan diri untuk tidak memiliki kendali atas kapan harus memutar balik persyaratan kedua ini tampaknya terlalu sulit untuk diterapkan.
Perasaan saya adalah bahwa 1 dapat diatasi juga (saya tidak mau repot-repot untuk membatalkan semua kasus sekarang. Jika ada orang lain yang ingin melakukannya, lanjutkan, suara positif saya akan dijamin)
Satu hal yang perlu diperhatikan adalah bahwa memang ada serangan pada pengaturan ini yang hanya dapat dikalahkan dengan perencanaan ke depan. Jika musuh dapat memutuskan digit berikutnya tanpa pemberitahuan, mereka dapat membunuh kita:
Contohnya adalah serangan 2 dari atas dengan strategi rinci berikut: siklus melalui kuning-> merah-> oranye terang-> ungu-> oranye tua memaksa putar balik. segera setelah belokan-u memaksa perubahan jalur dengan mengulang satu digit, tunggu saja sampai warna tidak menyisakan pilihan. Mulai dari awal. Jelas, jika kita mengetahui sebelumnya kapan perubahan jalur dijadwalkan, kita bisa beradaptasi kapan tepatnya untuk berbalik dan mengalahkan serangan ini.