Picking coins from two piles

Question

It is a variation of the game of Nim.

The rules are :

The game is played with two piles of coins. Initially, the first pile contains N coins and the second one contains M coins.

There are two players A and B. They alternate turns.

A plays first. On each turn, the current player must choose one pile and remove a positive number of coins (not exceeding the current number of coins on that pile) from it.

It is only allowed to remove X coins from a pile if the number of coins in the other pile divides X.

The player that takes the last coin from any pile wins.

Both players play optimally.

For a given N and M, devise a procedure to find the winner of the game

Answer 1

Let $N$ be the smaller pile, $M$ the larger. The first player wins if $\frac{M}{N}>\phi$.

Proof:

If $N<M<2N$ then your move is forced. There is only one possible move, namely to go from $(N,M)$ to $(N,M-N)$. This move will also not immediately win, because $N<M$.

If $M\ge2N$, then there are several moves possible. Write $M=qN+r$ with $q>1$ and $0\le r<N$, i.e. $r$ is the remainder when you divide $M$ by $N$.
In this case you have a range of moves possible, namely taking any multiple of $N$ from $1N$ to $qN$. Note however that if you do not take $qN$ to leave $(N,r)$, then your opponent can do so.

Either leaving $(N,r)$ is a winning move or a losing move. If it is a losing move, then you can take just $(q-1)N$ to leave $(N,r+N)$ after which your opponent is forced to leave $(N,r)$ and lose.

It remains now to be seen which you move should do - leave $(N,r)$ or $(N,r+N)$. What you certainly don't want to happen is that your opponent has a choice in his next move. If he had a choice, then he could choose whether or not to let you win. Unfortunately it is possible that both options give the opponent no choice, and then you would have to look ahead further.

Consider the fraction $\frac{M}{N}$. If there was a forced non-final move (i.e. $N<M<2N$) then it is like rewriting the fraction as $1+\frac{M-N}{N}$. Since the other pile has become the largest, we actually get $1+\frac{1}{\frac{M'}{N'}}$, where $M'$ and $N'$ are the new largest and smallest piles. With a series of forced moves, we get a continued fraction with a series of ones, like this: $$1+\frac{1}{1+\frac{1}{1+\frac{1}{\frac{M'}{N'}}}}$$
We want the first non-forced move to be ours, so that we can win. So we want the continued fraction of $\frac{M}{N}$ to have an even number of ones (possibly zero) before the first larger number. A continued fraction with only ones in it is the continued fraction for $\phi=\frac{1+\sqrt{5}}{2}$. A larger number at any point would make the result larger or smaller depending on whether it occurs at an odd or even spot in the series. For the first player to win it therefore means that we need $\frac{M}{N}>\phi$.

If it is your turn, and you actually have to decide between leaving $(N,r)$ or $(N,r+N)$, then you could compare their fractions $\frac{N}{r}$ and $\frac{r+N}{N}$ to $\phi$. However, one will be bigger than $\phi$ and the other smaller, so instead of comparing them to $\phi$ you can just compare them to each other. You want to leave the position which is smaller, because that will be a losing position for the next player. So if $\frac{N}{r}>\frac{r+N}{N}$ then don't take the maximal amount, otherwise do take all you can.

Answer 2

If anyone thinks answering this question would be disruptive to the contest (even though it closed last week) let me know and I, or somebody, will take this down.

Important note: according to the rules, our program need not know the specifics of the game, it just declares the winner assuming perfect play. Another thing that might make understanding the puzzle easier: Every time a player takes a turn, they will always be removing coins from the larger pile, in an amount that is some multiple of the smaller pile. This means there are plenty of occasions where the current player has no choice in the matter and makes what I call a "forced" move.

So let's build out an example where one pile has 5 coins

Any time we have N dividing into M, we know the 1st player (or current player) would win in a single move. From there, let us assume that we have (through some process) solved for all M < N. Each case will either predict the 1st player winning or the second. The next block of cases, where N < M < 2N, we know the active player has one option and must make a forced move. So the case [5,6] will have to become [5,1], it's just moving 5 steps up on our chart. We just have to flip the prediction for who would win, because there is one more turn involved. Moving beyond where M > 2N, the current player does have a choice. So [5,11] can become [5,6] or [5,1]. Since we know they have opposite predictions, we know the active player can always choose one in his favor.

The real lesson from this is:

Any time a player can make a choice, they can win the game!

Which has big consequences

We never need create a program that must branch out to solve for possible combinations. So far as I can tell, we do still need to solve for all of those "forced" moves, though. Here is my Excel VBA code verbatim. It's a picture... so sorry if you wanted to copy the text. It's not that complicated, anyway.

It's funny that the only tag this question had was "combinatorics" and it doesn't even need them.