六年后回看 CSP-S 2020 T4 贪吃蛇

题目引入

六年前考 CSP-S 2020 时，由于我当时的代码能力并不娴熟，写完前两题后，留给我的时间已经不多。然后 T4 看了一眼题面，就写了 20 分特殊情况赶紧走人。六年后，我从蒋炎岩的视频得知 OI 圈又发生了诸多变化，这让我再次回到了我曾经刷题的洛谷，发现 LLM 经过一定的尝试甚至可以 AC 一道新鲜出炉，并且只有出题人一人通过的黑题。

——当然我今天要说的重点不是这个，而是我回到了当时苟且偷生 20 分的 T4 贪吃蛇，简化题面是：

有 $n$ 条蛇，编号为 $1,\dots ,n$，初始体力为正整数 $a_i$，满足

$$a_1\le a_2\le \cdots \le a_n.$$

任意时刻，用 $(\text{体力},\text{编号})$ 比较蛇的强弱：体力大者更强；体力相同时，编号大者更强。因此最强蛇和最弱蛇唯一确定。

当前最强蛇可以选择是否吃掉当前最弱蛇。若最强蛇为 $(x,i)$，最弱蛇为 $(y,j)$，吃后最弱蛇死亡，最强蛇变为

$$(x-y,i).$$

每条蛇都是理性的：当它成为当前最强蛇时，当且仅当它吃掉当前最弱蛇后，在后续同样规则下自己最终不会死亡，它才会吃；否则它不吃，游戏立即结束。只剩一条蛇时游戏结束。

问题是求最终会剩下几条蛇？$n\le {10}^6$。

当然这个题已经有很多题解了，然而我在尝试上手这套题时，意外提出了另一个猜想：

当初态蛇的体力单调递增（而不是单调不降），也就是满足：

$$a_1<a_2<\cdots <a_n.$$

时，那么最后剩余蛇的数量一定是奇数吗？

当然，答案是 yes，只不过证明的过程比我想象的要繁琐得多，甚至比原题本身的思维+代码过程还要繁琐。更重要的是，完整的证明过程全部由 LLM 生成，这似乎与前文的 LLM AC 黑题交相呼应。

简要思路

这里我尽量先从人类的思维方式拆解这道题，然后在下一节给出 AI 自底向上的 Lemma-Theorem 风格的证明过程。

从原题题解出发

首先根据原题的题解，我们知道在一般的单调不降版本，一共有两个阶段：

• 阶段一（安全步）：所有最强蛇进食后都不是最弱蛇，放心大胆吃！
• 阶段二（危险步）：所有最强蛇进食后都是最弱蛇，直到有条蛇可以放心吃为止（吃了后不是最弱或者只剩两条）
• 阶段一结束时，游戏就基本结束了（根据阶段二的奇偶性看能不能再吃一次）

我们着重理解一下“根据阶段二的奇偶性看能不能再吃一次”这句话。首先考虑危险步的场景：

• 如果只有两条蛇，那么最强蛇的选择是毫无疑问的“肯定吃”；
• 如果有三条蛇，那么最强蛇吃完变成最弱，那么在下一轮一定被吃。所以最强蛇肯定选择不吃；
• 如果有四条蛇，那么最强蛇肯定会选择吃，因为它变成最弱后，根据上一行的结论，当前最强蛇肯定不会吃它；
• ......

所以根据以上推理，当 $n$ 为奇数时肯定选择不吃；$n$ 为偶数是肯定选择吃，从而变成 $n$ 为奇数的情况，然后游戏马上停止，最终剩下奇数条蛇——刚好是我们题目要证明的条件。

所以我们有一个很美好的设想——如果危险步一旦进入，不会切换成安全步，那么这道题其实就做完了。我经过了大量随机单调递增序列的验证，并没有找到反例，甚至即使只是把“单调递增”改为“单调不减”都能很快找到反例（比如说 1 1 1 1，第一步吃完后马上变成阶段一）。说明最后剩下奇数这个条件其实很苛刻，这进一步增强了“单调递增序列”真的满足“阶段二不会切换成阶段一”的可能性。

核心不等式

我们的思路是使用归纳法。首先我们来模拟一次最强蛇吃最弱蛇的过程，我们记当前剩下的蛇 $u_i=(b_i,\mathrm{id}(u_i))$，也就是对应体力和编号。把当前状态按照从弱到强排好为：

我们假设当前位于危险步（如果这个起始条件一直不成立，这意味着整个过程一直都是安全步，最后一定得到结果 $1$，满足题意），$u_m$ 吃掉 $u_1$ 后，得到更新后的状态 $u_m^{\prime }=(b_m-b_1,\mathrm{id}(u_m))$，并且 $u_m^{\prime }$ 是最弱蛇。

然后根据归纳法，需要证明下一步是危险步也仍然成立。具体而言，目前的最强蛇 $u_{m-1}$ 要吃掉最弱蛇 $u_m^{\prime }$，这一步的新体力就是 $b_{m-1}-(b_m-b_1)=b_{m-1}-b_m+b_1$，对应编号 $\mathrm{id}(u_{m-1})$。我们需要保证 $(b_{m-1}-b_m+b_1,\mathrm{id}(u_{m-1}))<u_2$，这等于证明：

因为 $u_1<u_2<\cdots <u_{m-1}<u_m$ 保证 $b_{m-1}\le b_m$。如果不取等号，前者是显然的；如果取等号走右边分支，也就是$(b_1=b_2)\wedge (b_{m-1}=b_m)$，就要证明 $\mathrm{id}(u_{m-1})<\mathrm{id}(u_2)$，后者是本题核心且困难的部分。

主要 invariant 以及简要直觉说明

为了证明这个不等式，有以下五个不变量（性质）被用到（为了书写方便，记 ${\iota }_r=\mathrm{id}(u_r)$）：

• $A$: 不会有三条蛇体力相同。
• $B$: 如果出现一对体力相同的蛇，那么这个体力一定比当前“最强体力 − 最弱体力”（记为 $\mathrm{\Delta }$）还大。
• $C$: 对于某低体力区（位置 $r\ge 3$，并且体力不超过 $\mathrm{\Delta }$）的蛇 $u_r$，若 $u_k$ 排在 $u_r$ 右边，则 ${\iota }_k>{\iota }_r$。
• $D$: 非最底部（位置 $r\ge 2$）的相等对，左边那条的编号小于它右侧所有蛇的编号。
• $E$: 不同体力的两组相等对必须编号交错。例如 $u_s<u_{s+1}<u_t<u_{t+1}$ 但 $b_s=b_{s+1}<b_t=b_{t+1}$，则 ${\iota }_{s+1}>{\iota }_t$。（欲证的 ${\iota }_{m-1}<{\iota }_2$ 是其直接推论）

注意我们欲证的这五个性质无论是在安全步还是在危险步都满足，而严格递增的初始态显然满足。因此这里还是类似于联合归纳的思路，假设 $A,B,C,D,E$ 成立，然后推导出最强蛇吃完后的下一状态 $A^{\prime },B^{\prime },C^{\prime },D^{\prime },E^{\prime }$ 仍然成立。具体的推导如表所示：

然后接下来说一下每一个性质的直觉步骤：

A'

如果出现三条体力相同的蛇，那么新增的蛇体力值 $\mathrm{\Delta }=b_m-b_1$ 要与旧蛇中有两条体力均为 $\mathrm{\Delta }$ 重合，而这与先前的假设 $B$ 矛盾。所以 $A^{\prime }$ 成立。

B'

这应该是最难证的一个性质。分为两种情况：这一个相等对是这一轮新出现的，还是先前就存在的：

对于这一对是新出现的情况，当蛇 $u_m$ 吃掉 $u_1$ 时，体力 $d=\mathrm{\Delta }=b_m-b_1$，而此时新宽度 ${\mathrm{\Delta }}^{\prime }\le b_m-b_2$。若 $b_1\ne b_2$，我们可以立即推出现在的 ${\mathrm{\Delta }}^{\prime }<\mathrm{\Delta }=d$。而对于 $b_1=b_2$，也就是最弱两条蛇体力相同的情况，性质 $B$ 已经说过 $\mathrm{\Delta }<b_1$，因此 $u_m$ 吃掉 $u_1$ 后实际上还有一条旧蛇的体力值也为 $b_m-b_1<b_1$（为了和这个新蛇配对），这与 $u_1,u_2$ 是最弱两条蛇的假设矛盾。

对于先前就存在这一对的情况，先前的情况 $B$ 已经满足 $d>\mathrm{\Delta }$，如果新蛇不是最弱蛇，那么我们有 ${\mathrm{\Delta }}^{\prime }\le \mathrm{\Delta }<d$ 直接成立。现在我们考虑新蛇（同时也是最弱蛇）体力为 $\mathrm{\Delta }$ 的情况，此时的 ${\mathrm{\Delta }}^{\prime }=b_{m-1}-\mathrm{\Delta }$。我们现在欲证 $d>{\mathrm{\Delta }}^{\prime }$，有不等式 ${\mathrm{\Delta }}^{\prime }=b_{m-1}-\mathrm{\Delta }\le b_m-\mathrm{\Delta }=b_1$，即 ${\mathrm{\Delta }}^{\prime }\le b_1$。另一方面若 $d=b_1$，这意味着原先就有一对体力为 $b_1$ 的蛇，加上原来的被吃掉的 $u_1$，一共就有三条体力相同的蛇，与性质 $A$ 矛盾，所以推出 $d\ne b_1$。而又因为这对蛇不是最弱的（否则被吃掉的就不是 $u_1$ 了），可得 $d>b_1$，因此综合前面的 ${\mathrm{\Delta }}^{\prime }\le b_1$ 也可以推出 ${\mathrm{\Delta }}^{\prime }<d$。

C'

$C^{\prime }$ 其实很容易直觉理解，因为新的蛇，不会插入到低体力区的左边，即使体力相同，也会因为编号更大而在更右边的位置。

D'

这里考虑两种情况：旧相等对不变和插入新相等对。对于前者，根据先前的情况 $D$，最右边的蛇 $u_m$ 编号 ${\iota }_m$ 肯定大于旧相等对，所以这条蛇无论插入在哪个位置都不会影响结论。

对于出现了新相等对的情况，设新相等对 $v=(\mathrm{\Delta },{\iota }_m)$ 撞上某旧蛇 $u_k$，满足 $b_k=\mathrm{\Delta }$，我们只需考虑 ${\iota }_m>{\iota }_k$ 是否成立。由于我们讨论的是“非最底部相等对”，若 $k=2$，则删去 $u_1$ 后，$u_2$ 与 $v$ 会形成最底部相等对，矛盾。因此 $k\ge 3$。而这条旧蛇 $u_k$ 位于“低体力区”范围内，且 $u_m$ 在原状态中位于 $u_k$ 右边，所以根据性质 $C$，$u_m$ 的编号大于 $u_k$。

E'

这里考虑四种情况（从低到高）：旧-旧、旧-新、新-旧、新-新。第一种情况可以直接 $E$ 归纳得出，第四种情况由于 $A$ 不可能发生，而性质 $B$ 说明新相等对的体力 $\mathrm{\Delta }$ 一定小于已有的旧相等对 $d$，从而第二种情况（旧-新）也不可能出现。

最后只剩下情况 新-旧。仍然设新相等对 $v=(\mathrm{\Delta },{\iota }_m)$ 撞上某旧蛇 $u_k$，满足 $b_k=\mathrm{\Delta }$。我们设高旧对的两条蛇为 $u_t,u_{t+1}$，因此我们需要证明 ${\iota }_t<max({\iota }_k,{\iota }_m)$。这里我们选择证明更强的 ${\iota }_t<{\iota }_m$。由于性质 $D$，在 $u_m$ 吃之前，它肯定在 $u_t,u_{t+1}$ 的右边（非最底部），所以 ${\iota }_t<{\iota }_m$ 成立。

完整证明

注意接下来的内容由 GPT 5.5-Pro 生成，我本人一共使用了三次 prompt：

• 第一次是给题意；

• 第二次追问 GPT 写出证明 $\mathrm{id}(u_{m-1})<\mathrm{id}(u_2)$ 的具体过程；

• 第三次是“请你把之前的输出合起来，写成一个完整的证明”。

这里只给出第三次 prompt 的完整输出。

下面把前面的结论合成一篇完整证明。记一条蛇为

其中 $x$ 是体力，$i$ 是编号。定义强弱序

当且仅当

或

所以 $\prec$ 越大表示越强。

定理

从初态

出发，按照题目中的理性规则进行游戏，最终存活蛇的数量一定为奇数。

一、强制过程与记号

先定义一个辅助过程，称为强制过程：无论蛇是否理性，每一步都强制令当前最强蛇吃掉当前最弱蛇。

若某个强制可达状态中还有 $m$ 条蛇，按强弱排序为

记

其中 $b_r$ 是体力，${\iota }_r=\mathrm{id}(u_r)$。

于是

若 $b_r=b_{r+1}$，则由于编号大者更强，有

当前最强蛇 $u_m$ 吃掉当前最弱蛇 $u_1$ 后，得到新蛇

记当前状态的宽度为

二、强制过程中的核心不变量

我们先证明一个较强的不变量族。之后要用到的关键结论是：

若某个强制可达状态中，前两条蛇体力相同，后两条蛇体力也相同，即

$$b_1=b_2,b_{m-1}=b_m,$$

则

$${\iota }_{m-1}<{\iota }_2.$$

为了严格证明它，我们同时证明以下五个性质在所有强制可达状态中成立。

不变量 A：不存在三条蛇体力相同

即任意强制可达状态中，不可能有三条蛇具有同一体力。

不变量 B：相等相邻对的体力大于当前宽度

若

则

不变量 C：低体力区编号单调

若

则对所有 $s>r$，都有

不变量 D：非底部相等对的左端编号小于右侧所有蛇编号

若

则对所有 $s>r+1$，都有

不变量 E：两个相等相邻对之间满足交叉编号关系

若

则

我们将证明 A–E 对所有强制可达状态成立。

初态成立

初态中

因此没有任何相等体力对，所以 A、B、D、E 都是空命题。

而初态排序就是

所以若 $r\ge 3$，则对所有 $s>r$，有

因此 C 也成立。

归纳步

假设某个强制可达状态

满足 A–E。

记

强制下一步中，新蛇为

下一状态由

重新排序得到，记为

设其体力为

下一状态宽度为

下一状态的体力集合是

所以

下面分别证明 A–E 在下一状态中仍成立。

1. 证明 B 在下一状态中成立

取下一状态中的一个相等相邻对，设其体力为 $d$。

分两类。

情形 1：这是旧相等对

也就是说，这个相等对不含新蛇 $v$，而是原状态中已经存在的两条旧蛇。

由于归纳假设 A 成立，原状态中不存在三条同体力蛇，所以这个旧相等对在原状态中也是相等相邻对。由归纳假设 B，

我们要证明

因为 $d>\mathrm{\Delta }$，且 $d\le b_{m-1}$，所以

若

则

于是

若

则

这个旧相等对不含 $u_1$。如果 $d=b_1$，则原状态中至少有 $u_1$ 以及这两条旧蛇共三条蛇体力为 $b_1$，违反 A。因此

于是

所以旧相等对满足 B。

情形 2：这是新产生的相等对

这说明新蛇 $v$ 的体力

恰好等于某条旧蛇 $u_k$ 的体力：

于是新相等对的体力为

因为 $b_k=\mathrm{\Delta }\ge b_2$，所以

我们要证明

若

则原状态底部有相等对 $u_1,u_2$。由归纳假设 B，

但另一方面

矛盾。

所以

又因为

故

于是

所以新相等对也满足 B。

因此 B 在下一状态中成立。

2. 证明 A 在下一状态中成立

原状态中没有三条蛇体力相同。

下一状态中唯一可能产生新的体力重合的是新蛇

如果 $v$ 加入某个已有的旧相等对，就会产生三条同体力蛇。

但若原状态中已经有两条旧蛇体力为 $\mathrm{\Delta }$，那么原状态中存在相等相邻对，体力为 $\mathrm{\Delta }$。这与归纳假设 B 矛盾，因为 B 要求任意相等相邻对体力 $d$ 满足

因此新蛇最多只能与一条旧蛇同体力，不可能制造三条同体力蛇。

所以 A 在下一状态中成立。

3. 证明 C 在下一状态中成立

我们要证明：若

则对所有 $s>r$，

先说明 $w_r$ 不可能是新蛇 $v$。

若 $w_r=v$，则

又因为 $r\ge 3$，所以在下一状态中至少有两条蛇排在 $v$ 前面，因此

于是

若 $b_1=b_2$，则原状态底部有相等对，由 B 得

与 $b_2\le \mathrm{\Delta }$ 矛盾。

故

于是

所以

但 $w_r=v$ 时 $c_r=\mathrm{\Delta }$，与 $c_r\le {\mathrm{\Delta }}^{\prime }$ 矛盾。

因此 $w_r$ 必为某条旧蛇。设

因为删去 $u_1$ 后，旧蛇 $u_2$ 在下一状态中至多排第 $2$，而 $r\ge 3$，所以

下面证明

反设

若

则

于是

与

矛盾。

若

则

从而

由 $b_k\le {\mathrm{\Delta }}^{\prime }$，得

所以

但 $k\ge 3$，所以

于是

出现三条同体力蛇，违反 A。

故必有

由原状态的 C，因

可知对所有 $t>k$，

下一状态中排在 $w_r=u_k$ 右侧的蛇，要么是某条旧蛇 $u_t$，其中 $t>k$，要么是新蛇 $v$，其编号为 ${\iota }_m$，而 $m>k$。因此均有

所以 C 在下一状态中成立。

4. 证明 D 在下一状态中成立

取下一状态中的一个非底部相等相邻对

且

我们要证明：对所有 $s>r+1$，

情形 1：这是旧相等对

设它在原状态中为

因为它不含被删去的 $u_1$，所以

由原状态的 D，

对所有

成立。

下一状态中排在这个旧相等对右侧的蛇，要么是旧蛇 $u_t$，其中 $t>k+1$，要么是新蛇 $v$，其编号为 ${\iota }_m$，而 $m>k+1$。因此结论成立。

情形 2：这是新产生的相等对

这说明

对某个 $2\le k\le m-1$ 成立，新相等对由旧蛇 $u_k$ 和新蛇 $v$ 组成。

由于这个相等对在下一状态中不是底部相等对，即 $r\ge 2$，所以删去 $u_1$ 后，仍有至少一条蛇排在它们前面。因此

由原状态的 C，因

可知对所有 $t>k$，

特别地，

所以在这个新相等对中，左端是旧蛇 $u_k$，不是新蛇 $v$。

下一状态中排在这个新相等对右侧的蛇都是旧蛇 $u_t$，其中 $t>k$。由上式，

所以 D 在下一状态中成立。

5. 证明 E 在下一状态中成立

取下一状态中的两个相等相邻对：

和

其中

我们要证明

情形 1：两个相等对都是旧相等对

它们在原状态中也是两个相等相邻对，并且相对顺序不变。

由原状态的 E，直接得到

情形 2：低的相等对是新的，高的相等对是旧的

新的相等对由

和某条旧蛇 $u_k$ 构成。

因此这个新相等对的右端编号为

设高的旧相等对在原状态中为

这个旧相等对不含 $u_1$，所以

由原状态的 D，

下一状态中，这个旧高相等对的左端编号仍为 ${\iota }_t$。于是

所以 E 成立。

情形 3：低的相等对是旧的，高的相等对是新的

这种情况不可能。

因为新相等对的体力必为

而由原状态的 B，任意旧相等对的体力都严格大于 $\mathrm{\Delta }$。所以新相等对一定比所有旧相等对更弱，不可能作为高的相等对。

情形 4：两个相等对都是新的

这种情况也不可能，因为一步只插入一条新蛇 $v$，它至多参与一个相等相邻对；而 A 又保证不会出现三条同体力蛇。

因此 E 在下一状态中成立。

综上，A–E 对所有强制可达状态成立。

特别地，由 E 得到我们后面需要的核心结论：

若某个强制可达状态中

则取 E 中

得到

也就是说：

三、安全步与危险步

现在回到强制过程。

在状态

中，强制令最强蛇 $u_m$ 吃掉最弱蛇 $u_1$，得到新蛇

如果 $v$ 在下一状态中不是最弱蛇，称这一步为安全步。

如果 $m\ge 3$，且 $v$ 在下一状态中变成最弱蛇，称这一步为危险步。

当 $m=2$ 时，吃完只剩一条蛇，吃者必然存活，所以 $m=2$ 的步骤视为安全步。

四、安全步中的蛇一定会吃

我们证明：

若某一步是安全步，则当前最强蛇在理性游戏中一定会吃。

设当前状态为

当前最强蛇为 $u_m$，吃后变为

因为这一步是安全步，所以 $p$ 在下一状态中不是最弱蛇。

我们先证明一个保护性质：

在强制过程之后的演化中，在 $p$ 下一次成为最强蛇之前，$p$ 不会成为最弱蛇。

证明如下。

首先，安全步推出

否则若

则底部有相等对。由不变量 B，

于是

这说明新蛇 $p$ 比 $u_2$ 更弱，从而 $p$ 会成为最弱蛇，矛盾于安全步。

所以

现在看吃后状态。把除 $p$ 外的蛇分为两类：

即比 $p$ 弱的蛇；

即比 $p$ 强的蛇。

因为这是安全步，所以

若

则 $p$ 已经是最强蛇，结论显然成立。

下面假设 $H\ne \varnothing$。

我们证明如下性质会一直保持：

对任意

$$h=(X,\alpha )\in H,\ell =(Y,\beta )\in L,$$

都有

$$(X-Y,\alpha )\prec p.$$

初始时，$h,\ell$ 都是原状态中的旧蛇。于是

因此

所以

现在假设这个性质在某个时刻成立，且 $p$ 还不是最强蛇。

因为 $H\ne \varnothing$，当前最强蛇在 $H$ 中；因为 $L\ne \varnothing$，当前最弱蛇在 $L$ 中。

设当前最强蛇为

当前最弱蛇为

强制过程下一步会产生

由保持性质，

所以 $z$ 会进入 $L$，而不会跑到 $p$ 右侧。

接下来只需检查保持性质仍然成立。

对旧的 $h\in H\setminus \{h_{\ast }\}$ 和旧的 $\ell \in L\setminus \{{\ell }_{\ast }\}$，性质原本就成立。

只需检查新的弱蛇 $z$。取任意旧的

因为 $h_{\ast }$ 是当前最强蛇，所以

从而

于是

若

则

所以

若

则 ${\ell }_{\ast }$ 与 $p$ 体力相同，且 ${\ell }_{\ast }\prec p$。

此时 ${\ell }_{\ast },p$ 是当前状态中最弱的两条蛇。若上式出现等号，即

则必须有

于是 $h$ 与 $h_{\ast }$ 体力相同，并且它们是当前状态中最强的两条蛇。

由核心不变量，

所以即使体力相同，也有

因此保持性质成立。

于是，只要 $p$ 还没成为最强蛇，强制过程每一步都会把一条 $H$ 中的蛇变成 $L$ 中的蛇，而 $p$ 自己既不会成为最弱蛇，也不会被吃掉。

所以 $p$ 要么在某个时刻成为最强蛇，要么游戏在此之前停止；无论哪种情况，它都不会在此之前死亡。

现在回到理性游戏。

如果从吃后的状态开始，游戏在 $p$ 成为最强蛇之前停止，那么 $p$ 显然存活。

如果游戏进行到 $p$ 成为最强蛇的状态，那么轮到 $p$ 决策。根据题目规则，$p$ 只会在自己最终不会死亡时才吃；否则它拒绝并立即存活。

所以，在安全步中，当前最强蛇吃掉最弱蛇后一定最终存活。

因此理性地说，它一定会吃。

五、危险步会形成连续尾段

下面证明：

若某一步是危险步，则之后直到剩下 $3$ 条蛇为止，每一步都是危险步。

设某个强制状态为

设这一步是危险步。即最强蛇 $u_m$ 吃掉最弱蛇 $u_1$ 后，新蛇

成为下一状态中的最弱蛇。

于是

下一状态中，最强蛇是原来的 $u_{m-1}$，最弱蛇是 $v$。

强制下一步会令 $u_{m-1}$ 吃掉 $v$，得到新蛇

其体力为

由于

所以

若严格小于 $b_2$，则 $q$ 显然成为新的最弱蛇，所以下一步仍是危险步。

唯一需要处理的是等号情形。

等号成立当且仅当

也就是说，当前状态中前两条蛇体力相同，后两条蛇体力也相同。

由核心不变量，

而 $q$ 的体力等于 $b_2$，编号为 ${\iota }_{m-1}$。因此

所以即使体力相同，$q$ 仍然比 $u_2$ 更弱，仍会成为下一状态中的最弱蛇。

因此下一步也是危险步。

于是，一旦某个 $m\ge 4$ 的步骤是危险步，则 $m-1$ 的步骤也是危险步。

所以危险步若出现，必定形成一个连续尾段：

其中

表示强制过程中还有 $k$ 条蛇的状态。

注意 $S_2\to S_1$ 吃完只剩一条蛇，吃者必然存活，因此它视为安全步。

六、理性游戏中的决策

现在考虑真正的理性游戏。

强制过程给出一串状态

真正游戏只可能沿着这条强制路径走，直到某一步当前最强蛇拒绝为止。

记

表示：在状态 $S_m$ 中，当前最强蛇会吃。

我们已经证明：

若 $S_m\to S_{m-1}$ 是安全步，则

特别地，

因为吃完只剩自己。

现在考虑危险步。

若 $S_m\to S_{m-1}$ 是危险步，$m\ge 3$，则当前最强蛇吃完后会在 $S_{m-1}$ 中变成最弱蛇。

因此它是否能存活，完全取决于 $S_{m-1}$ 中的最强蛇是否吃：

• 若 $S_{m-1}$ 中的最强蛇吃，则它立刻被吃死；
• 若 $S_{m-1}$ 中的最强蛇拒绝，则游戏立即停止，它存活。

所以对于危险步，有

七、最终存活数量为奇数

分两种情况。

情况 1：强制过程中没有危险步

那么每一步都是安全步。

由安全步结论，每一步当前最强蛇都会吃。

于是游戏一直进行到只剩一条蛇。

最终存活数量为

是奇数。

情况 2：强制过程中存在危险步

设第一个进入危险尾段的状态是

也就是说：

全是危险步，而所有

都是安全步。

因此真正游戏一定会先走到 $S_h$。

在危险尾段中，有

且对 $3\le m\le h$，

所以

依此类推。

即：

因此：

若 $h$ 为奇数，则在 $S_h$ 中最强蛇拒绝，游戏停在 $h$ 条蛇，存活数为奇数。

若 $h$ 为偶数，则 $S_h$ 中最强蛇会吃，游戏进入 $S_{h-1}$。而 $h-1$ 为奇数，所以 $S_{h-1}$ 中最强蛇拒绝，游戏停在 $h-1$ 条蛇，存活数仍为奇数。

结论

无论强制过程中是否出现危险步，真正理性游戏结束时的存活蛇数量都一定为奇数。

因此原命题成立：