喊到“50”获胜：NIM 与报数游戏的最优策略

call out “50” wins

1）玩 NIM：桌上有 $n$ 根火柴（例如 10 根），每回合可取 1、2 或 3 根。取到最后一根的人输。问最优策略是什么？

2）两人轮流报整数，第一个报到“50”的人赢。规则：先手第一次必须报 1 到 10 之间的整数；之后每次报的新数必须比上一次至少大 1、至多大 10。例如先手报 9，则后手可报 10 到 19。

你想先手吗？如果先手，你的策略是什么？

You are asked to play NIM, with the last one to pick up a stick losing. What's the optimal strategy? There are various versions of the game of NIM but let's consider a simple one. There are n matches, for example 10, on the table. Each turn you can take 1,2 or 3 matches. The person who takes the last stick loses.
You and I are to play a competitive game. We shall take it in turns to call out integers. The first person to call out “50” wins. The rules are as follows: 1. The player who starts must call out an integer between one and 10, inclusive; 2. A new number called out must exceed the most recent number called by at least one and by no more than 10. For example, if the first player calls out “nine,” then the range of valid numbers for the opponent is 10 to 19, inclusive.

Do you want to go first, and if so, what is your strategy?

解析

(1) 取最后一根输的 NIM（misère，允许取 1..3）

可验证输局为 $n\equiv 1\pmod 4$ （1、5、9、…）。最优策略是每步把对手留在 $1\bmod 4$ ：

(2) 报数到 50（每次加 1..10）

把 50 之前的“必达点”设为

50,\ 39,\ 28,\ 17,\ 6.

它们相差都为 11。先手应选择先报 $\boxed{6}$ ，此后无论对手报到 $7\sim 16$ 中的哪一个，你都报到 17；同理再把对手从 18..27 拉到 28，从 29..38 拉到 39，最后报到 50 获胜。

因此你应先手，并采用“始终把总数带到 6、17、28、39、50” 的策略。