As 2021 comes to an end, I thought I’d use this month’s blog post to share one of the cooler bits of math I’ve learned this year. It’s a paradox that comes from combinatorial game theory which, for those not familiar with the field, Wolfram Mathworld describes as “the theory of two player games of perfect knowledge such as go, chess, or checkers”. Before I can get into the paradox, I need to start with a definition:
Definition: A game G is somewhat finite if it satisfies the following four conditions:
- G is a two player game, with a Player 1 and Player 2 alternating turns. Each player has complete information about what moves have been made so far.
- G is not a game of chance.
- Every play of G ends after finitely many moves.
- There are no ties. Once G terminates, there will be exactly one winner and one loser.
To make the above definition more concrete, here are a few examples of somewhat finite games:
- “Player 1 loses.” In this game, the only rule is that Player 1 immediately loses!
- Chess, with the added rule that if no check mate occurs by Turn 50, black immediately wins.
- Player 1 picks a natural number n > 100. Player 2 counts from 1 to n!, and their move ends once they’ve finished counting. On the next move, Player 1 immediately wins.
So despite the silly examples, somewhat finite games seem fairly well-behaved. However, consider a game with the following rules:
- The game starts with Player 1 choosing a somewhat finite game G.
- Player 2 then starts playing G as the first player, and with Player 1 as the second player.
- The game ends when G ends.
The game described above is called the hypergame. You can check that the hypergame is somewhat finite, which means that, during play of the hypergame, it is a valid move for Player 1 to choose G = hypergame. This means that, on Player 2’s next move, they must behave as the first player of the hypergame, and it’s again a valid move for Player 2 to choose G = hypergame. Then Player 1 is once again the first player of the hypergame, and can choose G = hypergame, and so on ad infinitum. But this implies that the hypergame is not somewhat finite, since we can force a game that goes on forever. Thus we have a paradox.
Paradoxes like the above are one of the things that first fascinated me when I got into math, and I hope you found this interesting, too. See you all in 2022!
(If my explanation of the paradox is unclear or you’d like to learn more, I’d suggest reading this paper by William S. Zwicker, who was the first to discover the paradox.)