文章摘要
Deepseek-v3.2

一、巴什博奕（Bash Game）类

例题1（基础）

有21颗石子，两人轮流取，每次取1~4颗，取到最后一颗者胜。问先手必胜策略。

解析：

  • 可控和 m + 1 = 5。
  • 21 ÷ 5 = 4⋯1，余数1。
  • 先手取1颗，剩余20（5的倍数），之后对方取a颗，我方取5 − a颗。
  • 必胜。

例题2（取最后一颗输）

30颗石子，每次取1~3颗，取到最后一颗的人输。问先手策略。

解析：

  • 取最后一颗输 ⇒ 转化为29颗石子取最后一颗胜。
  • 29 ÷ 4 = 7⋯1。
  • 先手取1颗，剩余28（4的倍数），之后对方取a颗，我方取4 − a颗，最后对方取最后一颗输。
  • 必胜。

二、威佐夫博奕（Wythoff Game）

例题3

两堆石子，一堆10个，一堆15个，两人轮流取，可以： 1. 从一堆取任意个； 2. 从两堆同时取相同个数。 取到最后一颗者胜。问先手策略。

解析：

  • 威佐夫博奕：必败态为 (ak, bk)，其中 ak = ⌊kφ⌋，bk = ak + k，。
  • 判断 (10, 15)：k = b − a = 5，a5 = ⌊5φ⌋ = ⌊8.09⌋ = 8。
  • (8, 13) 是必败态，(10, 15) ≠ (8, 13) ⇒ 先手必胜。
  • 策略：从15中取2个，变成 (10, 13)，再计算 k = 3, a3 = 4，不对。正确做法：
    • 差 d = 5，检查 a5 = 8，所以要把10减少到8，15减少到13 ⇒ 从两堆各取2个 ⇒ (8, 13) 必败态。
  • 先手从两堆各取2个。

三、尼姆博奕（Nim Game）及其变种

例题4（三堆普通Nim）

三堆：3、5、7颗，每次从一堆取任意个，取最后一颗胜。

解析：

  • 3 ⊕ 5 ⊕ 7 = 1，非零 ⇒ 先手必胜。
  • 找一步使异或为0：设 s = 1，看7：7 ⊕ 1 = 6，从7取到6（取1颗）。
  • 新局面 (3, 5, 6)：3 ⊕ 5 = 6，6 ⊕ 6 = 0。
  • 先手从7颗堆取1颗。

例题5（限制取法上限）

三堆：3、4、5颗，每次从一堆取至少1颗，最多3颗，取最后一颗胜。

解析：

  • 这是受限Nim，用 Grundy数。
  • 单堆Grundy数：g(0) = 0，g(n) = mex{g(n − 1), g(n − 2), g(n − 3)}（对于n≥1）。
  • 计算：
    • g(0) = 0
    • g(1) = mex{g(0)} = mex{0} = 1
    • g(2) = mex{g(0), g(1)} = mex{0, 1} = 2
    • g(3) = mex{g(0), g(1), g(2)} = mex{0, 1, 2} = 3
    • g(4) = mex{g(1), g(2), g(3)} = mex{1, 2, 3} = 0
    • g(5) = mex{g(2), g(3), g(4)} = mex{2, 3, 0} = 1
  • 局面Grundy值：g(3) ⊕ g(4) ⊕ g(5) = 3 ⊕ 0 ⊕ 1 = 2 ≠ 0 ⇒ 先手必胜。
  • 找一步使异或为0：需改变一堆使其Grundy值等于当前异或值2。
    • 3颗堆：g(3) = 3，不能变成2（取法受限）。
    • 4颗堆：g(4) = 0，要变成2，但g(k) = 2 ⇒ k = 2，从4取2颗 → 允许。
    • 验证：新局面 (3, 2, 5)：g(3) = 3, g(2) = 2, g(5) = 1，异或 3 ⊕ 2 ⊕ 1 = 0。
  • 先手从4颗堆取2颗。

四、斐波那契博弈（Fibonacci Nim）

例题6

一堆n=100个石子，先手第一次可取1~n-1个（不能全取），之后每人取数不超过上一人的2倍，取最后一颗胜。

解析：

  • 必败态是斐波那契数：n = 2, 3, 5, 8, 13, 21, 34, 55, 89, ...
  • 100不是斐波那契数，先手必胜。
  • 策略：取成最近≤n的斐波那契数。
  • 100 - 89 = 11，先手取11颗，剩89（必败态）给对方。
  • 先手取11颗。

五、对称策略类

例题7（棋盘上的对称）

在8×8棋盘左上角放一枚棋子，两人轮流移动，每次可向右、向下或向右下移动任意格，不能移动者输。

解析：

  • 这是一个对称博弈。
  • 先手必胜：先手第一步向右下移动1格到(1,1)。
  • 之后对方任何移动从(x,y)到(x’,y’)，先手都从(x’,y’)移动到(x,y)的对称位置（具体是(7-x’,7-y’)? 不对，应该是中心对称点）。
  • 更简单：第一次走到主对角线对称点(1,1)，之后对方走任何(a,b)，你先手走(b,a)到对称位置（如果规则允许），这里规则是右/下/右下，所以用对主对角线的对称策略。
  • 实际必胜策略：第一步到(1,1)，之后对方到(p,q)，你到(q,p)（若p≠q），总能移动。
  • 先手必胜。

六、数学归纳法 / 奇偶性类

例题8

在1×100棋盘两端各放一枚棋子A、B，A先手，每次可移动自己棋子向右1~3格，不能越过对方，不能不动。无法移动者输。

解析：

  • 初始位置A在左端1，B在右端100。
  • 中间空格数98。
  • 每次A移动减少中间空格数13，B移动也减少中间空格数13。
  • 等效于98颗石子，每次取1~3颗，取最后一颗胜。
  • 98 ÷ 4 = 24⋯2，余数2 ⇒ 先手A取2格（即A从1走到3），中间空格96（4的倍数），之后对方取a格，我方取4-a格。
  • A第一步走到位置3。

七、Green Hackenbush（树上删边）

例题9

地面连接若干根线段的图，两人轮流删一条边，删掉与地面不连通的部分随之消失，不能删者输。

解析：

  • 用Colon Principle：一根长n的链的Grundy值 = n。
  • 某点合并多个链：Grundy值 = 各链Grundy值的异或。
  • 计算整个图的Grundy值，非零则先手胜。
  • 例：地面连接两根链，长3和5：Grundy= 3 ⊕ 5 = 6，非零，先手胜。先手可使3变成1（取2），新Grundy 1 ⊕ 5 = 4，再一步可到0。

这些例题覆盖了常见的博弈类型，每种都有独特的解题思路和技巧，适合系统学习和训练。