巴什博弈 与 威佐夫博弈 与 动态 k 倍减法
__staring__
·
2024-12-15 19:19:27
·
算法·理论
若以下内容出现了谬误，烦请私信我进行指正，以及可私信提问。
问题一 (巴什博弈)
有一堆石子，石子数为 n ，先手 A 和后手 B 轮流取，每次取 [1,k] 内的整数个石子，无法操作的人判负，问什么情况下先手必胜，或先手必败。
显然我们知道答案为，当且仅当 (k+1) \nmid n 先手必胜，否则先手必败。
这是因为我们遇见过这道题，但假使我们没见过，我们也可以从头推出这个结论。
记 f(n) 表示 n 个石子时胜负情况，即 f(n)=1 代表先手必胜，f(n)=0 代表先手必败。
显然 f(0)=0 ，这是游戏的边界情况。
$f(2)=1$ ，当先手取一个石子时必败，取两个石子时必胜，显然先手应该取两个石子。
$f(3)=1$ ，同上，先手应该取三个石子。
可以发现，当 $n \in [1,k]$ 时，先手总是可以一次取完，即 $f(n)=1$ 均成立。
而当 $n=k+1$ 时，先手无法再一步取完，此时局面变成后手操作，剩下的石子数 $n'=n-x \in [1,k]$ ，而我们有 $f(n')=1$ ，因此后手必胜，即先手必败。
当 $n \in [k+2,2k+1]$ 时，先手又可以一步取走 $n \bmod (k+1)$，使得 $n'=k+1$ ，把必败态转到后手，自己必胜。
那么同上可知，$f(n)=1$ 当且仅当 $\exist i \in [1,k],f(n-i)=0$ ，或者 $f(n)=0$ 当且仅当 $\forall i \in [1,k],f(n-i)=1$ ，以及边界情况 $f(0)=0$。
那么我们就能推出 $f(n)=0 \Leftrightarrow (k+1) \mid n$。
同时，先手的策略应是每次取走 $n \mod (k+1)$ 个石子。
# 问题二 (威佐夫博弈)
> 有两堆石子，石子数为 $a,b$ ，先手 A 和后手 B 轮流取，每次可以单独取一堆中的任意石子数，或是两堆同时取相同石子数，无法操作的人判负，问什么情况下先手必胜，或先手必败。
根据问题一的推导过程，我们可以记 $f(a,b)$ 表示先手的胜负情况，边界为 $f(0,0)=0$。
同时根据问题一的结论，我们有 $f(a,b)=1$ 当且仅当，$\exist x \leq a,f(a-x,b)=0$ 或 $\exist x \leq b,f(a,b=x)=0$ 或 $\exist x \leq \min(a,b),f(a-x,b-x)=0$。
写出式子似乎不太好观察，那我们把 $f$ 搬到平面上，第 $a$ 行 $b$ 列的元素代表 $f(a,b)$ 的值，比如下面的 excel。
那么 $f(a_0,b_0)$ 的前驱，即计算 $f(a_0,b_0)$ 的值需要的点，应该在这样的红线上：
只要这三条线上出现了 $=0$ 的点，$f(a,b)=1$。
似乎还是不好计算，那么我们正难则反，考虑一个 $f(a,b)=0$ 的点会使哪些点 $=1$。
即蓝线上的点一定 $=1$ ，如上图中若 $f(3,1)=0$ 则 $f(5,3)=1$。
那么现在的情况似乎就简单一些了，我们从边界 $f(0,0)=0$ 开始，把蓝线上的点删掉，并将当前一定不会再被删掉点加入。
即初始：
接下来把 $f(1,2)$ 和 $f(2,1)$ 覆盖：
之后是 $f(3,5)$ 和 $f(5,3)$：
以此类推。
显然地，我们发现，每行每列只会有一个星，并且整个平面呈轴对称，那我们只考虑这些星星的一半，即 $f(a,b)=0,a<b$ 的点。
根据图片且自己推导可以得到前几个点是 $(0,0),(1,2),(3,5),(4,7),(6,10),(8,13)$。
发现似乎有些规律，其中可以看图且比较易证的有：$a_i$ 递增，$b_i$ 递增，$b_i-a_i=i$，$i \le a_i \le 2i$。
以及实际上，我们有 $a_i = \operatorname{mex} ( \bigcup_{j=1}^{i-1} \{a_j,b_j\})$ ，这也是易证的。
那么我们已经可以递推出所有项了，但我们还可以继续探究增长率。
对于第 $k$ 行，由于 $k \le a_k \le 2k$ ，那么当 $k \rightarrow \infty$ 时，$a_k$ 与 $k$ 应该呈正比例，那么我们设 $a_k=\phi k$。
同时因为 $b_i$ 递增，总存在一个最大的 $t$ 使得 $b_t<a_k$ 且 $b_{t+1}>a_k$ ，同时此时 $b_t \sim a_k$。
那么，我们有 $a_k=\phi k=k+t,\phi t+t=b_t=\phi k$ ，可以得到 $\phi^2-\phi-1=0$ ，由于 $\phi >0$ ，显然我们应取 $\phi = \frac {1+\sqrt5} {2}$。
这是个无理数，但我们的点集为整数，那么肯定差了一部分，显然应该不是常数，那么我们猜测是取整函数。
具体来说，由于 $\phi>1$ ，那么我们有 $\lfloor \phi k \rfloor$ 互不相同，而上取整和四舍五入由于 $\phi$ 是无理数本质相同，所以应该有 $a_k=\lfloor \phi k \rfloor$。
那么我们也就有 $b_k=\lfloor (\phi+1)k \rfloor$，显然这样生成的 $\{a\},\{b\}$ 内部互不相同，但一定满足 $\{a\} \cap \{b\} = \varnothing,\{a\} \cup \{b\}=\N^+$ 吗？（以下证明不考虑 $k=0$ 的特例）。
在证明之前，我们需要知道 $\frac {1} {\phi} + \frac {1} {\phi + 1} = 1$ ，这是显然的，读者可自行验证。
#### 1. $\{a\} \cap \{b\} = \varnothing
考虑反证，设正整数 x 满足 x \in \{a\} 且 x \in \{b\} ，那么一定存在正整数 m,n 满足 x < m\phi < x+1,x < n(\phi+1) < x+1 。
即 \frac{x}{\phi}<m<\frac{x+1}{\phi},\frac{x}{\phi+1}<n<\frac{x+1}{\phi+1} 。
由于 \frac {1} {\phi} + \frac {1} {\phi + 1} = 1 ，两式相加我们得到 x < m + n < x + 1 ，然而 x,m,n 都是正整数，所以一定不存在这样的 x 。
2. \{a\} \cup \{b\} = \N^+
同样考虑反证，设正整数 x 满足 x \notin \{a\} 且 x \notin \{b\} ，那么一定存在正整数 m,n 满足 \lfloor m\phi \rfloor < x < \lfloor (m+1)\phi \rfloor,\lfloor n(\phi+1) \rfloor < x < \lfloor (n+1)(\phi+1) \rfloor 。
由于 \phi 是无理数，所以有 m\phi < x < (m+1)\phi - 1 ，即 m < \frac{x}{\phi} < m+1-\frac{1}{\phi} 。
同理有 n < \frac{x}{\phi+1} < n+1-\frac{1}{\phi+1} ，两式相加得到 m+n < x < m+n+1 ，同样由于 x,m,n 都是正整数，所以不存在 x 。
实际上以上证明来自贝蒂定理 。
至此我们证明了，记 \phi = \frac{1+\sqrt5}{2} ，得到数列 a_i = \lfloor i\phi \rfloor,b_i = \lfloor i(\phi+1) \rfloor ，对于任意 x,y ，f(x,y)=0 当且仅当 \exist k,a_k=x 且 b_k=y 。
也即 f(x,y)=0 \Leftrightarrow \lfloor |y-x|\phi \rfloor = x 。
此时先手的操作策略为，每次在平面上将当前点移动到任意一个星处即可。
问题三 (动态 k 倍减法)
有一堆石子，石子数为 n ，先手 A 和后手 B 轮流取，第一次只能取 [1,n-1] 内的整数个石子，之后每个人取的石子数不超过上一个人的 k 倍，无法操作的人判负，问先手第一次应至少取多少石子才能保证必胜，或先手必败。
注意，k 可取小数。
（由于 k<1 的情况较为复杂，这里我们只讨论 k \ge 1 的情况）。
1. k=1
显然我们应从最简单的版本开始讨论。
类似地，我们记 f(n) 表示先手在 n 个石子时至少取多少个才能必胜，定义当 f(n)=n 时表示先手必败，于是我们可以抛弃掉第一次只能取 <n 个石子的限制。
稍微手推一下，我们应该有 f(1)=1,f(2)=2 ，以及 f(3)=1 ，f(0) 似乎应该等于 0 ，但我们将在下文具体讨论。
根据问题一的讨论，我们应用这样一个式子来描述先后手取石子的过程：
f(n) = \min \{ i \in [1,n] \mid f(n-i)>i\}
这表示，我们要找到一个最小的 i ，使得拿掉 i 个石子后，后手在 n-i 的局面下必胜需要的石子数严格超过 k=1 倍的先手取石子数。
以下的所有讨论，读者均可参考下图辅助理解：
根据式子，f(0) 应该定义为 +\infty 。
同样地，我们把满足 f(n)=n 的 n 取出组成序列 N ，应有 N=\{1,2,4,8,16,...\} ，我们猜测 f 与二进制有关，实际上可以归纳求出。
设当前已知 i \in [1,n] 的 f(i) 且 n \in N 且当前 N=\{2^k\} ，对于 i \in (n,n+\frac{n}{2}] 的点，根据递推式一定有 f(i)<n ，那么这与 (0,\frac{n}{2}] 的结构本质相同，即对于 \forall i \in (n,n+\frac{n}{2}],f(i) = f(i-n) 。
同理，对于 i \in (n+\frac{n}{2},n+\frac{n}{2}+\frac{n}{4}] ，有 f(i)<n+\frac{n}{2} ，与 (0,\frac{n}{4}] 本质相同，f(i)=f(i-n-\frac{n}{2}) 。
如此递归下去，直到 \frac{n}{2^k}=1 ，我们可以得到 \forall i \in (n,2n),f(i)=f(i-n) ，而 f(2n)=2n ，即 2n \in N 。
再根据初始 f(1)=1,1 \in N ，那么一定有 N = \{1,2,4,8,16,32,...\} ,f(n)=\operatorname{lowbit}(n) ，\operatorname{lowbit}(n) 指 n 在二进制下最低一位的权值。
有策略后我们也可反向证明策略的正确性，即将 n 按二进制分解后先手取走 \operatorname{lowbit}(n) ，此时后手只能取走 \le \operatorname{lowbit}(n) 的值，而在后手取走后一定又会生成一个新的 \operatorname{lowbit} ，且一定能被取走。
而当 n=2^k 时，由于先手无法取完，因此后手按照上述策略即可必胜，即先手必败。
即必胜策略为先手每次取走 f(n) 。
2. k=2
此时我们的递推式变为 f(n) = \min \{ i \in [1,n] \mid f(n-i)>2i\} 。
图为（画得太丑了请见谅 orz ）：
而 N = \{1,2,3,5,8,...\} ，我们猜测是 \text{Fibonacci} 数列，这也可以归纳证明。
设当前已知 i \in [1,n] 的 f(i) 且 n \in N 且 N=\text{Fib} ，记 pre(n) = \max\{ x \in N \mid 2x < n \},pre'(n) = \min\{ x \in N \mid 2x \ge n \} 。
我们知道 2pre(n)<n,2pre'(n) \ge n ，对于 i \in (n,n+pre(n)] 的点，根据递推式一定有 f(i)<n ，那么这与 (0,pre(n)] 的结构本质相同，即 \forall i \in (n,n+pre(n)],f(i) = f(i-n) 。
同理，对于 i \in (n+pre(n),n+pre(n)+pre(pre(n))] ，有 f(i)<n+pre(n) ，与 (0,pre(pre(n))] 本质相同，f(i)=f(i-n-pre(n)) 。
如此递归下去，直到 pre^c(n) \le 2 ，由 \text{Fib} 的性质我们知道 1+\sum_{i=1}^c pre^i(n)=pre'(n) ，可以得到 \forall i \in (n,n+pre'(n)),f(i)=f(i-n) ，而 f(n+pre'(n))=n+pre'(n) ，即 n+pre'(n) \in N 。
再根据初始 f(1)=1,f(2)=2,N=\{1,2\} ，那么一定有 N = \{1,2,3,5,8,13,21,...\} ,f(n)=\operatorname{lowbit}(n) ，\operatorname{lowbit}(n) 指 n 在 \text{Fib} 进制下最低一位的权值。
3. k \ge 1
此时递推式为 f(n) = \min \{ i \in [1,n] \mid f(n-i) > ki\} 。
初始有 N = [1,k] \cap \N ，我们从 \lfloor k \rfloor+1 开始枚举每个数，检查是否放入 N 中。
记当前数为 x ，类似 \text{Fib} 进制的，我们把 x 按当前 N 中的数进行分解，记 x_i 是分解出的从大到小第 i 个数，为了使先手取到 \operatorname{lowbit}(x) 后后手一定取不到 \operatorname{lowbit}(x') ，我们需要保证 x_i > kx_{i-1} ，如果不存在这样的分解就把 x 加入集合 N 。
显然，这样得到的 N 满足上述归纳过程的所有性质，也满足 f(n) = \operatorname{lowbit(n)} 。
实际上，N 还有另外一种生成方式，一样初始为 [1,k] ，每次 N \leftarrow N \cup \{\max(N) + pre'(\max(N))\} ，读者同样可类比 \text{Fib} 进制。
同时 \{ x \in N \mid x \le n\} 的集合大小为 O(\log n) 级别。
由于笔者很菜，以上性质这里暂不给出证明 orz。