杂题01

allenchoi · 2024-11-10 12:14:50 · 学习·文化课

前言：

周六刚从学校逃出来，在初中班群看到有人发了道博弈题。颅内狂想无果，回家打了份代码找到结论，后面又花了整整一小时证明，宋完了。

题目描述：

有 n 个石子，甲乙两人轮流取，甲第一次可以任取但不能取完，之后每一次取的石子数不能超过前一次的两倍，求最优策略。

正解：

令 f 为斐波那契数列 2,3,5,8,13...

必胜策略存在性证明：

有如下两条结论：

1.若 n 为某斐波那契数 f_i，则先手必败。
2.设 l_i 表示有 f_i 个石子时，后手在最优策略下最后一次取走的石子个数，则 l_i\le f_{i-1}。

考虑归纳证明。
当 i\le 2 时命题显然成立；
当 i>2 时，假设命题在 i-1,i-2 时成立。
假设先手第一步取走石子个数为 x，剩余石子数为 y=f_i-x。
若 x\ge f_{i-2}，则 y\le f_i-f_{i-2}=f_{i-1}\le2f_{i-2}\le2x，那么剩余的石子可以一次取完，此时 l_i=y\le f_{i-1}。

若 x<f_{i-2}，那么后手可以套用 i-2 时的策略，使得自己可以取走前 f_{i-2} 个石子中的最后一个。由于 2l_{i-2}\le 2f_{i-3}<f_{i-1}，所以剩余的 f_{i-1} 个石子先手不能一次取完，那么再套用 i-1 时的策略即可。此时 l_i=l_{i-1}\le f_{i-2}<f_{i-1}。

证毕。

由此，我们还可以得出，对于非斐波那契数的 n，先手必胜，证明如下：
设 i=\min\limits_{f_j>n}j，则 n>f_{i-1}=f_i-f_{i-2}，因此此时的局面相当于上一步后手在 n'=f_i 的时候取走了 f_i-n<f_{i-2} 个石子，那么先手可以套用上文中第二种情况的策略，必胜。
证毕。

刻画必胜策略：

设当前玩家剩余 n 个石子（n 为非斐波那契数），上一个玩家操作前剩余 f_i 个石子，（初始时令 i=\min\limits_{f_j>n}j），令 x=f_i-n。
由上文的证明，我们可以设计一个函数 g(i,x) 表示当前玩家的最优策略。
不难写出转移式：

进一步地，令 k=\max\limits_{i\equiv j\pmod{2} \land x\ge f_{j-2}}j，g(i,x) 即当前最优策略为 f_k-x。

End

感谢观看。