Combinatorial game theory (Summer session 2, 2021) is the study of games with no randomness or chance. Some of the most popular games in the world, such as chess and go, fall under this category, although we will not spend much time on these games, since they are too complicated for our current techniques.
Instead, we will spend a lot of time looking at the games of Nim, Hackenbush, and Domineering. In the game of Nim, there are several piles of stones on the table, and two players take turns removing as many stones as they wish on each turn, but only from one pile per turn. You win (or lose, in a popular variant) if you take the last stone on the whole table.
In the game of Hackenbush, we start with a graph emanating from the ground, with each edge colored blue, red, or green. Two players take turns removing edges, with the colors indicating which edges they can remove: one player can remove blue edges, the other can remove red edges, and either player can remove green edges. If an edge is left dangling in midair, it is also removed. The player to move loses if there are no available edges left to remove.
In the game of Domineering, two players take turns placing dominoes on two squares of rectangular grid, with one player placing them in the north-south direction and the other player placing them in the east-west direction. Dominoes may not overlap. The player to move loses if there are no more spaces left to place a domino in that player’s orientation.
These games are model games in that they highlight much of the theory that mathematicians have worked out. They also have surprising connections to the rest of mathematics. For example, a careful study of Nim and its variants leads to the construction of finite fields, finite simple groups, and error-correcting codes. The study of Hackenbush leads to the development of an exceptionally rich number system known as the surreal numbers. We will study these connections and others in the class.
Since combinatorial game theory is a relatively new subject, there are lots of open problems and avenues for exploration; see for instance Richard Guy’s list. We will present many open problems in class that students will be encouraged to work on.
This class will meet Monday, Tuesday, Thursday, and Friday mornings from 9:30–11:30 AM Pacific time for 5 weeks, starting July 12th. Applications are due May 30th. Click here to apply!
Euler Circle 