Amuba berukuran besar lolos

Dec 01 2020

Sebagai perpanjangan dari pertanyaan @WhatsUp di sini , aturannya disertakan di bawah ini, dengan perbedaan berikut:

Di salah satu kotak, hiduplah seekor amuba (ditandai sebagai lingkaran pada gambar berikut).

Di beberapa kotak, terdapat amuba (ditandai dengan warna hijau / kuning pada gambar berikut).

Di grid, ada wilayah yang disebut "penjara" (dicat abu-abu pada gambar berikut).

Di sini "penjara" terdiri dari semua kotak kuning dan hijau.

  1. Jika kotak paling bawah kekuningan tidak ditempati, dapatkah amuba melarikan diri? Seberapa sulit?

  2. Malam sebelum pelarian mereka diluncurkan, sel kuning diisi dengan tahanan amuba baru (semua kuning dan hijau dianggap terisi), apa yang bisa mereka lakukan sekarang?

Referensi

Ada petak kotak yang tak terbatas.

Di salah satu kotak, hiduplah seekor amuba (ditandai sebagai lingkaran pada gambar berikut).

Amuba tidak dapat bergerak, tetapi mereka dapat melakukan tindakan uniknya: amuba dapat membelah dirinya menjadi dua amuba, yang identik dengan yang asli, dan masing-masing akan menempati kotak yang (secara ortogonal) berdekatan dengan kotak asli.

Karena setiap kotak hanya dapat menampung satu amuba, pemisahan hanya dapat terjadi jika amuba memiliki setidaknya dua kotak yang berdekatan kosong (jika ada lebih dari dua, maka ia dapat dengan bebas memilih kotak mana yang akan dipisahkan). Selain itu, dua amuba tidak boleh terpisah secara bersamaan, sehingga tidak terjadi konflik.

Di grid, ada wilayah yang disebut "penjara" (dicat abu-abu pada gambar berikut). Tujuannya adalah untuk membiarkan amuba lolos dari penjara, yaitu untuk mencapai status bahwa tidak ada amuba di dalam penjara.

Jawaban

8 PaulPanzer Dec 01 2020 at 09:59

Jawaban untuk Q2. Seperti yang ditunjukkan @Milo Brandt dalam komentar ke Q yang direferensikan, ada setengah invarian berikut:

Letakkan koordinat integer pada grid dengan (0,0) sebagai pusat persilangan. Berat persegi (n, m) sebesar$2^{-\lvert n \rvert - \lvert m \rvert}$. Kemudian orang dapat dengan mudah memverifikasi itu

1. berat seluruh papan (tak terbatas) adalah 9 (gambar lih)
dan
2. berat kotak yang ditempati oleh amuba tidak pernah turun.

Seperti berat seluruh salib $4\frac 1 2$ yang sama dengan berat komplemennya (tak terbatas), amuba tidak dapat melarikan diri dalam banyak gerakan yang tak terbatas.