Chomp
In this game, Archibald and Cookie Monster play a game that involves Cookie Monster's true favorite dessert–a bar of chocolate. In the beginning of the game, the bar of chocolate is a perfect rectangle. On any turn, a player picks a square of the chocolate and eats all squares above and to the right of it. The player who eats the bottom left square loses, as it is poisoned.
For example, the following is a valid first move, where player 1 chooses the square marked with an X and chomps everything above and to the right of it.
Zermelo’s Theorem tells us that one player has a strategy to win. As a simple case, if Archibald goes first, identify the winning player and strategy if the chocolate bar begins as a perfect square.
Archibald has the winning strategy by chomping out a square such that two equally long one-square-thick spires are left:
Note that this essentially reduces to a game of Nim with two equally-sized piles. So, Archibald can win from here by mirroring Cookie Monster.
It turns out that the general strategy for Chomp is unknown. Computers can play perfectly by brute force, but this is unfeasible for large chocolate bars as the number of possible game states grows exponentially.
However, it is possible to prove that the player who chomps first always has a winning strategy on every size of bar, even without knowing what the strategy is. Try it out yourself.
Hint: Suppose by contradiction that on some starting bar, no matter what initial move the first player makes, the second player has a winning strategy.
Suppose by contradiction that on some starting bar, no matter what initial move that Archibald makes, Cookie Monster has a winning strategy. Then, consider the position in which Archibald removes the single upper right square, like so:
Observe that any possible move from Cookie Monster in this game state would have been possible to make as Archibald. Since we assume that Cookie Monster must have a winning strategy as a follow-up to this move, then it must have been possible for Archibald to win by using Cookie Monster's strategy to begin with.
Thus, although we still don’t know what the strategy for Archibald is, we have proven that it is always possible for him to guarantee a win. This argument is known as the strategy stealing argument. As an exercise, try to apply this argument to prove that the second player can never guarantee a win in tic-tac-toe.