The Sprague-Grundy theorem is one of the most important results in combinatorial game theory. It allows us to analyze complex impartial games by breaking them down into simpler components. In an impartial game, both players have the same set of moves available from any position, and the game ends when no moves are possible.
To understand the Sprague-Grundy theorem, we need to learn about Grundy numbers. The Grundy number of a position is calculated using the mex function, which stands for minimum excludant. The mex of a set is the smallest non-negative integer that is not in the set. For example, mex of the set zero, one, two is three.
Let's see how Grundy numbers work in the classic Nim game. We have three piles with three, two, and one stones respectively. The Grundy number of each pile equals the number of stones in it. To find the overall Grundy number, we XOR all individual Grundy numbers: three XOR two XOR one equals zero. A position with Grundy number zero is a losing position for the current player.
The Sprague-Grundy theorem is the cornerstone of combinatorial game theory. It states that every impartial game position is equivalent to a Nim heap of a specific size, determined by the Grundy number of that position. This powerful result allows us to reduce any complex impartial game to the well-understood Nim game, enabling systematic analysis and optimal strategy determination.
The Sprague-Grundy theorem provides a systematic approach to finding winning strategies. Any position with Grundy number zero is a losing position for the current player, while positions with non-zero Grundy numbers are winning. The optimal strategy is always to move to a position with Grundy number zero, forcing your opponent into a losing position. This creates a complete framework for analyzing and solving impartial games.