Un «jeu de Markov»

Question

J'appelle des jeux similaires à celui que je décris ci-dessous des jeux de Markov. Je sélectionne juste celui-là ou plutôt une série de jeux à 1 paramètre. Le défi ouvert est de savoir lequel des joueurs$\ 0\ $ ou $\ 1\ $ a une stratégie gagnante pour chacun des paramètres donnés $\ W.$

NOTATION $\ n\%2=0\ $ pour $\ n\ $ même, et $\ n\%2=1\ $ pour $\ n\ $ impair.;

Laisser $ d(0)=J(0)=0.\ $ Pour un entier positif arbitraire $\ n,\ $ joueur $\ n\%2\ $ sélectionne un entier positif $\ d(n)\le d(n-1)+1;\ $ puis $\ J(n)=J(n-1)+d(n).$

Quand les joueurs s'affrontent au jeu $\ M(W),\ $ où $\ W\ $ est un entier positif arbitrairement fixé, alors le joueur qui obtient exactement $J(n)=W\ $ gagne.

Laisser $\ \omega(W)=0\ $ si joueur $0$ a une stratégie gagnante à $M(W);\ $ sinon laissez $\ \omega(W)=1\ $ si joueur $1$ a une stratégie gagnante à $M(W)$.

PROBLÈME:   fonction de calcul$\ \omega:\mathbb N\to\{0\ 1\}.$

Par exemple: $\ \omega(1)=1;\ \omega(2)=\omega(3)=0;\ \omega(4)=1, $ etc. Cependant, $\ \omega(120)\ $ ou $\ \omega(5553)\ $ est un peu plus difficile (et inconnu de moi).

Answer 1

La réponse ne change pas beaucoup avec un plus grand nombre.

La réponse complète est $$ \omega(W)=\left\{ \begin{array}{ll} 1, & W\%5=1,4\\ 0, & W\%5=0,2,3 \end{array}\right. $$

Disons cette position $(W-J,d)$ gagne si le joueur $n\%2$ a une stratégie gagnante pour le jeu $M(W)$ à son tour $n$ avec $d(n)=d,J(n)=J$. Il perd autrement. Clairement, cela ne dépend en effet que de la différence$W-J$.

$(i,d)$ est en train de gagner ssi il existe de perdre $(j,f)$ st $j+f=i,f\le d+1$. Nous sommes intéressés à savoir si$(W-1,1)$ gagne.

Pour cela, il suffit de considérer uniquement $(i,d)$ avec $d\le 3$.

Le motif ressemble à ceci:

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

Pour le voir, remarquez:

• $(0,d)$ perd pour tous $d$, c'est-à-dire que la première ligne est remplie avec $-$de
• si $(i,d)$ gagne, alors $(i,d+1)$ est gagnant, c'est-à-dire à droite de $+$ est toujours un autre $+$

Answer 2

Nous avons déjà une réponse complète de @JosephGordon qui a prouvé la périodicité de $\ \omega,\ $ la durée de la période étant de 5. Joseph - merci beaucoup!

Permettez-moi d'écrire une solution qui, du moins pour moi, est plus facile à suivre.

Souviens-toi de ce joueur $\ \omega(n)\ $ est celui qui a la stratégie gagnante pour le jeu Markov $\ M(n).$

Théorème Pour chaque entier positif$\ n\ $ les deux propriétés suivantes sont valables:

• Joueur $\ \omega(n)\ $ peut gagner chaque partie de $\ M(n)\ $ en sélectionnant tous leurs propres coups de telle sorte que $\ d(k)\le 3;$

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

  Joueur de preuve$\ \omega(n)\ $, lors du jeu $\ M(n+5)\ $, est capable d'arriver à la position $\ n\ $ tout en utilisant des mouvements tels que $\ d(k)\le 3\ $chaque fois. En particulier,$\ d(t)\le 3\ $ quand $\ J(t)=n.\ $ Ainsi, nous n'avons plus que quatre extensions du jeu:

• $\ d(t+1)=4.\ $ Puis joueur $\ \omega(n)\ $ pièces $\ d(t+2)=1\ $ et gagne (depuis $\ J(t+2)=n+5\ \text{and}\ t+2\equiv t\mod 2)$;

• $\ d(t+1)=3.\ $ Puis joueur $\ \omega(n)\ $ pièces $\ d(t+2)=2\ $ et gagne;

• $\ d(t+1)=2.\ $ Puis joueur $\ \omega(n)\ $ pièces $\ d(t+2)=3\ $ et gagne;

• $\ d(t+1)=1.\ $ Puis joueur $\ \omega(n)\ $ pièces $\ d(t+2)=1;\ $ puis l'autre joueur joue $\ d(t+3)= 1$ ou $2\ $et joueur $\ \omega(n)\ $ pièces $\ 2$ ou $1\ $ respectivement, et gagne.

Le reste formel de l'argument est totalement routinier et évident. Fin de PREUVE.

La description numérique complète de $\ \omega\ $ est donné par le théorème ci-dessus et l'initiale $5$ valeurs:

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

Par exemple, $\ \omega(5)=0\ $ parce que J (1) = 1, alors joueur $0$ peut jouer d (2) = 1, soit J (2) = 2, puis - après un coup du joueur $0$ - joueur $\ 0\ $ jouera $\ J(4)=5.$