数学博弈

一、巴什博奕（Bash Game）类

例题1（基础）

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

解析：

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

---

例题2（取最后一颗输）

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

解析：

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

---

二、威佐夫博奕（Wythoff Game）

例题3

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

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

解析：

• 威佐夫博奕：必败态为 $(a_k, b_k)$，其中 $a_k = \lfloor k \varphi \rfloor$，$b_k = a_k + k$，$\varphi = \frac{1+\sqrt{5}}{2}$。
• 判断 $(10,15)$：$k = b-a = 5$，$a_5 = \lfloor 5\varphi \rfloor = \lfloor 8.09\rfloor = 8$。
• $(8,13)$ 是必败态，$(10,15) \neq (8,13)$ ⇒ 先手必胜。
• 策略：从15中取2个，变成 $(10,13)$，再计算 $k=3, a_3=4$，不对。正确做法：
  • 差 $d=5$，检查 $a_5=8$，所以要把10减少到8，15减少到13 ⇒ 从两堆各取2个 ⇒ $(8,13)$ 必败态。
• 先手从两堆各取2个。

---

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

例题4（三堆普通Nim）

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

解析：

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

---

例题5（限制取法上限）

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

解析：

• 这是受限Nim，用 Grundy数。
• 单堆Grundy数：$g(0)=0$，$g(n) = \text{mex}\{g(n-1), g(n-2), g(n-3)\}$（对于n≥1）。
• 计算：
  • $g(0)=0$
  • $g(1)=\text{mex}\{g(0)\} = \text{mex}\{0\} = 1$
  • $g(2)=\text{mex}\{g(0),g(1)\} = \text{mex}\{0,1\} = 2$
  • $g(3)=\text{mex}\{g(0),g(1),g(2)\} = \text{mex}\{0,1,2\} = 3$
  • $g(4)=\text{mex}\{g(1),g(2),g(3)\} = \text{mex}\{1,2,3\} = 0$
  • $g(5)=\text{mex}\{g(2),g(3),g(4)\} = \text{mex}\{2,3,0\} = 1$
• 局面Grundy值：$g(3) \oplus g(4) \oplus g(5) = 3 \oplus 0 \oplus 1 = 2 \neq 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\oplus 2\oplus 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移动减少中间空格数1_{3，B移动也减少中间空格数1}3。
• 等效于98颗石子，每次取1~3颗，取最后一颗胜。
• $98 \div 4 = 24 \cdots 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 \oplus 5 = 6$，非零，先手胜。先手可使3变成1（取2），新Grundy $1 \oplus 5 = 4$，再一步可到0。

---

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