Brain Teaser 两则 | VariantConst

type

status

date

slug

summary

玩家 A 和玩家 B 玩一个填数游戏。对于减式，每个可以填入一个之间的整数。每一轮总是 A 先举出一个整数，然后由 B 填入其中的一个中。假设 A 和 B 都是理性人，A 希望最大化减式的计算结果，而 B 希望最小化之。问两人的最优策略和对应的减式计算结果。

假设 A 举出，考虑 B 的应对策略：

因为 B 希望最小化计算结果，因此，当即时，B 把填到左边；否则，B 把填到右边。不管哪种情形下，计算结果都是。

回到 A 的视角，既然不管 A 出什么数，结果都是，那么 A 会选择，此时取得最大值。

小结：对于一位数的情形，A 的最优策略是出或。B 的最优策略是 A 出时 B 把它首先填到左边，否则首先填到右边。对应的计算结果是。

对于的情形，我们发现，这种情形可以看成是两个小游戏的叠加，只不过这一组游戏的收益权重是的倍。根据情形中的讨论，（目前只是合理地猜测）A 只会出或。

为什么 A 选定了之后，就只能一直出这个数了呢？因为如果 A 出了任何一个比小的数（以为例），B 都会把它填到最左边的红框，即，那么 A 下面只能一直出，最多拿到的结果；如果 A 出了任何一个比大的数（以为例），B 都会把它填到最右边的红框，即，那么 A 下面只能一直出，最多拿到的结果。

对于的情形，A 的最优策略是一直出或，直到 B 填了某个，然后依据具体情况一直出或。B 的最优策略是首先把 A 出的数填满所有，最后只剩下两个最高位时，按照情形的策略继续。对应的计算结果是。

一只蚂蚁要从起点 A 前往终点 B，AB 距离为，要求：
蚂蚁只能恰好走步，且每一步都只能走直线段；
蚂蚁和终点 B 之间的距离必须严格递减。
问蚂蚁从起点走到终点，最长的路径长度是多少？

考虑只走 步的情形。此时必须直接前往终点，最长路径长度是。

考虑走 步的情形。假设蚂蚁途径点为，则一定有，即第一步的路径一定与以终点为圆心、为半径的圆相切。这是题目要求的自然推论，不难证明。

此时路径长度为

当时，路径长度取得最大值。

考虑走 步的情形。假设蚂蚁途径各点分别为，则一定有。下图显示了的情形。

此时路径长度为

用数学归纳法可证明步情形下最长路径长度为。故时，最长路径长度为。