12
$\begingroup$

Alice and Bob play a game with two stacks of fluffy, golden pancakes, of sizes $p$ and $q$. They alternate turns, with Alice starting.

On their turn, a player must eat some number of pancakes from the larger stack. The number they eat must be a multiple of the size of the smaller stack. Since the bottom pancake of each stack is soggy, the first player to finish a stack loses.

For example, if the stacks were sized $5$ and $17$, then the current player can eat either $5,10$ or $15$ pancakes from the large stack.

For which values of $p$ and $q$ does Alice have a winning strategy?

Source: Mathematical Puzzles: A Connoisseur's Collection, Peter Winkler.

$\endgroup$
  • 9
    $\begingroup$ None, because that is a lot of pancakes, and she is going to be sick by the end no matter what. $\endgroup$ – Aggie Kidd Jul 8 '15 at 1:51
  • $\begingroup$ Do I understand correctly: Does it mean that when Alice eats 15 from the second (larger stack), then there are stacks 5 and 2, so Bob has to eat 2 or 4 from the first stack? $\endgroup$ – Voitcus Jul 8 '15 at 3:52
  • $\begingroup$ I hope the pancakes aren't made from real gold ;). $\endgroup$ – Bojidar Marinov Jul 8 '15 at 10:05
  • 1
    $\begingroup$ In next weeks episode, Alice and Bob go to hospital. (interesting puzzle, tho) $\endgroup$ – AJFaraday Jul 8 '15 at 10:11
  • 1
    $\begingroup$ @AJFaraday Well, after this puzzle is solved, nothing can stop you from making the "next episode" :) $\endgroup$ – Bojidar Marinov Jul 8 '15 at 14:03
13
$\begingroup$

What a beautiful problem! The winning positions (for Bob, the player who just moved) are those where the stack sizes are within a factor of the golden ratio $\phi$, i.e. the $(p,q)$ with $$1/\phi < q/p < \phi.$$ So, the winning strategy is to make the stacks as even as possible to keep this invariant true after your move.

Say that $p\leq q$. The legal moves result in positions of the form $(p,q')$. This is in the band of winning positions whenever $q' \in (p/\phi,p \phi)$ an interval whose length is exactly $p$.

Since the possible $q'$ are spaced $p$ apart, exactly one such $q'$ lies in the band. Then, $(p,q')$ is a winning move unless it is $(p,q)$ itself in the band, since we must have $q'<q$. We've shown that there's a move to a winning position exactly when we're not a winning position, which inductively proves that these are the winning positions.

I found this solution by writing code to find the winning positions, and noticing the band pattern and suspecting the golden ratio.

$\endgroup$
  • $\begingroup$ Two things I'm unclear on: 1. If ($q' < p$), how do we know whether this new position will be in or out of the winning band? 2. As far as I can see you've just proven that you stay inside the band, not that this ultimately leads to a winning position. $\endgroup$ – Ben Aaronson Jul 8 '15 at 12:26
  • $\begingroup$ This really takes a lot to get my head around and much maths (as you may have seen from deleted comments somehow). I think the key thing of this proof is that if you are in the band you can only go outside of it and if you are outside of it you can always get inside. You can then be sure since the total number of pancakes is reducing you will eventually get to (1,1) if you've not had a loss before that (from a (k,k)). Which is the base win position after your move. $\endgroup$ – Chris Jul 8 '15 at 15:08
  • $\begingroup$ The reason it's the golden ratio is because of something to do with the Euclidean algorithm, and how the possible sequence of moves is actually fixed. $\endgroup$ – Joe Z. Jul 8 '15 at 18:44
  • $\begingroup$ This reminds me of Wythoff's Nim/Wythoff's Game wherein $\phi$ and $1/\phi$ appear but not quite in the same way. $\endgroup$ – Mark S. Feb 27 '16 at 4:14
3
$\begingroup$

This is Nim in disguise because it is an impartial game. $(1,1)$ is a P position, so $(1,n)$ is N for $n \ge 2$. $(k,k)$ is P. $(2,3)$ is P. I suspect a relation with the Fibonacci series-find it. That is a wonderful book.

$\endgroup$
  • $\begingroup$ (1,3) is an N position, the winning move being to (1,1) $\endgroup$ – Mike Earnest Jul 8 '15 at 3:24
  • $\begingroup$ @MikeEarnest: Oops. Fixed. Thanks. $\endgroup$ – Ross Millikan Jul 8 '15 at 3:28
  • $\begingroup$ you can go further and say (k,nk) is N (N means winning position when its your turn, right?) because you can reduce to (k,k) which is a losing position (must eat k). $\endgroup$ – Chris Jul 8 '15 at 14:51
  • $\begingroup$ @Chris: That is correct. $\endgroup$ – Ross Millikan Jul 8 '15 at 15:06
1
$\begingroup$

Without loss of generality, assume the larger stack is of size $q$. Here's a non-constructive partial result:

If $q > 2p$, Alice wins.

I'll refer to the player whose turn it is as the "current player".

Let $q=np+r$, where $r$ is the remainder of $\frac{q}{p}$. Since $q>2p$, $n\ge2$. Eventually the game will reach the state $(r,p)$: players will take multiples of $p$ from the stack that is currently of size $q$ until that stack is smaller than $p$. At that point, the size of that stack will be $r$, and the other stack will be $p$, with $r<p$.

Since a tie is not possible, either the current player in the state $(r,p)$ can force a win, or the other player can. Alice can control whether she is the current player in the state $(r,p)$.

If the current player wins at $(r,p)$, Alice should take $(n-1)p$ pancakes from the $q$-stack, making the state $(p,p+r)$. She can always do this, since $n\ge2$. Bob's only move in that state is to take $p$ pancakes from the $p+r$ stack, making the state $(r,p)$ and Alice the current player. Thus, Alice wins.

If the current player loses at $(r,p)$, Alice should take $np$ pancakes from the $q$-stack, making the state $(r,p)$ with Bob the current player. Thus, Bob loses (and Alice wins).

Note that this tells us that Alice can win in the case that $q > 2p$, but it doesn't tell us how. We know there is a move that she can use to put herself in a winning position, but if we were Alice, we wouldn't know from this analysis what that move is.

$\endgroup$
  • $\begingroup$ For your solution, how Alice will win for p=2,q=5. $\endgroup$ – Hemant Rupani Jul 8 '15 at 9:28
  • $\begingroup$ @HemantRupani Doesn't she eat 2, leading to (2,3). Then Bob has to eat 2, leading to (1,2), so Alice can eat 1, leading to (1,1) and Bob loses $\endgroup$ – Ben Aaronson Jul 8 '15 at 12:29
  • $\begingroup$ @HemantRupani Ben Aarons on is correct about the (2,5) case. In general, my analysis only proves the existence of a winning strategy for Alice under certain conditions. It doesn't actually show what that strategy is. I find non-constructive results like that fascinating, although I must admit this result alone is not particularly helpful to Alice while she's playing... $\endgroup$ – John Stevens Jul 8 '15 at 15:19
  • $\begingroup$ Yes! My bad.... $\endgroup$ – Hemant Rupani Jul 8 '15 at 16:10
1
$\begingroup$

Provided they have unlimited appetites, Alice will win when

$p=nq~or~q=np~for~(n\in N \& n>1) $

Because, when Alice starts she'll eat

$\Big((n-1)\times~smaller~stack\Big)$, then both stacks will be same, and Bob will have to eat a stack(full).

Alice will win.

$\endgroup$
  • $\begingroup$ ... when Alice start he'll eat ... Are you sure it isn't she ? :) $\endgroup$ – Bojidar Marinov Jul 8 '15 at 10:06
  • 1
    $\begingroup$ @BojidarMarinov, No! Thanks! Now I see Alice shows a girls on Google Images :P so edited. $\endgroup$ – Hemant Rupani Jul 8 '15 at 10:17
  • 1
    $\begingroup$ @BojidarMarinov - I just assumed it was Alice Cooper vs Bob, in which case both are male. I also like the visual of Alice Cooper eating an arbitrarily high stack of pancakes. $\endgroup$ – Deacon Jul 8 '15 at 12:49
  • $\begingroup$ But how does alice force that position? if the stacks aren't multiples of each other then can you force your opponent to make them so? This doesn't seem to answer the question except in one small case. $\endgroup$ – Chris Jul 8 '15 at 14:09
  • $\begingroup$ @Chris... I missed. $\endgroup$ – Hemant Rupani Jul 8 '15 at 16:20

Your Answer

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

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