数学博弈 | guangzhou

文章摘要

Deepseek-v3.2

一、巴什博奕（Bash Game）类

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

解析：

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

解析：

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

解析：

威佐夫博奕：必败态为 $(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)$ $(10, 13)$ ，再计算 $k=3, a_3=4$ $k = 3, a_{3} = 4$ ，不对。正确做法：
- 差 $d=5$ ，检查 $a_5=8$ ，所以要把10减少到8，15减少到13 ⇒ 从两堆各取2个 ⇒ $(8,13)$ 必败态。
先手从两堆各取2个。

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

解析：

三堆：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颗。

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

解析：

在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），总能移动。
先手必胜。

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

解析：

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

解析：

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

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