3
$\begingroup$

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

$\endgroup$
2
  • 3
    $\begingroup$ Did you try to draw the oriented graph of the game? Vertices correspond to possible states (here couples (d,J)) and there is an arrow from a vertice to another whenever a move gets you from the first to the second. Then one colors some obvious winning states in some color, and deduces some losing states (those from which all outgoing edges go to winning states), and recursively colors each state as losing or winning. $\endgroup$ Oct 19, 2020 at 6:07
  • $\begingroup$ @BenoîtKloeckner, frankly speaking, I've attached the name Markov based on 1.memory reached just one step back; 2. The whole series, for all W together, exhibits translation invariance. Of course, we should consider a 2-parameter extension, where in addition to W, we have also d(0) as an arbitrary. non-negative integer. (I guess that your suggestion and the two moments I have mentioned are strongly related). $\endgroup$
    – Wlod AA
    Oct 19, 2020 at 6:21

2 Answers 2

3
$\begingroup$

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 $+$
$\endgroup$
1
  • $\begingroup$ Period 5? -- Yes, it's great! And, now it is so easy that even I can write down a solution too. $\endgroup$
    – Wlod AA
    Oct 19, 2020 at 16:50
0
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.