Puzzle Toad-3 Take the last chip

Puzzle Toad-3 Take the last chip #

题目翻译 #

Turkey Sandwich 很担心即将到来的离散数学考试, 难以入睡. Turkey 一大早就被恶魔般的笑声唤醒了, 他看到一个顽皮的小矮人坐在床的尽头, 旁边是一堆看上去有无限多的薯条. 小矮人说: " Turkey 你好, 你愿意玩一个小游戏吗? 这堆薯条一共有 43546758343209876 个, 并且底部的薯条代表你永恒的灵魂. 游戏规则很简单, 第一个玩家拿走一些薯条, 但不能拿走全部的薯条. 之后我们轮流拿走一些薯条. 唯一的限制就是一个玩家拿走的薯条不能超过前一轮玩家拿走的薯条数. 拿走最后一个薯条的人获得胜利. 如果我赢了, 我就取走你的灵魂; 而如果你赢了, 你就会在考试中拿到 A . 你是要先手还是后手? " 对于 Turkey 来讲, 这似乎是一个合理的赌局. 你能够给 Turkey 一个策略, 让他能够应对任意薯条数的赌局吗? 如果上面这个问题对你来说太简单, 那么把规则修改成 “一个玩家拿走的薯条不能超过前一轮玩家拿走的薯条数的两倍” , 此时最优的策略是什么?

解答 #

这里先分别给出两个问题的解答, 再来看看原站给出的解答.

Q1 #

$n = 1$ 时, 游戏无法进行, 不作讨论. $n = 2$ 时, 先手只能拿走 $1$ 个, 后手必胜. $n$ 为奇数时, 先手只要拿走 $1$ 个就可以, 之后每轮玩家都只能拿走 $1$ 个, 最后一个由先手玩家拿走, 先手必胜. $n$ 为偶数时, 如果当前局面下剩余薯条数为偶数, 那么拿走奇数个一定是必败的, 因为这会使得对面进入到必胜局面. 所以双方每次不得不拿偶数个, 这等价于 $\frac{n}{2}$ 的情形. 如果 $n = 2^k$ , 那么等价于 $n = 2$ 的情形, 后手必胜; 否则等价于 $n$ 为奇数的情形, 先手必胜. 综上, $n = 2^k$ 时, 后手必胜; 其余情况先手必胜

Q2 #

Q2 是一个经典的博弈问题 " 斐波那契博弈 " . 我们来证明, 先手必胜当且仅当 $n$ 不是斐波那契数. 记斐波那契数列为 $f_1 = 1, f_2 = 2, f_3 = 5, …$ . $n = 1, 2$ 时同 Q1 .

后手必胜: n 为斐波那契数 #

假设 $\forall\ i\leq k$ , $n = f_i$ 均满足后手必胜. 考虑 $i = k + 1, n = f_{k + 1}$ 的情形. 此时, $n = f_{k - 1} + f_k$ . 假设先手取走的数量 $\geq f_{k - 1}$ , 则由于 $f_k < 2\times f_{k - 1}$ , 后手一次可以取走剩余所有薯条, 故先手第一次取走的数量应该 $< f_{k - 1}$ . 在这种情况下, 我们把 $n$ 个薯条看成两堆薯条 $f_{k - 1}$ 和 $f_{k}$ . 对于 $f_{k - 1}$ , 由归纳假设可知, 无论先手怎么取, 后手都能取到这一堆的最后一根. 记后手取最后一根时取走的薯条数为 $x$ , 则先手在 $f_{k}$ 堆第一次取至多取走 $2x$ 个, 由归纳假设可知, 如果 $2x < f_k$ , 即先手不能一次性取完 $f_k$ 堆时, 后手必胜. 所以我们下面来寻找 $x$ 的最大值. 由于 $x + \frac{x}{2} \leq f_{k - 1}$ , 有 $x\leq \frac{2}{3} f_{k - 1}$ . 由归纳法不难得到 $\frac{2}{3} f_{k - 1} < \frac{1}{2}f_k$ , 故 $2x < f_k$ 成立, 该情况下先手必败.

先手必胜: n 不为斐波那契数 #

先介绍一下齐肯多夫 (Zeckendorf) 定理: 任何正整数都可以表示成若干个不连续的斐波那契数之和, 这种表示方法可以由贪心算法 (每次选出最大可能的斐波那契数得到) . 对于 $n$ 不为斐波那契数的情况, 根据齐肯多夫定理, $n$ 可以写成 $f_{a_1}+ f_{a_2} + … + f_{a_p}$ , 其中 $a_i + 1 < a_{i + 1}$ . 先手先取完 $f_{a_1}$ 这一堆, 由于 $a_i + 1 < a_{i + 1}$ , 故后手至多取 $2\times f_{a_1} < f_{a_2}$ 个薯条. 前面已经证明了对于数量为斐波那契数的堆的博弈, 后手可以取到最后一根薯条, 因此本情形中 $a_2$ 堆的最后一根薯条由先手取到. 同理, 对于之后的每一个斐波那契堆, 整局的先手都是这一堆博弈中的后手, 可以取到最后一根薯条, 也可以取到整局游戏的最后一根薯条, 故先手必胜.

Puzzle Toad 给出的解答 #

一个通用的模型 #

让我们用下面这个形式来概括这个博弈问题: 有两个玩家 $A$ 和 $B$ , 并且 $A$ 先手. 给出一个单调不减的函数 $f: N\rightarrow N$ , 其中 $N$ 是正整数集合 ${1, 2, …}$ . 第一次行动中, $A$ 可以取走小于薯条总数的任意数量的薯条. 在之后一系列的行动中, 如果一个玩家取走了 $n$ 个薯条, 那么下一步中的玩家只能取走至多 $f(n)$ 个薯条. 因此, 本题实质上是 $f(n) = n$ 和 $f(n) = 2n$ 的特殊情况.

引理 #

定义一个集合 $\mathcal H = {H_1 = 1 < H_2 < …}$ 来表示先手必败的初始局势. 当然, 对于初始局势 $h\not \in \mathcal H$ , 先手必胜. 下面给出一个定理:

• 如果 $f(H_j)\geq H_j$ , 那么 $H_{j + 1} = H_j + H_l$ , 其中 $H_l = \underset{i\leq j}{min}{H_i\vert f(H_i) \geq H_j}$ .
• 如果 $f(H_j) < H_j$ , 则先手必败的局势有限, 并且终止于 $H_j$ .

本题的解答 #

根据这个定理, 我们可以得到:

• 对于 $f(n) = n$ 的博弈, $\mathcal H = {1, 2, 4, …, 2^k, …}$ .
• 对于 $f(n) = 2n$ 的博弈, $\mathcal H = {1, 2, 3, 5, …, f_k, …}$ , 其中 $f_k$ 为斐波那契数.

引理证明 #

接下来我们来证明这个定理. 假设 $f(H_j) \geq H_j$ , 那么 $H_l = \underset{i\leq j}{min}{H_i\vert f(H_i) \geq H_j}$ 一定存在. 对于任何先手必败态 $H_i < H_l$ , 都有 $f(H_i) < H_j$ . 所以对于 $H_j + H_i$ 的初始局面, 玩家 $A$ 可以先取走 $H_i$ 个薯条, 这样留给 $B$ 的就是 $H_j$ 的先手必败态, 所以 $H_j + H_i$ 就是一个先手必胜态. 考虑一个先手必胜态 $x < H_l$ . 对于 $H_j + x$ 的初始局势, 玩家 $A$ 总能找到一个策略取走前 $x$ 个石子的最后一个薯条, 并且最后一次取走的薯条数为 $y$ , 且满足 $f(y) < H_j$ . 这样操作后, 留给 $B$ 的局面就是初始为 $H_j$ 且无法一次性取走所有薯条的先手必败局面, 这对于 $A$ 来说就是一个先手必胜态. (玩家 $A$ 总是拥有这样的策略来保证 $f(y) < H_j$ . 因为假设对于某一个操作方案, $A$ 移走 $x$ 堆最后一根薯条时的一共取走 $y$ 个薯条, 有 $f(y) \geq H_j$ , 则 $y < H_l$ 必然是一个先手必胜态 (否则与 $H_l$ 的定义矛盾) . 此时 $A$ 只需要考虑在一堆数量 $y$ 的薯条中取走最后一根薯条时所取走的薯条个数 $y’$ . 通过这种迭代, $A$ 合法操作方案中取走 $x$ 堆最后一根薯条时取走的薯条个数 $y$ 是严格单调减的, 总能找到一种方案使得 $f(y) < H_j$) . 最后, 对于 $H_j + H_l$ 的初始局势, 如果 $A$ 第一次取走了至少 $H_l$ 根薯条, 因为 $f(H_l) \geq H_j$ , 此时 $B$ 可以一次性取走剩下的所有薯条从而获胜; 如果玩家 $A$ 取走的薯条数 $< H_l$ , 问题就转化成了我们前面探讨过的两种情况( $H_j + H_i$ 或 $H_j + x$ )之一 , 只不过先后手交换了, 这时 $B$ 作为新局势的先手, 自然是必胜的. 至此我们把引理的第一部分证明了, 接下来证明第二部分. 假设 $f(H_j) < H_j$ , 如果存在必败态 $H_{j + 1} = H_j + x, x > 0$ . 类似前文可知, $x$ 不能为某个必败态 $H_i$, 否则玩家 $A$ 先取走 $H_i$ 个薯条, 必然有 $f(H_i) \leq f(H_j) < H_j$ , 留给 $B$ 的是一个必败态 $H_j$ , 这与 $H_{j + 1}$ 为 $A$ 的必败态矛盾. 故 $x$ 只能是一个必胜态. 同样类似前文可知, 对于 $H_{j + 1}$ 的初始局势, $A$ 可以取走 $x$ 堆的最后一根薯条, 并且最后一次取走的个数 $y$ 满足 $f(y) < H_j$ , 留给 $B$ 一个必败态 $H_j$ , 这与 $H_{j + 1}$ 为 $A$ 的必败态矛盾. 故不存在 $H_{j + 1}$ .