Puzzle time - Pancake stacks
-
At the table are you, your roommate, and two stacks of pancakes, of height m and n. You and she, in turn, must eat from the larger stack a non-zero multiple of the number of pancakes in the smaller stack. The bottom pancake of each stack is soggy, and thus whoever first finishes a stack is the loser.
For which pairs (m,n) do you, who happen to be playing first, have a winning strategy?
-
Hm, my first thought when reading the description: This sounds a lot like the ancient Euclid algorithm to find the greatest common divisor of two numbers, hence I assume that the (m,n) pairs will have something to do with that (wild guess, probably wrong: m and n need to be coprime).
-
This is certainly not a complete solution, but I think the game is over whenever both stacks have the same height. Hence a set of pairs where there is a winning strategy is pairs of the form
(a* b,b)or(b,a*b)for any a >=2 and b >=1: Eat (a-1) times b pancakes and the remaining stack is (b,b).I guess this solution is complete for games with just one round. For games with two rounds, consider how one can force stacks of the form
(a*b,b)as above... -
I never made much progress on this week’s puzzle but it looks like the Fibonacci observation was not irrelevant after all.
SOLUTION: Let m and n be the two stack sizes. You (if you are next to play) are immediately stuck when m = n. Thus, if instead m > n and m is a multiple of n, you can win by eating m − n pancakes off of the m−stack, reducing it to size n. For example, if the short stack has just one pancake, you are in great shape.
What if m is only close to a multiple of n? Suppose, for example, that m = 9 and n = 5. Then you are forced to reduce to m = 4, n = 5, but your opponent must now give you a 1-stack. If m = 11 and n = 5, you have a choice, but reducing to m = 6, n = 5 wins for you.
It's beginning to look like you want to make the ratio of the stacks small for your opponent, forcing her to make the ratio big for you. Let's see. Suppose the current ratio r = m/n is strictly between 1 and 2; then the next move is forced and the new ratio is 1/(1−r). These ratios are equal only for r = phi = (1+ sqrt 5)/2 ~ 1.618, the golden mean; since phi is irrational, one of the two ratios r and 1/(1−r) must exceed phi while the other is smaller than phi. Aha! Thus, when you present your roommate with r < phi she must make it bigger, then you make it smaller, etc., until she's stuck with r = 1 and must lose!
We conclude that you win exactly when the initial ratio of larger to smaller stack exceeds phi, in which case you can always make a move that reduces the ratio to less than phi. To see this, suppose m > phi n, but m is not a multiple of n. Write m = an + b, where 0 < b < n. Then either n/b < phi, in which case you eat an, or n/b > phi, in which case you eat only (a−1)n. This leaves your roommate with a ratio below phi, and faced with a forced move which restores a ratio greater than phi.
