A Game of Candy Squares

This two-player game starts with two heaps of candy squares. To make a move, a player gobbles one heap and divides the other one into two. The players take turns; the one who can't move, i.e., divide a heap, loses the game. Is there a strategy to win the game?

In the applet below, the game is played against the computer. To divide a heap just click somewhere between two squares. The other heap will automatically disappear. If you wish the computer to make the first move press the "You start" button.

If you are reading this, your browser is not set to run Java applets. Try IE11 or Safari and declare the site https://www.cut-the-knot.org as trusted in the Java setup. What if applet does not run?

Discussion  An easily overlooked but crucial fact is that one of the two present heaps disappears on a move and thus has no bearings on the game, except, of course, that up front one may not know which one of the two heaps is less important than the other.

We are going to prove that the player who faces a situation in which at least one of the heaps has an even number of squares has a winning strategy.

For convenience, let's call the configuration of two heaps of which at least one has an even number of squares P-position. Let's call all others N-position. And let's denote positions by the lengths of their heaps, i.e., by a pair of integers (n, m). Thus (n, m) is a P-position if either n or m is even, perhaps both.

Statement

Every move in an N-position - different from the final (1, 1) - leaves a P-position. In any P-position, there is a move that leaves an N-position.

Proof

Assume both n and m are odd, i.e., (n, m) is an N-position. If both n and m are greater than 1, there is a choice to make. Otherwise, the player will split the larger heap and consume 1 square. Any split of a heap with an odd number of squares leaves one even heap, i.e., a P-position.

Assume n is even, so that (n, m) is a P-position. It is always possible to split n into the sum of two odd numbers and consume the m-heap. The position left is an N-position.

References

1. A Decade of the Berkeley Mathematical Circle, The American Experience, Volume I, Z. Stankova, Tom Rike (eds), AMS/MSRI, 2008, p. 159 • What Is a Combinatorial Game?
• A Sticky Problem
• Another Sticky Problem
• Date Game
• Dawson's Chess: an Interactive Gizmo
• Dawson's Kayles: an Interactive Gizmo
• Grundy's Game
• Hex 7
• Kayles
• Nimble: an Interactive Gizmo
• Northcott's game (An Interactive Gizmo)
• Odd Scoring
• One Pile: an Interactive Gizmo
• Plainim (An Interactive Gizmo)
• Plainim Misere (An Interactive Gizmo)
• Scoring: the simplest of the impartial games
• Scoring Misere: an Interactive Gizmo
• Scoring Misere: Two Heaps Perfect Strategy
• The Fraction Game
• The Silver Dollar Game
• Silver Dollar Game With No Silver Dollar
• Subtraction Game
• TacTix: an Interactive Gizmo
• Turning Turtles
• Take-Away Games
• Wythoff's Nim, Literal Implementation
• Wythoff's Nim (An Interactive Gizmo)
• 