偶数组合游戏：两堆硬币博弈规则及技术问询

让我们来拆解这个硬币博弈问题，先把规则明确，再一步步分析胜负策略：

我们有两堆初始数量为$X$、$Y$（均>0）的硬币，两名玩家轮流操作，每回合的操作规则是：

• 选择其中一堆硬币，取出偶数数量$K$（$K≥2$且不超过该堆硬币总数）
• 将$K$的一半放回另一堆（未被选择的堆），另一半直接移出游戏
• 无法进行合法操作的玩家输掉游戏

博弈类问题的关键是找到必败态（P-position）和必胜态（N-position）：

• 必败态：当前玩家无论怎么操作，都会让对手进入必胜态
• 必胜态：当前玩家存在至少一种操作，能让对手进入必败态

通过枚举小规模状态+数学归纳法，我们可以总结出清晰的胜负规律：

规律结论 #

• 必败态：当两堆硬币数量的差的绝对值≤1时，当前玩家处于必败态
• 必胜态：当两堆硬币数量的差的绝对值≥2时，当前玩家处于必胜态

归纳证明 #

基础步骤 #

当$X,Y$都≤2时，枚举所有状态均符合规律：

• (1,1)、(1,2)、(2,2)：差的绝对值≤1，均为必败态
• (2,0)、(0,2)：差的绝对值=2>1，均为必胜态

归纳假设 #

假设对于所有满足$a + b < n$的状态$(a,b)$，都符合“差≤1为必败态，差>1为必胜态”的规律。

归纳步骤 #

考虑状态$(X,Y)$，其中$X+Y = n$，不妨设$X ≥ Y$：

1. 若$X-Y ≤1$（必败态）：
   所有合法操作后的状态都会变成差>1的必胜态：

   • 从$X$堆取偶数$k$，新状态差为$(X-k)-(Y+k/2)=(X-Y)-(3k/2)$，因$k≥2$，差≤1-3=-2，绝对值>1
   • 从$Y$堆取偶数$k$，新状态差为$(X+k/2)-(Y-k)=(X-Y)+(3k/2)$，因$k≥2$，差≥0+3=3>1
     因此当前状态为必败态。

2. 若$X-Y ≥2$（必胜态）：
   总能找到合法操作让新状态差≤1（必败态）：

   • 比如当$X-Y=2$：从$X$堆取$k=2$，新状态为$(X-2,Y+1)=(Y,Y+1)$，差=1
   • 当$X-Y=5$：从$X$堆取$k=4$，新状态为$(X-4,Y+2)=(Y+1,Y+2)$，差=1
     核心思路是通过调整取出的偶数$K$，让操作后的两堆数量差回到≤1的范围，把必败态抛给对手。

比如初始状态为$(5,1)$（差=4≥2，必胜态）：

1. 当前玩家从第一堆取2个硬币，新状态变为$(5-2,1+1)=(3,2)$（差=1，必败态）
2. 对手只能从3的堆取2个，新状态变为$(1,2+1)=(1,3)$（差=2≥2，必胜态）
3. 当前玩家再从3的堆取2个，新状态变为$(1+1,1)=(2,1)$（差=1，必败态）
4. 对手无论怎么操作，都会再次让当前玩家回到必胜态，直到对手无法操作输掉游戏

内容的提问来源于stack exchange，提问作者mkh