威佐夫博弈(Wythoff‘s Game)
1. Beatty 定理
设 无理数 \(r\) 对应的 Beatty 数列 \(B_r\) 为 \((B_r)_i=\lfloor i\times r\rfloor\)。
定理:若无理数 \(r,s\) 满足 \(\frac 1 r+\frac 1 s=1\),则 \(B_r,B_s\) 为 \(\mathbb{N_+}\) 的一个划分。
证明:
考虑数列 \(C_r,C_s\) 满足 \((C_r)_i=\frac i r,(C_s)_j=\frac j s\)。
首先 \(C_r,C_s\) 没有相同元素。设 \((C_r)_i=(C_s)_j\),则 \(\frac i r=\frac j s\Rightarrow \frac i j=\frac r s=r-1\),一边是无理数,一边是有理数,矛盾。
然后将 \(C_r,C_s\) 合并后升序排序得到 \(C\)。
考虑 \((C_r)_i\) 在 \(C\) 中的位置,前边的元素中 \(C_r\) 占 \(i\) 个,\(C_s\) 占 \(\lfloor \frac{is}{r}\rfloor=\lfloor i(s-1)\rfloor\) 个,共 \(\lfloor is \rfloor\) 个。
然后考虑 \((C_s)_j\),同理得前面有 \(\lfloor jr\rfloor\) 个元素。又由于 \(C\) 是无限序列,于是 \(B_r,B_s\) 为 \(\mathbb{N_+}\) 的划分。得证。
2. Wythoff 博弈
有两堆石子,分别有 \(x,y\) 个。两人轮流行动,可以选择一堆拿走一些石子,或选择从两堆中同时拿走相同数量的石子,不能行动则判负。判断是否先手必胜。
观察:若 \((x,y)\) 是必败态,则 \((x+i,y),(x,y+i),(x+i,y+i)\) 都是必胜态。
定理 1:若 \((x,y)\) 是必败态,则 \((y,x)\) 也一定是必败态。
证明: \(x=0,y=0\) 时一定成立。
当 \(x\ne 0,y\ne 0\) 时,数学归纳法,假设定理对 \(x'\le x\land y'\le y\land (x',y')\ne(x,y)\) 的 $(x',y') $ 成立。
假设 \((y,x)\) 不是必败态。设 \((y,x)\) 可以走到的一个必败态为 \((y',x')\),\((x',y')\) 满足归纳条件,那么 \((x',y')\) 也是必败态。
而 \((x,y)\) 一定能走到 \((x',y')\) ,则 \((x,y)\) 为必胜态,矛盾。
所以接下来只讨论 \(x>y\) 的部分,另一部分是对称的。
定理 2:设 \((x_i,y_i)\) 为 \(x\) 第 \(i\) 大的必败态。则 \(x_i={\rm mex}\{x_j,y_j|(j<i)\},y_i=x_i+i\)。
证明:
若 \(x<{\rm mex}\{x_j,y_j|(j<i)\}\),则 \(x\) 一定在 \(\{x_j,y_j|(j<i)\}\) 中。
- 若存在 \(x_j=x_i\),则 \((x_i,y_i),(x_j,y_j)\) 一定有其一不是必败态,矛盾。
- 若存在 \(y_j=x_i\),则 \((y_j,x_j)\) 也是必败态,同理得出矛盾。
若 \(y_i<x_i+i\),设 $y_i=x_i+j $。前面一定有一个 \((x_j,x_j+j)\),则 \((x_i,x_i+j)\) 为必胜态,矛盾。
而 \((x_i,x_i+i)\) 确实是一个必败态:走不到任意一个前面的必败态。
所以 \(\{x_i\},\{y_i\}\) (除去 $(0,0) $)是 \(\mathbb{N_+}\) 的划分。
定理 3:设 \(\phi=\frac{\sqrt{5}+1}{2}\),则 \(x_i=\lfloor \phi i\rfloor,y_i=\lfloor (\phi+1)i\rfloor\)。
尝试构造两个 Beatty 序列 \(B_x,B_y\) 满足限制:
\(\frac 1 a+\frac 1 b=1,\lfloor a\times i \rfloor+i=\lfloor b\times i\rfloor\)。联立得 \(\frac 1 a+\frac 1 {a+1}=1\),得 \(a=\frac{\sqrt{5}+1}{2}\)。
定理 4:\((x,y)\) 为必败态,当且仅当 \(x=\lfloor\phi(y-x) \rfloor\)。