A "Markov game"

Question

I call games similar to the one I describe below to be Markov games. I am selecting just that one or rather a 1-parameter series of games. The open challenge is to find out which of the players $\ 0\ $ or $\ 1\ $ has a winning strategy for each of the given parameter $\ W.$

NOTATION $\ n\%2=0\ $ for $\ n\ $ even, and $\ n\%2=1\ $ for $\ n\ $ odd.;

Let $ d(0)=J(0)=0.\ $ For arbitrary positive integer $\ n,\ $ player $\ n\%2\ $ selects a positive integer $\ d(n)\le d(n-1)+1;\ $ then $\ J(n)=J(n-1)+d(n).$

When players compete at game $\ M(W),\ $ where $\ W\ $ is an arbitrarily fixed positive integer, then the player that gets exactly $J(n)=W\ $ wins.

Let $\ \omega(W)=0\ $ if player $0$ has a winning strategy at $M(W);\ $ otherwise let $\ \omega(W)=1\ $ if player $1$ has a winning strategy at $M(W)$.

PROBLEM:   Compute function $\ \omega:\mathbb N\to\{0\ 1\}.$

For instance: $\ \omega(1)=1;\ \omega(2)=\omega(3)=0;\ \omega(4)=1, $ etc.   However, $\ \omega(120)\ $ or $\ \omega(5553)\ $ is a bit harder (and unknown to me).

Answer 1

The answer doesn't change much with greater numbers.

The full answer is $$ \omega(W)=\left\{ \begin{array}{ll} 1, & W\%5=1,4\\ 0, & W\%5=0,2,3 \end{array}\right. $$

Let us say that position $(W-J,d)$ is winning if player $n\%2$ has a winning strategy for game $M(W)$ on his turn $n$ with $d(n)=d,J(n)=J$. It is losing otherwise. Clearly, it indeed depends only on the difference $W-J$.

$(i,d)$ is winning iff there exists losing $(j,f)$ s.t. $j+f=i,f\le d+1$. We are interested in whether $(W-1,1)$ is winning.

For this it suffices to consider only $(i,d)$ with $d\le 3$.

The pattern looks like this:

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

To see it, notice:

• $(0,d)$ is losing for all $d$, i.e. first row is filled with $-$'s
• if $(i,d)$ is winning, then $(i,d+1)$ is winning, i.e. to the right of $+$ is always another $+$

Answer 2

We already have a full answer from @JosephGordon who proved periodicity of $\ \omega,\ $ the length of the period being 5. Joseph -- many thanks!

Let me write a solution that at least to me is easier to follow.

Remember that player $\ \omega(n)\ $ is the one who has the winning strategy for Markov game $\ M(n).$

Theorem For every positive integer $\ n\ $ the following two properties hold:

• Player $\ \omega(n)\ $ can win every game of $\ M(n)\ $ by selecting all of their own moves such that $\ d(k)\le 3;$

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

Proof   Player $\ \omega(n)\ $, when playing game $\ M(n+5)\ $, is able to arrive at position $\ n\ $ while utilizing moves such that $\ d(k)\le 3\ $ each time. In particular, $\ d(t)\le 3\ $ when $\ J(t)=n.\ $ Thus, now we have only four extensions of the game:

• $\ d(t+1)=4.\ $ Then player $\ \omega(n)\ $ plays $\ d(t+2)=1\ $ and wins (since $\ J(t+2)=n+5\ \text{and}\ t+2\equiv t\mod 2)$;

• $\ d(t+1)=3.\ $ Then player $\ \omega(n)\ $ plays $\ d(t+2)=2\ $ and wins;

• $\ d(t+1)=2.\ $ Then player $\ \omega(n)\ $ plays $\ d(t+2)=3\ $ and wins;

• $\ d(t+1)=1.\ $ Then player $\ \omega(n)\ $ plays $\ d(t+2)=1;\ $ then the other player plays $\ d(t+3)= 1$ or $2\ $, and player $\ \omega(n)\ $ plays $\ 2$ or $1\ $ respectively, and wins.

The formal rest of the argument is totally routine and obvious. End of PROOF.

The complete numerical description of $\ \omega\ $ is given by the above theorem and the initial $5$ values:

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

For instance, $\ \omega(5)=0\ $ because J(1)=1, then player $0$ can play d(2)=1, i.e. J(2)=2, then -- after a move by player $0$ -- player $\ 0\ $ will play $\ J(4)=5.$