Golden Pancakes

Question

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.

Answer 1

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.

Answer 2

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.

Answer 3

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.

Answer 4

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.