← 完整题目索引

PROJECT EULER · #0306

纸条游戏

Paper-strip Game

仅题目 · 已解决原题 ↗

以下游戏是组合博弈论的经典示例:

两名玩家从一条 n 白色方块开始,然后轮流轮流。
在每个回合中,玩家选择两个连续的白色方块并将它们涂成黑色。
第一个无法采取行动的玩家失败。

  • n=1:没有有效的移动,因此第一个玩家自动失败。
  • n=2:只有一次有效的移动,之后第二个玩家就输了。
  • n=3:两次有效的移动,但都导致第二个玩家失败。
  • n=4:第一个玩家可以通过三个有效动作,通过绘制中间的两个方块来赢得游戏。
  • n=5:第一个玩家有四次有效的移动(如下图红色所示),但无论玩家做什么,第二个玩家(蓝色)都会获胜。
0306_pstrip.gif

因此,对于 1n5n 有 3 个值,第一个玩家可以强制获胜。
同样,对于 1n50n 有 40 个值,第一个玩家可以强制获胜。

对于 1n1000000,有多少个 n 的值可以让第一位玩家获胜?

题解待补充

这道题的题目已收录,解题思路、代码和答案将在后续补充。