Um “jogo Markov”

Question

Eu chamo jogos semelhantes ao que descrevo abaixo de jogos de Markov. Estou selecionando apenas esse, ou melhor, uma série de jogos de 1 parâmetro. O desafio aberto é descobrir qual dos jogadores$\ 0\ $ ou $\ 1\ $ tem uma estratégia vencedora para cada um dos parâmetros dados $\ W.$

NOTAÇÃO $\ n\%2=0\ $ para $\ n\ $ mesmo, e $\ n\%2=1\ $ para $\ n\ $ ímpar.;

Deixei $ d(0)=J(0)=0.\ $ Para número inteiro positivo arbitrário $\ n,\ $ jogador $\ n\%2\ $ seleciona um número inteiro positivo $\ d(n)\le d(n-1)+1;\ $ então $\ J(n)=J(n-1)+d(n).$

Quando os jogadores competem no jogo $\ M(W),\ $ Onde $\ W\ $ é um número inteiro positivo fixo arbitrariamente, então o jogador que obtém exatamente $J(n)=W\ $ vitórias.

Deixei $\ \omega(W)=0\ $ se jogador $0$ tem uma estratégia vencedora em $M(W);\ $ caso contrário, deixe $\ \omega(W)=1\ $ se jogador $1$ tem uma estratégia vencedora em $M(W)$.

PROBLEMA:   Função de computação$\ \omega:\mathbb N\to\{0\ 1\}.$

Por exemplo: $\ \omega(1)=1;\ \omega(2)=\omega(3)=0;\ \omega(4)=1, $ etc. No entanto, $\ \omega(120)\ $ ou $\ \omega(5553)\ $ é um pouco mais difícil (e desconhecido para mim).

Answer 1

A resposta não muda muito com números maiores.

A resposta completa é $$ \omega(W)=\left\{ \begin{array}{ll} 1, & W\%5=1,4\\ 0, & W\%5=0,2,3 \end{array}\right. $$

Vamos dizer que posição $(W-J,d)$ está ganhando se jogador $n\%2$ tem uma estratégia vencedora para o jogo $M(W)$ na vez dele $n$ com $d(n)=d,J(n)=J$. É perder de outra forma. Claramente, realmente depende apenas da diferença$W-J$.

$(i,d)$ está ganhando se existe perda $(j,f)$ st $j+f=i,f\le d+1$. Estamos interessados ​​em se$(W-1,1)$ está ganhando.

Para isso, basta considerar apenas $(i,d)$ com $d\le 3$.

O padrão é assim:

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

Para ver, observe:

• $(0,d)$ está perdendo para todos $d$, ou seja, a primeira linha é preenchida com $-$de
• E se $(i,d)$ está ganhando então $(i,d+1)$ está ganhando, ou seja, à direita de $+$ é sempre outro $+$

Answer 2

Já temos uma resposta completa de @JosephGordon que comprovou a periodicidade de $\ \omega,\ $ a duração do período sendo 5. Joseph - muito obrigado!

Deixe-me escrever uma solução que, pelo menos para mim, seja mais fácil de seguir.

Lembre-se daquele jogador $\ \omega(n)\ $ é aquele que tem a estratégia vencedora para o jogo Markov $\ M(n).$

Teorema para cada inteiro positivo$\ n\ $ as duas propriedades a seguir são válidas:

• Jogador $\ \omega(n)\ $ pode ganhar todos os jogos de $\ M(n)\ $ selecionando todos os seus próprios movimentos de forma que $\ d(k)\le 3;$

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

Proof   Player$\ \omega(n)\ $, ao jogar o jogo $\ M(n+5)\ $, é capaz de chegar à posição $\ n\ $ enquanto utiliza movimentos tais que $\ d(k)\le 3\ $cada vez. Em particular,$\ d(t)\le 3\ $ quando $\ J(t)=n.\ $ Assim, agora temos apenas quatro extensões do jogo:

• $\ d(t+1)=4.\ $ Então jogador $\ \omega(n)\ $ tocam $\ d(t+2)=1\ $ e ganha (desde $\ J(t+2)=n+5\ \text{and}\ t+2\equiv t\mod 2)$;

• $\ d(t+1)=3.\ $ Então jogador $\ \omega(n)\ $ tocam $\ d(t+2)=2\ $ e ganha;

• $\ d(t+1)=2.\ $ Então jogador $\ \omega(n)\ $ tocam $\ d(t+2)=3\ $ e ganha;

• $\ d(t+1)=1.\ $ Então jogador $\ \omega(n)\ $ tocam $\ d(t+2)=1;\ $ então o outro jogador joga $\ d(t+3)= 1$ ou $2\ $, e jogador $\ \omega(n)\ $ tocam $\ 2$ ou $1\ $ respectivamente, e vence.

O resto formal do argumento é totalmente rotineiro e óbvio. Fim da PROOF.

A descrição numérica completa de $\ \omega\ $ é dado pelo teorema acima e o inicial $5$ valores:

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

Por exemplo, $\ \omega(5)=0\ $ porque J (1) = 1, então jogador $0$ pode jogar d (2) = 1, ou seja, J (2) = 2, então - após uma jogada do jogador $0$ - jogador $\ 0\ $ vai jogar $\ J(4)=5.$