文章摘要
Deepseek-v3.2

一、巴什博奕（Bash Game）类

例题1（基础）

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

解析：

  • 可控和 。
  • ，余数1。
  • 先手取1颗，剩余20（5的倍数），之后对方取颗，我方取颗。
  • 必胜。

例题2（取最后一颗输）

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

解析：

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

二、威佐夫博奕（Wythoff Game）

例题3

两堆石子，一堆10个，一堆15个，两人轮流取，可以：

  1. 从一堆取任意个；
  2. 从两堆同时取相同个数。
    取到最后一颗者胜。问先手策略。

解析：

  • 威佐夫博奕：必败态为 ，其中 ，，。
  • 判断 ：，。
  • 是必败态， ⇒ 先手必胜。
  • 策略：从15中取2个，变成 ，再计算 ，不对。正确做法：
    • 差 ，检查 ，所以要把10减少到8，15减少到13 ⇒ 从两堆各取2个 ⇒ 必败态。
  • 先手从两堆各取2个。

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

例题4（三堆普通Nim）

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

解析：

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

例题5（限制取法上限）

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

解析：

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

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

例题6

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

解析：

  • 必败态是斐波那契数：
  • 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移动减少中间空格数1~3，B移动也减少中间空格数1~3。
  • 等效于98颗石子，每次取1~3颗，取最后一颗胜。
  • ，余数2 ⇒ 先手A取2格（即A从1走到3），中间空格96（4的倍数），之后对方取a格，我方取4-a格。
  • A第一步走到位置3。

七、Green Hackenbush（树上删边）

例题9

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

解析：

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

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