Sign in to watch this lesson
Advanced - Combinatorics, Games and Puzzles · 4:40
Nim and Bouton's Theorem
In Nim, players take any number of tokens from one pile, and whoever takes the last token wins. After labelling winning and losing positions from the bottom up in a simple take-away game, we prove Bouton's theorem: the player to move loses exactly when the xor of the pile sizes is zero, and the winning move turns a pile x into x xor s. We finish with the misère version, where the last token loses, and two interview traps: the parity of the total and staircase Nim.
You will learn
- Classify positions of a finite impartial game as winning or losing from the bottom up, and solve take-away games such as 'take 1 to k' (losing iff n is a multiple of k + 1)
- State and prove Bouton's theorem: the player to move in Nim loses iff the xor of the pile sizes is 0
- Construct the winning move by choosing a pile x with the top bit of s = xor set and moving it to x xor s
- Play misère Nim by switching to 'leave an odd number of 1-piles' at the endgame, and recognise the staircase and sum-parity traps