0%

Problem 260


Problem 260


Stone Game

A game is played with three piles of stones and two players.
On each player’s turn, the player may remove one or more stones from the piles. However, if the player takes stones from more than one pile, she must remove the same number of stones from each of the selected piles.

In other words, the player chooses some $N>0$ and removes:

  • $N$ stones from any single pile; or
  • $N$ stones from each of any two piles ($2N$ total); or
  • $N$ stones from each of the three piles ($3N$ total).

The player taking the last stone(s) wins the game.

A winning configuration is one where the first player can force a win.
For example, $(0,0,13)$, $(0,11,11)$ and $(5,5,5)$ are winning configurations because the first player can immediately remove all stones.

A losing configuration is one where the second player can force a win, no matter what the first player does.
For example, $(0,1,2)$ and $(1,3,3)$ are losing configurations: any legal move leaves a winning configuration for the second player.

Consider all losing configurations $(x_i,y_i,z_i)$ where $x_i\le y_i\le z_i\le 100$.

We can verify that $\sum(x_i+y_i+z_i) = 173895$ for these.

Find $\sum(x_i+y_i+z_i)$ where $(x_i,y_i,z_i)$ ranges over the losing configurations with $x_i\le y_i\le z_i\le 1000$.


取石子游戏(一)

取石子游戏需要两名玩家和三堆石子。
每一名玩家在自己的回合可以从堆中取走一个或多个石子。然而,如果玩家从多个堆中取石子,从其中每个堆所取的石子数目必须一致。

也就是说,每一名玩家选择一个数$N>0$,然后移走:

  • 一个堆中的$N$个石子;或
  • 两个堆中各$N$个石子(共$2N$个);或
  • 三个堆中各$N$个石子(共$3N$个)。

拿走所有石子的玩家赢得游戏。

所谓必胜态,指的是先手玩家必胜的石子分布。
例如,$(0,0,13)$、$(0,11,11)$和$(5,5,5)$是必胜态,因为先手玩家可以立刻取走所有的石子。

所谓必败态,指的是无论先手玩家如何操作,后手玩家必胜的石子分布。
例如,$(0,1,2)$和$(1,3,3)$是必败态:先手玩家任何符合规则的取法都会给后手玩家留下必胜态。

考虑所有满足$x_i\le y_i\le z_i\le 100$的必败态$(x_i,y_i,z_i)$。
可以验证,对于所有这些必败态,$\sum(x_i+y_i+z_i) = 173895$。

考虑所有满足$x_i\le y_i\le z_i\le 1000$的必败态$(x_i,y_i,z_i)$,求$\sum(x_i+y_i+z_i)$。