第八十七讲 极值型游戏讲义-2026年高中数学竞赛

第八十七讲  极值型游戏

某些游戏问题中，含有参数或目标函数，寻求在正确的策略下取得最大或最小值， 这类问题是组合极值问题与游戏策略问题的融合，需要从两方面的策略加以论证，说明该值是最佳的。

例 1 阿里巴巴和四十大盗 要分一堆共 1987 枚金币。 先将这堆金币分成非空的两堆,接着 将其中一堆再分成非空的两堆,依次下去,直至 ,这样便产生了 41 个非空的金币堆。 取走其中最多的一堆, 接着取走剩下的最多的一堆,依次下去,直至 取走剩下两堆中较多的一堆,最后一堆留给阿里巴巴。对每个 ,试求 在不依赖其他人的策略下所能保证自己得到的金币个数。

解 对 只能保证至少得到 1 枚金币,因为另外 39 个强盗总可以制造出 39 堆只有 1 枚金币的金币堆。

可以保证至少得到 50 枚。 策略先分成两堆分别为 1 和 1986,剩余的人把 1986 分成 40 堆至少有一堆有 枚金币。另一方面,其他人也可设法不让 得到超过 50 枚金币。这只需 每人如果看到有一堆多于 50 枚金币,就从中分出一堆有恰好 50 枚金币, 否则就任意分。这样分成 41 堆均不超过 50 。

可以保证自己至少获得 26 枚金币。一方面其他的人有策略让 无法获得超过 26 枚金币。事实上 分成 1 和 1986。假设 将 1986 分成 。若 39，则剩下 38 个强盗将 分成 堆 1 枚金币，另从 中也分出一些 1，这样形成 40 堆 1 枚金币, 只拿到 1 枚金币。若 ,则剩下 38 个强盗将 尽量均分,由于 993，因此可分出第二多的堆不超过 枚金币。另一方面 也有策略使自己获得至少 26 枚金币。假设 先分成 两堆, 。设 。接着 从 中分出 枚金币,还剩下

若将 再分成不超过 39 堆,总有一堆不小于 26 。而要将 枚硬币分成每堆小于 26, 至少分 次,将 枚硬币分成若干堆,每堆小于 26,至少分 次,但是后面只有 38 次，故在 和 中至少还有一堆不小于 26，从而 可保证自己拿到 26 枚硬币。

例 2 甲、乙两人玩如下的游戏:甲先在 的方格表中填入 1 至 10000 , 每个数恰填一次。接着乙将一枚棋子放在最左边一列的某个方格中,乙可以将这枚棋子移动到相邻的方格中(两个方格若有公共顶点则视为相邻)，乙经过若干次移动后将这枚棋子移动到最右边一列的某个方格中。计算棋子经过的方格(包括最初和最终的方格) 中的所有数之和 。试求最小的整数 ,使得在不依赖于甲的策略下,乙总能使得 。

解 的最小值为 500000 。首先甲有策略使得 。甲将第 列从上至下填 至 ,将第 行从下至上填 至 。由于第 列与第 列中任意两个相邻方格中的数之和不小于 ，而这枚棋子必定经过第 列与第 列中两个相邻方格，故

另一方面，乙有方法总使得 。将表格分成 50 个 的子表格，则必有一个子表格 ,其中所有数之和不超过

在 中取每列两个数中的较小数,则这 100 个数从左至右依次相邻,它们的总和不超过 。

例 3 考虑直角坐标平面上的 整点集合 ,

20}。初始时 中的点均未染色。甲、乙两人轮流将 中的点染色,由甲先进行。每次轮到甲时,他选择 中一个未染色的点染为红色,要求任意两个红点之间的距离都不等于 。每次轮到乙时,他选择 中一个未染色的点染为蓝色,无任何限制。如此这般进行下去直至某个人无法再染色。

试确定最大的整数 ,使得无论乙如何染色,甲总能保证至少将 个点染为红色。

解 首先, 甲有策略可以将至少 100 个点染为红色。将所有整点分为奇偶两类, 若 ,则称 是奇整点,否则称其为偶整点。由于任意两个奇整点之间的距离都不等于✓万，且奇整点共有 200 个，故甲可以在前 100 次轮到自己时都将一个未染色的奇整点染为红色，这样甲可以至少将 100 个点染为红色。

其次,乙有策略让甲至多将 100 个点染为红色。考虑一个 的点阵,可以分成 4 组, 如下所示, 标记同一个字母的四个整点为一组。

同一组的四个整点,将其中距离等于 的两个点连线,均构成一个平行四边形。乙采用如下策略，先将 400 个整点分成 25 个 的点阵，每个点阵中都按上图方式分成 4 组，每组 4 个点，并且在每组中将距离为 的两个点连线，这样构成了 100 个平行四边形。甲每次在某个平行四边形中选择了一个顶点 染为红色,乙就将这个平行四边形上与 相对的顶点染为蓝色,与 相邻的两个顶点甲都不能再染为红色。这样甲在每个平行四边形上至多将一个顶点染为红色, 因此甲至多将 100 个顶点染为红色。

综上可知,所求 。

例 4 在一个 的棋盘上,放有一块 的骨牌,恰覆盖了 4