
> 
> 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).
> 
> 
> 



A "Markov game"
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 $+$


