Problem 488
Unbalanced Nim
Alice and Bob have enjoyed playing Nim every day. However, they finally got bored of playing ordinary three-heap Nim.
So, they added an extra rule:
- Must not make two heaps of the same size.
The triple (a,b,c) indicates the size of three heaps.
Under this extra rule, (2,4,5) is one of the losing positions for the next player.
To illustrate:
- Alice moves to (2,4,3)
- Bob moves to (0,4,3)
- Alice moves to (0,2,3)
- Bob moves to (0,2,1)
Unlike ordinary three-heap Nim, (0,1,2) and its permutations are the end states of this game.
For an integer N, we define F(N) as the sum of a+b+c for all the losing positions for the next player, with 0 < a < b < c < N.
For example, F(8) = 42, because there are 4 losing positions for the next player, (1,3,5), (1,4,6), (2,3,6) and (2,4,5).
We can also verify that F(128) = 496062.
Find the last 9 digits of F(1018).
不均衡取石子游戏
爱丽丝和鲍勃每天都玩取石子游戏。然而，他们终于还是厌倦了普通的三堆取石子游戏。
于是，他们给游戏增加了一条新的规则：
- 禁止让其中两堆大小相同。
三元组(a,b,c)仍旧分别表示三个堆的大小。
在新规则下，(2,4,5)将成为一个必败的局面。
一种可能的进程演示如下：
- 爱丽丝给对方留下(2,4,3)
- 鲍勃给对方留下(0,4,3)
- 爱丽丝给对方留下(0,2,3)
- 鲍勃给对方留下(0,2,1)
与普通的三堆取石子游戏不同，这个游戏中(0,1,2)或者它的任何排列都是游戏结束的状态。
对于一个整数N和所有满足0 < a < b < c < N的必败局面(a,b,c)，记所有a+b+c的和为F(N)。
例如 F(8) = 42，因为满足上述条件的必败局面共有4组，分别是(1,3,5)，(1,4,6)，(2,3,6)和(2,4,5)。
我们同样也可以验证 F(128) = 496062。
求F(1018)的最后9位数字。