Project Euler/301
From charlesreid1
Problem statement
The problem asks for the number of positive integers $ n \leq 2^{30} $ such that the Nim game position (n, 2n, 3n) is a losing position for the player whose turn it is, assuming perfect play.
The function X(n1, n2, n3) determines this: X=0 for a losing position and X!=0 for a winning position
Notes
Key mathematical topics:
- Game theory (impartial game, available moves only depend on the state of the game and not on which player is moving)
- P-positions (previous player winning, current player will lose if opponent plays optimally) and N-positions (next player winning)
- Problem statement says, X(a,b,c)=0 corresponds to a P-position
- Bouton's Theorem (fundamental to solving Nim)
- States that a Nmim position $ (n_1, n_2, ..., n_k) $ is a P-position iif and only if the nim-sum of the heap sizes is zero
- The Nim-sum is calculated using the bitwise XOR operation
- The given 3-heap problem has a Nim-sum $ X(n_1, n_2, n_3) = n_1 \oplus n_2 \oplus n_3 $