2
$\begingroup$

Consider the following game:

Two players alternately take one or two stones from a pile of stones. The objective of each player is to take, in total, an even number of stones. Suppose that in the beginning the pile has an odd number of stones $n$, so that one of the players wins and another loses.

I would like to know, what player has the winning strategy here.

If $n = 1$ the second player is the one, who wins, as the first player takes the only stone and loses immediately.

If $n = 3$ the first player wins by taking two stones and reducing the game $n = 1$ on second player's turn.

However, I have no idea how to get the solution for an arbitrary odd $n$.

This question (not all of it, however, but only the quoted "rules of the game") was initially posted by @kris, but got deleted as a PSQ. However, this question seemed too interesting to ignore so I reposted it (with added context).

$\endgroup$
4
  • $\begingroup$ Not sure I follow your logic for $n=5$. Say $A$ takes $1$ initially, leaving four, and $B$ then takes $1$, leaving $3$. Now $A$ is not in the $n=3$ position because $A$ has already taken $1$. If $A$ takes $1$ (so $2$ in total) that leaves $B$ with two, so $B$ takes $1$ and wins. If $A$ takes $2$ (so $3$ in total) that leaves $B$ with one, so $B$ takes that one and wins. Or have I misunderstood? $\endgroup$
    – lulu
    May 18, 2020 at 20:33
  • $\begingroup$ @lulu, it seems, that I have made a mistake there... $\endgroup$ May 18, 2020 at 20:34
  • $\begingroup$ My point, to be sure, is that it is not enough to say that $n=3$ is a winning state since it depends on whether the player has reached that via an even or an odd number of removals. $\endgroup$
    – lulu
    May 18, 2020 at 20:34
  • $\begingroup$ I suggest working out $5,7,9$. Maybe it is as simple as alternating between advantage $A$ and advantage $B$. After all, if $n$ is a losing state (if we are in (Even, Even)) then $n+2$ is a winning state from (Even, Even) since taking $2$ leaves your opponent in $n$ (Even, Even). $\endgroup$
    – lulu
    May 18, 2020 at 20:34

1 Answer 1

4
$\begingroup$

Label a state (where it is your turn) by $(n,m)$ where $n$ is the number of stones in the pile and $m$ is the parity ($0= even$, $1=odd$) of the number of stones you have. Note that the total number of stones is odd, so if $n$ is even your opponent's number of stones has the opposite parity to yours, while if $n$ is odd your opponent's number has the same parity as yours. Thus $(0,0)$, $(1,1)$ are winning positions and $(0,1)$ and $(1,0)$ are losing.

By induction, I find the following:

$(4k,0)$ is a win, $(4k,1)$ is a loss

$(4k+1,0)$ is a loss, $(4k+1,1)$ is a win

$(4k+2,0)$ is a win, $(4k+2,1)$ is a win.

$(4k+3,0)$ is a win, $(4k+3,1)$ is a loss.

Thus from $(4k,0)$ (if $k>0$) you take one stone, leaving your opponent in the losing position $(4k-1,1)$. From $(4k,1)$ you have a loss, as you must leave your opponent with either $(4k-1,0)$ or $(4k-2,1)$, both wins. Similarly in other cases.

$\endgroup$
1
  • $\begingroup$ Should it be $(4k-2,0)$ at the end? It is still a win for the other player. $\endgroup$ Jun 4, 2022 at 18:36

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .