一个经典的博弈论题。

Problem

有 $n$ 个石子，A B 两人博弈，A 先手。A 首先取若干个石子（至少一个，不能取完），然后 B 和 A 再轮流取石子，每次取的石子不能超过上次取的石子数，且至少取一个，无法操作的人输。求 $n$ 满足什么条件时先手必胜。

增强一下：如果不能超过上次取的石子数的两倍，求先手必胜的条件？如果不能超过 $f(x)$ （$x$ 表示上次取的石子数， $f$ 是一个非降函数），求先手必胜的条件？

Solution

令 $H$ 为先手必败的 $n$ ，易知 1 肯定在 $H$ 里。

接下来我们递推出 $H$ 。可以证明，如果 $H_{i+1} = H_i + H_l$ ，其中

$$H_l = \min_{x \leq i} \{H_x \| f(H_x) \geq H_i \}$$

我们证明，若 $x < H_l$ 是必胜状态，则 $H_i + x$ 一定也是必胜状态。由于 $x$ 是必胜状态，所以先手一开始一定可以照着 $x$ 的必胜策略行动，且先手一定可以拿掉第 $x$ 个石子。接下来还剩 $H_i$ 个石子，一开始的先手变成了后手，所以先手一定可以必胜 。

若 $x < H_l$ 是必败状态，则 $H_i + x$ 也是必胜状态。先手只需一开始拿走 $x$ 个石子，则还剩 $H_i$ 个石子，后手必败，所以先手必胜。

同样，我们可以证明 $H_i + H_l$ 是必败状态。若先手一开始拿走不小于 $H_l$ 个石子，则后手可以把剩下的所有石子拿完。若先手一开始拿走的石子数小于 $H_l$ ，则后手一定有策略拿到第 $H_l$ 个石子。此时还剩下 $H_i$ 个石子，先手尚未改变，所以先手必败。

当 $f(x) = x$ 时，可以得到 $H = \{1, 2, 4, 8, \dots, 2^t\}$ 。

当 $f(x) = 2x$ 时，可以得到 $H = \{1, 2, 3, 5, 8, \dots, fib_t\}$ 。