13
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ In other words "X is a multiple of coins on the other pile". If one of the pile becomes empty the game is over. $\endgroup$ – user60166 May 8 at 10:51
  • $\begingroup$ Sorry, I removed my comment. I didn't see the game ended at the first empty pile, and had normal Nim games in mind where all piles become empty. $\endgroup$ – Jaap Scherphuis May 8 at 10:54
  • $\begingroup$ This post has been locked, as it is taken from an ongoing contest. For more information see our policy on Questions from Ongoing Contests. It comes from the Code Chef May Long Challenge, ending 13-May at 15:00 IST. I don't plan to keep tabs on this question until then, so if OP (or someone else) is interested enough in having it unlocked, please flag it for moderator attention once the contest has ended. $\endgroup$ – Rubio May 8 at 14:59
11
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ fixed some wordings for you, hope you don't mind... nice answer, +1! $\endgroup$ – Omega Krypton May 8 at 13:22
  • $\begingroup$ Thanks @OmegaKrypton. I was just revising things too, but completely failed to reread the first line. Thanks for catching that editing error. $\endgroup$ – Jaap Scherphuis May 8 at 13:25
  • $\begingroup$ Alright, I don't know how this forum works but I guess this post was hidden for a time? We agree on everything in the beginning and as far what would decide the winning player. Beyond that you determined how the first player should play, and I'll admit your continued fraction idea is a little beyond me. I think I see that it works but that isn't the same as understanding why you thought to do that in the first place. Intuitively, why would you start thinking about M/N? $\endgroup$ – Dark Thunder May 21 at 12:58
  • $\begingroup$ @DarkThunder Yes, I answered before it was realised that the question came from a competition, so when the question was locked, my answer was (soft)deleted. For some reason they didn't undelete it when the question was unlocked, and I had to ask a moderator to do so. I'm sorry you got caught in the middle. As for the continued fraction, I did not come up with it myself. I googled for Euclidean nim and soon found that this game is called Euclid. After seeing the answer involved continued fractions and phi, I figured out the proof myself. $\endgroup$ – Jaap Scherphuis May 21 at 14:20
0
$\begingroup$

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.![enter image description here

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. enter image description here

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

$\endgroup$
  • $\begingroup$ The code is wrong. If for instance there are 7+2 coins, B wins. A can only leave 7+1, 6+2 or 5+2. With the first two B wins. So A leaves 5+2. From 5+2, likewise, B can only leave 5+1, 4+2 or 3+2. With the first two, A wins, so B leaves 3+2. From 3+2, whatever A leaves, 3+1, 2+2, 1+2, B wins. So B wins from 7+2. But your program claims A wins. $\endgroup$ – Florian F May 20 at 20:54
  • $\begingroup$ Are we reading the rules differently? Starting at [7,2] I have the first move being A taking 4, making it [3,2]. Player 2 must take 2 from 3 (no choice) leaving [1,2] and then player A can win by taking 2 from 2. $\endgroup$ – Dark Thunder May 20 at 22:02
  • $\begingroup$ Yes, we read the rules differently and ... well ... I am not on the right side. I misread that you can remove a number of coins that divides the size of the other stack. In fact you can remove a number of coins that is a multiple of the other stack. So no more objection my honour. - PS: note that the reversed rules also result in an interesting game. $\endgroup$ – Florian F May 21 at 12:46
  • $\begingroup$ I agree! Without thinking about it too hard, that seems far more intimidating. Your rule would be "take a number of coins from one pile such that it is a divisor of the other pile"? My gut feeling is that would require an insane program to keep track of all the possibilities. $\endgroup$ – Dark Thunder May 21 at 13:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy