初中数学竞赛 · 组合趣题

操作与游戏

找不变量，游戏就变成了账本；谁动谁死的局面，先看奇偶和余数。

八年级难度 ★★★★13 分钟

不变量与单调量

操作题两条主线：

不变量：操作前后不变的量（和的奇偶、黑白格计数、除以 $3$ 的余数）。终局状态的不变量值被锁定，对不上就说明到不了；
单调量：操作后严格减少（或增加）的量，保证过程必然终止，并能数出操作次数的上界。

游戏的胜负分析

轮流操作、无法行动者输的游戏，标准流程：

找终局：什么局面无法再动；
标 P/N：先手必输的局面叫 P（previous player 赢），先手必赢叫 N。终局是 P；一步能到 P 的局面是 N；所有下一步都到 N 的局面是 P。从终局倒着标；
必胜策略：处在 N 局面时，走出到达 P 的那一步，之后每轮把对手送回 P。

对称策略是初等博弈的利器：后手在中心对称位置模仿先手，往往直接获胜（棋盘对称、奇数堆石子等）。

例题

例1 奇偶不变量

黑板上写着 $1$ 到 $10$ 。每次擦去两个数，写上它们的和。若最后剩下的一个数是奇数，问操作次数与可能性的判断。

解：每次操作把数的个数减少 $1$ ，从 $10$ 个数到 $1$ 个数需 $9$ 次，与奇偶无关。

全部数字之和是操作不变量：初始和为 $1 + 2 + \dots + 10 = 55$ ，无论怎么合并，最后剩下的数恒等于 $55$ ，是奇数。所以最后必是奇数，操作方式不影响结果。

例2 P/N 标注

一堆 $21$ 个石子，两人轮流取 $1$ 到 $4$ 个，取到最后一粒者赢。先手还是后手有必胜策略？

解： $0$ 个石子时轮到谁谁输，标 P。倒推： $1$ 到 $4$ 都能一步取完，是 N； $5$ 时取 $1$ 到 $4$ 后剩 $1$ 到 $4$ （全是 N），标 P；每 $5$ 个一循环，P 局面是 $5 k$ 。

$21$ 不是 $5$ 的倍数，是 N 局面，先手必胜：先取 $1$ 个剩下 $20$ （P），此后每轮把对手取后凑成 $5$ （对手取 $x$ ，自己取 $5 - x$ ），每轮减少 $5$ ，最终石子在自己手中取完。

例3 对称策略

$8 \times 8$ 棋盘，两人轮流在空格放 $1 \times 2$ 骨牌（不重叠），无法放置者输。谁有必胜策略？

解：后手有必胜策略：棋盘以中心为对称中心，先手每放一块，后手放在其中心对称位置。

中心对称保持合法性的原因：骨牌不经过中心（ $8 \times 8$ 无中心格），先手的骨牌与其对称像不重叠；只要先手能放，对称位置必空，后手就能模仿。

于是先手永远有格子可走当且仅当后手刚走过，矛盾——最终无法行动的一定是先手，后手胜。

三个坑

不变量找错：不是任何量都不变，“总和”在“擦两写差”类操作里就会变，动手前先验证一遍。
P/N 只标了几格就下结论：倒推要标到目标局面，周期规律要验证一个完整周期。
对称策略不检查中心：棋盘有中心格或操作允许覆盖中心时，模仿可能失效，先核对对称的不动点。

练习（先做，再看答案）

数列 $1, 2, \dots, 100$ ，每次删去相邻两数并写上它们的差（绝对值）。最后剩下的数是奇数还是偶数？
一堆 $30$ 个石子，每次取 $1$ 到 $3$ 个，取到最后一粒者输。先手第一步应取几个？
$1$ 到 $100$ 写在黑板上，每次擦去 $a$ 、 $b$ 写上 $a + b + a b$ 。证明最后剩下的数与操作顺序无关，并求出它。

看答案

1. 每次操作把总和减去两倍较小的数，总和的奇偶不变。初始总和 $5050$ 是偶数，最后剩下偶数。

2. 取到最后一粒者输，所以剩 $1$ 时轮到谁谁赢。 $30 - 1 = 29$ ，每轮凑 $4$ ： $29 = 4 \times 7 + 1$ ，先手第一步取 $1$ 个，剩下 $29$ ，此后每轮与对手合计取 $4$ ，对手终将面对剩 $1$ 而被迫取最后一粒。

3. 注意 $a + b + a b = (a + 1) (b + 1) - 1$ ，令 $c_{i} =$ 当前各数加 $1$ 的乘积，每次操作把它保持不变。初始 $\prod_{i = 1}^{100} (i + 1) = 2 \times 3 \times \dots \times 101 = 101!$ ，最后剩下 $101! - 1$ ，与顺序无关。

一句话收束

操作题先找不变量与单调量；游戏题从终局倒标 P/N；有对称就让后手照镜子。

看完了？ 去组合趣题做配套练习，或回到竞赛总览挑下一个专题。想动手刷题、看看这些方法在题目里怎么用，去奥数挑战。