„Gra Markowa”
Gry podobne do tej, którą opisuję poniżej, nazywam grami Markowa. Wybieram tylko tę jedną, a raczej serię gier z 1 parametrem. Otwartym wyzwaniem jest ustalenie, który z graczy$\ 0\ $ lub $\ 1\ $ ma zwycięską strategię dla każdego z podanych parametrów $\ W.$
NOTACJA $\ n\%2=0\ $ dla $\ n\ $ nawet i $\ n\%2=1\ $ dla $\ n\ $ dziwny.;
Pozwolić $ d(0)=J(0)=0.\ $ Dla dowolnej dodatniej liczby całkowitej $\ n,\ $ gracz $\ n\%2\ $ wybiera dodatnią liczbę całkowitą $\ d(n)\le d(n-1)+1;\ $ następnie $\ J(n)=J(n-1)+d(n).$
Gdy gracze rywalizują w grze $\ M(W),\ $ gdzie $\ W\ $ jest dowolnie ustaloną liczbą całkowitą dodatnią, to gracz, który otrzyma dokładnie $J(n)=W\ $ wygrywa.
Pozwolić $\ \omega(W)=0\ $ jeśli gracz $0$ ma zwycięską strategię na $M(W);\ $ inaczej niech $\ \omega(W)=1\ $ jeśli gracz $1$ ma zwycięską strategię na $M(W)$.
PROBLEM: funkcja obliczeniowa$\ \omega:\mathbb N\to\{0\ 1\}.$
Na przykład: $\ \omega(1)=1;\ \omega(2)=\omega(3)=0;\ \omega(4)=1, $ itd. Jednak $\ \omega(120)\ $ lub $\ \omega(5553)\ $ jest nieco trudniejsze (i mi nieznane).
Odpowiedzi
Przy większych liczbach odpowiedź niewiele się zmienia.
Pełna odpowiedź brzmi $$ \omega(W)=\left\{ \begin{array}{ll} 1, & W\%5=1,4\\ 0, & W\%5=0,2,3 \end{array}\right. $$
Powiedzmy to stanowisko $(W-J,d)$ wygrywa, jeśli gracz $n\%2$ ma zwycięską strategię gry $M(W)$ na jego kolej $n$ z $d(n)=d,J(n)=J$. Inaczej przegrywa. Oczywiście, to rzeczywiście zależy tylko od różnicy$W-J$.
$(i,d)$ wygrywa, gdy istnieje przegrywa $(j,f)$ św $j+f=i,f\le d+1$. Interesuje nas, czy$(W-1,1)$ wygrywa.
W tym celu wystarczy tylko rozważyć $(i,d)$ z $d\le 3$.
Wzór wygląda następująco:
$ \begin{array}{ccc} - & - & -\\ + & + & +\\ + & + & +\\ - & + & +\\ + & + & +\\ - & - & -\\ \vdots & \vdots & \vdots \end{array} $
Aby to zobaczyć, zwróć uwagę:
- $(0,d)$ przegrywa dla wszystkich $d$, czyli pierwszy wiersz jest wypełniony $-$jest
- Jeśli $(i,d)$ wygrywa więc $(i,d+1)$ wygrywa, tj. na prawo od $+$ jest zawsze inny $+$
Mamy już pełną odpowiedź od @JosephGordon, który udowodnił okresowość $\ \omega,\ $ długość tego okresu wynosi 5. Józef - wielkie dzięki!
Napiszę rozwiązanie, które przynajmniej dla mnie jest łatwiejsze do naśladowania.
Zapamiętaj tego gracza $\ \omega(n)\ $ jest tym, który ma zwycięską strategię w grze Markov $\ M(n).$
Twierdzenie Dla każdej dodatniej liczby całkowitej$\ n\ $ zachowane są następujące dwie właściwości:
Gracz $\ \omega(n)\ $ może wygrać każdą grę $\ M(n)\ $ wybierając wszystkie własne ruchy, tak że $\ d(k)\le 3;$
$\ \omega(n+5) = \omega(5).\ $
Proof Player$\ \omega(n)\ $podczas gry $\ M(n+5)\ $, jest w stanie dotrzeć na pozycję $\ n\ $ wykorzystując takie ruchy $\ d(k)\le 3\ $za każdym razem. W szczególności,$\ d(t)\le 3\ $ kiedy $\ J(t)=n.\ $ Tak więc teraz mamy tylko cztery rozszerzenia gry:
$\ d(t+1)=4.\ $ Następnie gracz $\ \omega(n)\ $ gra $\ d(t+2)=1\ $ i wygrywa (od $\ J(t+2)=n+5\ \text{and}\ t+2\equiv t\mod 2)$;
$\ d(t+1)=3.\ $ Następnie gracz $\ \omega(n)\ $ gra $\ d(t+2)=2\ $ i wygrywa;
$\ d(t+1)=2.\ $ Następnie gracz $\ \omega(n)\ $ gra $\ d(t+2)=3\ $ i wygrywa;
$\ d(t+1)=1.\ $ Następnie gracz $\ \omega(n)\ $ gra $\ d(t+2)=1;\ $ wtedy inny gracz gra $\ d(t+3)= 1$ lub $2\ $i odtwarzacz $\ \omega(n)\ $ gra $\ 2$ lub $1\ $ odpowiednio i wygrywa.
Formalna reszta argumentacji jest całkowicie rutynowa i oczywista. Koniec DOWODU.
Pełny opis liczbowy $\ \omega\ $ wynika z powyższego twierdzenia i inicjału $5$ wartości:
$$ \omega(1)=1;\,\ \omega(2)=\omega(3)=0;\,\ \omega(4)=1, \,\ \omega(5)=0 $$
Na przykład, $\ \omega(5)=0\ $ ponieważ J (1) = 1, to gracz $0$ może zagrać d (2) = 1, czyli J (2) = 2, a następnie - po ruchu gracza $0$ -- gracz $\ 0\ $ zagrasz $\ J(4)=5.$