Problem 301
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 his turn the player removes any positive number of stones from any single heap.
- The first player unable to move (because no stones remain) loses.
If (n1,n2,n3) indicates a Nim position consisting of heaps of size n1, n2 and n3 then there is a simple function X(n1,n2,n3) — that you may look up or attempt to deduce for yourself — that returns:
- 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 X(1,2,3) = 0 because, no matter what the current player does, his opponent can respond with a move that leaves two heaps of equal size, at which point every move by the current player can be mirrored by his opponent until no stones remain; so the current player loses. To illustrate:
- current player moves to (1,2,1)
- opponent moves to (1,0,1)
- current player moves to (0,0,1)
- opponent moves to (0,0,0), and so wins.
For how many positive integers n ≤ 230 does X(n,2n,3n) = 0?
取石子游戏
取石子游戏是用数堆石子进行的游戏，由两名玩家轮流从任意一堆中取走任意数量的石子，直到石子全部取完为止。
我们考虑按如下方式进行的三堆经典取石子游戏：
- 游戏开始时有三堆石子。
- 每名玩家在轮到自己时从任意一堆中取走任意正数枚石子。
- 轮到时已无石子可取的玩家输掉游戏。
如果用(n1,n2,n3)表示游戏目前的三堆石子分别有n1、n2和n3枚，那么存在一个简单函数X(n1,n2,n3)——你可以查询相关知识或自己推理得出——其函数值为：
- 零，如果在双方都采取最优策略的情况下即将取石子的玩家最终会输掉游戏；或者
- 非零，如果在双方都采取最优策略的情况下即将取石子的玩家最终会赢得游戏。
例如，X(1,2,3) = 0，因为无论当前玩家如何操作，他的对手都能够给他留下两堆同样规模的石子并不断仿照他的操作直到石子全部取完；因此当前玩家必定会输掉游戏。举例来说：
- 当前玩家取完后留下(1,2,1)
- 对手玩家取完后留下(1,0,1)
- 当前玩家取完后留下(0,0,1)
- 对手玩家取完后留下(0,0,0)，对手玩家获胜。
有多少个正整数n ≤ 230使得X(n,2n,3n) = 0？