TOAD 3 - Take the Last Chip

一个经典的博弈论题。

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\}\) 。