PROJECT EULER · #0301
Nim
Nim is a game played with heaps of stones, where two players take it in turn to remove any number of stones from any heap until no stones remain.
We'll consider the three-heap normal-play version of Nim, which works as follows:
- At the start of the game there are three heaps of stones.
- On each player's turn, the player may remove any positive number of stones from any single heap.
- The first player unable to move (because no stones remain) loses.
If
- zero if, with perfect strategy, the player about to move will eventually lose; or
- non-zero if, with perfect strategy, the player about to move will eventually win.
For example
- current player moves to
- opponent moves to
- current player moves to
- opponent moves to
, and so wins.
For how many positive integers
Write-up coming later
The complete problem is available here. An approach, code, and answer will be added later.