两堆规模可变的Nim变种游戏必胜策略问询

别慌，这个变种Nim游戏的规则初看有点绕，但其实必胜策略的规律非常清晰，我一步步给你拆解明白：

首先先把规则再明确一遍，避免理解偏差：

游戏开始时有两堆石子，规模分别为n和m。两名玩家轮流操作：每回合玩家必须先选择其中一堆完全移除，再把剩下的那一堆拆分成两个非空堆（不需要相等）。如果玩家无法完成有效操作（也就是移除任意一堆后，剩下的堆没法拆成两个非空堆——说白了就是剩下的堆大小是1），那这名玩家输掉游戏。

核心状态分类（博弈论里的P/N态） #

我们把游戏状态分成两类：

• 必败态（P-position）：当前轮到操作的玩家，不管怎么选，最终都会输掉游戏；
• 必胜态（N-position）：当前轮到操作的玩家，存在至少一种操作方式，能让对手陷入必败态，从而自己获胜。

规律推导与证明 #

先从最小的状态入手找规律，再用归纳法验证：

1. 基础状态(1,1)：不管移除哪一堆，剩下的都是1，没法拆分，所以当前玩家无法操作直接输，这是必败态。
2. 状态(1,2)：玩家可以移除1，把2拆成(1,1)，留给对手必败态，所以这是必胜态。
3. 状态(1,3)：玩家只能移除1，把3拆成(1,2)（必胜态），所有操作都留给对手必胜机会，所以这是必败态。

以此类推，我们可以归纳出一个核心规律：

一个状态(a,b)是必败态，当且仅当a和b都是奇数

用数学归纳法可以严谨证明这个规律：

• 归纳假设：所有石子总数小于a+b的状态，都符合“双奇必败，其余必胜”的规律。
• 归纳步骤：
  • 若a和b都是奇数：移除任意一堆后，剩下的是奇数堆，拆分奇数堆只能得到一奇一偶的两个堆（因为奇数=奇数+偶数），而一奇一偶是必胜态，所以当前状态所有操作都指向必胜态，因此是必败态。
  • 若a和b不都是奇数（至少一个偶数）：玩家可以移除奇数堆（若一奇一偶）或任意一个偶数堆（若双偶），然后把剩下的偶数堆拆成两个奇数堆（比如拆成1和“堆大小-1”，偶数-1是奇数），这样留给对手的就是双奇的必败态，因此当前状态是必胜态。

具体必胜策略 #

根据上面的规律，直接对应到你的初始状态(n,m)：

• 如果n和m都是奇数：先手玩家处于必败态，无论怎么操作，后手都能通过调整让你再次陷入必败局面，最终输掉游戏；
• 如果n和m不都是奇数（至少一个偶数）：先手玩家处于必胜态，具体操作步骤是：
  1. 选择移除其中的奇数堆（如果是一奇一偶的情况），或者任意一个偶数堆（如果是双偶的情况）；
  2. 把剩下的那个偶数堆拆分成两个奇数堆（比如拆成1和堆大小-1，简单直接）；
  3. 之后每回合，对手操作后都会把局面变成一奇一偶的必胜态，你重复上述步骤，直到最后留给对手(1,1)的必败态，对手无法操作，你获胜。

举个例子：初始状态是(4,3)（一偶一奇），先手可以移除3，把4拆成(1,3)（两个奇数），后手面对(1,3)必败态，不管后手怎么操作，比如移除1拆3成(1,2)，你再移除1拆2成(1,1)，后手输。

备注：内容来源于stack exchange，提问作者stack122adam