Let’s play some games today! We will play a classic game known as nim, which is thought to be one of the oldest games.
Typically people play nim using matchsticks, though stones and coins are popular too. There are a few heaps of matchsticks in nim. Players take turns to remove matchsticks from a heap of their choosing. The player can remove any number of matchsticks they wish from that heap. Whoever has no matchsticks left to take loses.
This following position will be written as
As another example, this is
We will omit heaps of size zero, so
Nim is important because a large class of games are equivalent to it despite its simple appearance. The interested reader should look up "Sprague-Grundy Theorem".
Let us introduce a few terms that will be helpful for analyzing games. A game