What is the strategy to always win?

Question

Assuming we have a two player game consisting of the following:

The game starts with $p$ stones in one column and $q $ stones in another column. Players play alternately as follows: Pick a column and take as many stones as you want from that column. Or they take the same amount of stones from each column. The player wins when the other can no longer play, that is, whoever makes the move that has $0$ stones in each column wins the game. What is the strategy to always win?

"Resolution'':

Essentially you want to "trap" the opponent. To do so, WLOG let us make an example. $p=10$, $q=15$. If you go first, you can always guarantee a win. We will show taking both from the columns makes the first player loose. Take $5$ from each column. We are left with $5,10$. Obviously the other player wouldn't want to take a whole row, or else you can take the remaining row. So he/she must leave part of each row left, so he/she still has a chance. It basically boils down to who will take the last $1$ from the row. If the second player tries to "trap" the first player by taking $4$ out from the top, the first player can just take $8$ out from the bottom(note not $9$ because the second player will just do $1$ from each column). Then the second player must do one of the following: Take out $1$ from one of the column, take $2$ from the second column, or take $1$ from both, each of which "traps" the second player. This is similar if the second player takes out $2$ from the row. So the second player will proceed with a different step. Now say if the second player didn't do that. Say he/she took out $n$ stones, where $0<n<4$ and is odd. We have $5-n$ and $10-n$. Obviously, if the second player takes out one of these, the first player is again, trapped. So the second player will obviously play this move.

So now notice, this actually applies to the original case. If the first player didn't take out both from each column, then he/she can apply the same strategy to force the second player, and he/she gets the upper hand this time.

I was thinking of a way to always win. I've seen a similar problem, but the problem was something like giving the number of stones in each column. Can you generalize to something like that?

Answer 1

I've just become aware that this game is known as Whytoff's game, its solution having already been given by the Dutch mathematician Willem Whytoff in 1907. A connection with the so-called Whytoff sequences makes it possible to give a simpler description of the winning strategy than I gave here. Here's a brief description of the winning strategy, for the pile sizes for which it exists.

For convenience, let $\ s=\min(p,q)\ $, $\ \ell =\max(p,q)\ $, $\ \phi=\frac{1+\sqrt{5}}{2}\ $, the golden ratio, $\ a_n=\lfloor n\phi\rfloor\ $, the $\ n^\text{th}\ $ term of the lower Whytoff sequence, and $\ b_n=\lfloor n(\phi+1)\rfloor=a_n+n\ $ the corresponding term of the upper Whytoff sequence. A winning strategy exists if and only if $\ s\ne a_{\ell-s}\ $.

The sequences $\ \left\{a_n\right\}\ $ and $\ \left\{b_n\right\}\ $ are strictly increasing, and have the property that every positive integer $\ z\ $ belongs to exactly one of them. Let $\ t=\left\lceil\frac{z}{\phi}\right\rceil\ $, and $\ r=\left\lceil\frac{z}{\phi+1}\right\rceil\ $ . Then $\ t=\frac{z}{\phi}-\alpha\ $ and $\ r=$$\frac{z}{\phi+1}-\beta\ $, with $\ 0<\alpha,\beta<1\ $, so $\ \alpha+\beta=\frac{z}{\phi}+\frac{z}{\phi+1}-t-r=$$s-t-r\ $, an integer. But since $\ 0<\alpha,\beta<1\ $, the only way this can occur is if $\ \alpha+\beta=1\ $. Now, since $\ \frac{1}{\phi}+\frac{1}{\phi+1}=\alpha+\beta\ $, then $\ \alpha-\frac{1}{\phi}\ $ and $\ \beta-\frac{1}{\phi+1}\ $ have opposite signs. Neither of these quantities can be zero, because that would imply that $\ \phi=\frac{z-1}{t}\ $ or $\ \phi+1=\frac{z-1}{r}\ $, thus contradicting the irrationality of $\ \phi\ $. Therefore, exactly one of the two inequalities $\ \phi\alpha<1\ $ or $\ (\phi+1)\beta<1\ $ holds. In the first case, $\ z=a_t\ $, while in the second $\ z=b_r\ $.

• If $\ s>a_{\ell-s}\ $, then $\ \ell=b_{\ell-s}+\left(s- a_{\ell-s}\right)\ $, and a winning move is to take $\ s-a_{\ell-s}\ $ stones from both piles to leave piles of sizes $\ a_{\ell-s}\ $ and $\ b_{\ell-s}\ $.

• If $\ s<a_{\ell-s}\ $ then either $\ s=a_n\ $, where $\ n=\left\lceil\frac{s}{\phi}\right\rceil\ $, or $\ s=b_m\ $, where $\ m=\left\lceil\frac{s}{\phi+1}\right\rceil\ $.

  • In the first case, $\ \ell> b_n\ $, and a winning move is to take $\ \ell-b_n\ $ stones from the pile of size $\ \ell\ $ to leave piles of sizes $\ a_n\ $ and $\ b_n\ $.
  • In the second case, $\ \ell\ge s> a_m\ $, and a winning move is to take $\ \ell-a_m\ $ stones from the pile of size $\ \ell\ $ to leave piles of sizes $\ a_m\ $ and $\ b_m\ $.

• If $\ s=a_{\ell-s}\ $, then there is no winning move:

  • Removing $\ k\ $ stones from both piles will leave piles of sizes $\ s-k\ $ and $\ \ell-k\ $, and $\ s-k\ne a_{(\ell-k)-(s-k)}\ $.
  • Removing $\ k\ $ from the smaller pile will leave piles of sizes $\ s-k\ $ and $\ \ell\ $, with $\ s-k < s<a_{\ell-(s-k)}\ $.
  • Removing $\ k\ $ from the larger pile will leave piles of sizes $\ s\ $ and $\ \ell-k\ $. If $\ \ell-k>s\ $, then $\ s=a_{\ell-k}> a_{\ell-k-s}\ $, while if $\ \ell-k\le s\ $, then $\ \ell-k \ne a_{s-(\ell-k)}\ $, because this would imply that $\ s=b_{s-(\ell-k)}\ $, which is impossible.