Sebuah "permainan Markov"

Question

Saya menyebut game yang mirip dengan yang saya jelaskan di bawah ini sebagai game Markov. Saya hanya memilih satu atau lebih tepatnya rangkaian game 1 parameter. Tantangan terbukanya adalah mencari tahu pemain mana$\ 0\ $ atau $\ 1\ $ memiliki strategi kemenangan untuk setiap parameter yang diberikan $\ W.$

NOTASI $\ n\%2=0\ $ untuk $\ n\ $ bahkan, dan $\ n\%2=1\ $ untuk $\ n\ $ aneh.;

Membiarkan $ d(0)=J(0)=0.\ $ Untuk bilangan bulat positif arbitrer $\ n,\ $ pemain $\ n\%2\ $ memilih bilangan bulat positif $\ d(n)\le d(n-1)+1;\ $ kemudian $\ J(n)=J(n-1)+d(n).$

Saat pemain bersaing di pertandingan $\ M(W),\ $ dimana $\ W\ $ adalah bilangan bulat positif yang ditetapkan secara sewenang-wenang, lalu pemain yang mendapatkan persis $J(n)=W\ $ menang.

Membiarkan $\ \omega(W)=0\ $ jika pemain $0$ memiliki strategi kemenangan di $M(W);\ $ jika tidak biarkan $\ \omega(W)=1\ $ jika pemain $1$ memiliki strategi kemenangan di $M(W)$.

MASALAH:   Fungsi komputasi$\ \omega:\mathbb N\to\{0\ 1\}.$

Contohnya: $\ \omega(1)=1;\ \omega(2)=\omega(3)=0;\ \omega(4)=1, $ dll. Namun, $\ \omega(120)\ $ atau $\ \omega(5553)\ $ sedikit lebih sulit (dan tidak saya ketahui).

Answer 1

Jawabannya tidak banyak berubah dengan angka yang lebih besar.

Jawaban lengkapnya adalah $$ \omega(W)=\left\{ \begin{array}{ll} 1, & W\%5=1,4\\ 0, & W\%5=0,2,3 \end{array}\right. $$

Mari kita katakan posisi itu $(W-J,d)$ menang jika pemain $n\%2$ memiliki strategi kemenangan untuk permainan $M(W)$ pada gilirannya $n$ dengan $d(n)=d,J(n)=J$. Itu kalah jika tidak. Jelas, itu memang hanya bergantung pada perbedaannya$W-J$.

$(i,d)$ menang jika ada kekalahan $(j,f)$ st $j+f=i,f\le d+1$. Kami tertarik apakah$(W-1,1)$ menang.

Untuk ini, cukup dipertimbangkan saja $(i,d)$ dengan $d\le 3$.

Polanya terlihat seperti ini:

$ \begin{array}{ccc} - & - & -\\ + & + & +\\ + & + & +\\ - & + & +\\ + & + & +\\ - & - & -\\ \vdots & \vdots & \vdots \end{array} $

Untuk melihatnya, perhatikan:

• $(0,d)$ kalah untuk semua $d$, yaitu baris pertama diisi $-$'s
• jika $(i,d)$ menang, kalau begitu $(i,d+1)$ menang, yaitu di sebelah kanan $+$ selalu berbeda $+$

Answer 2

Kami sudah memiliki jawaban lengkap dari @JosephGordon yang membuktikan periodisitas $\ \omega,\ $ jangka waktunya menjadi 5. Joseph - terima kasih banyak!

Izinkan saya menulis solusi yang setidaknya bagi saya lebih mudah diikuti.

Ingat pemain itu $\ \omega(n)\ $ adalah orang yang memiliki strategi kemenangan untuk permainan Markov $\ M(n).$

Teorema Untuk setiap bilangan bulat positif$\ n\ $ dua properti berikut ini berlaku:

• Pemain $\ \omega(n)\ $ bisa memenangkan setiap pertandingan $\ M(n)\ $ dengan memilih semua jurus mereka sendiri sedemikian rupa $\ d(k)\le 3;$

• $\ \omega(n+5) = \omega(5).\ $

Bukti   Pemain$\ \omega(n)\ $, saat bermain game $\ M(n+5)\ $, Mampu mencapai posisi $\ n\ $ sambil memanfaatkan gerakan sedemikian rupa $\ d(k)\le 3\ $setiap waktu. Secara khusus,$\ d(t)\le 3\ $ kapan $\ J(t)=n.\ $ Jadi, sekarang kami hanya memiliki empat ekstensi permainan:

• $\ d(t+1)=4.\ $ Kemudian pemain $\ \omega(n)\ $ memainkan $\ d(t+2)=1\ $ dan menang (sejak $\ J(t+2)=n+5\ \text{and}\ t+2\equiv t\mod 2)$;

• $\ d(t+1)=3.\ $ Kemudian pemain $\ \omega(n)\ $ memainkan $\ d(t+2)=2\ $ dan menang;

• $\ d(t+1)=2.\ $ Kemudian pemain $\ \omega(n)\ $ memainkan $\ d(t+2)=3\ $ dan menang;

• $\ d(t+1)=1.\ $ Kemudian pemain $\ \omega(n)\ $ memainkan $\ d(t+2)=1;\ $ lalu pemain lain bermain $\ d(t+3)= 1$ atau $2\ $, dan pemain $\ \omega(n)\ $ memainkan $\ 2$ atau $1\ $ masing-masing, dan menang.

Argumen formal lainnya benar-benar rutin dan jelas. Akhir BUKTI.

Deskripsi numerik lengkap dari $\ \omega\ $ diberikan oleh teorema di atas dan inisial $5$ nilai:

$$ \omega(1)=1;\,\ \omega(2)=\omega(3)=0;\,\ \omega(4)=1, \,\ \omega(5)=0 $$

Contohnya, $\ \omega(5)=0\ $ karena J (1) = 1, maka pemain $0$ dapat memainkan d (2) = 1, yaitu J (2) = 2, kemudian - setelah digerakkan oleh pemain $0$ -- pemain $\ 0\ $ akan bermain $\ J(4)=5.$