转imo题目

  上周,知友 @雍俗人士 咨询了我一道数学题,它是 1986 年的国际数学奥林匹克竞赛(IMO)的第 3 题。这是此次竞赛中最难的一道题,只有 12 名选手解出。题目的参考答案中构造了一个辅助函数,堪称「神来之笔」;而这 12 名选手中,有一位名叫 Joseph Keane 的选手则构造了一种更是「异想天开」的辅助函数,并因此获得此次竞赛的特别奖。说实话,我自己并没能解出这道题;在看过参考答案后,我产生了强烈的好奇:这些辅助函数,都是怎么想出来的呢?

  先来看一下题目:

题目

  考虑如下的「五角形游戏」:在五角形的每个顶点处放置一个整数,这些数可正可负(也可以为 0),但总和为正。只要这些数中有负数,就可以选定一个负数,把它加到相邻的两个数上去,再把它本身的符号反转。即,如果相邻的三个数为 x,y,z,且 y<0,则可以把它们变成 x+y, -y, y+z。问:经过有限步操作,是否一定能把所有数都变成非负的?

  举个例子:设初始时五角形顶点上的数分别为 7, -1, -2, 5, -4,它们的总和 5 为正。经过图 1 动画中的 6 步操作,可以把五个数分别变为 0, 1, 1, 1, 2,全为非负。

图 1:劫富济贫

  形象地说,这道题目描述的是一个「均贫富」的过程:每个负数从自己的邻居那里「抢」来一些值加到自己身上,使自己变成正数。这种「抢」是有些贪心的:一个负数 -a 实际上只需要抢来 a 就可以变得非负了,实际上它却从两个邻居那里各抢来 a,一共抢了 2a。如果邻居们因为被抢而变成负数,那么它们可以再抢回去。抢来抢去的结果,可能有两种:一是所有数都变成非负的,大家「和平共处」;二是因为抢得太过分,有两个数甚至更多数之间「冤冤相报何时了」。由于所有数的总和为正,我们感觉「和平共处」还是有希望的。那就试着来证明一下吧!

证明

  证明这种「有限步内能结束」式的结论,常常会利用这个定理:单调有界数列必收敛。我们可以构造一个非负(即有界)的辅助函数用来概括整个局面,并让它在操作的过程中单调递减。由于题目中涉及的数都是整数,如果这个辅助函数也是整数,那么它就必须在有限步之内达到最小值,于是操作必将在有限步内结束。

  常见的非负函数有两种:绝对值、平方。我们要找的辅助函数,很有可能就是一堆绝对值相加,或者一堆平方相加的形式。又由于五角形的五个顶点地位都平等,这个辅助函数也应该是轮换对称的。再考虑到题目描述的是一种「均贫富」的过程,一种辅助函数就呼之欲出了 —— 方差。既然五个数在操作过程中会越来越平均,那么它们的方差,大抵应该是单调减小的吧!

  在继续推理之前,我们注意到,「五角形」里的「五」似乎没有什么特别之处。我们不妨把它一般化为任意 n 角形。设每个顶点上的数分别为 x_1, \ldots, x_n,它们的总和为 S,平均值 \bar{x} = S/n。所有数的方差就是:\sigma^2 = \frac{1}{n} \sum_{i=1}^n (x_i – \bar{x})^2 \\通过拆括号,可以把它化简: \sigma^2 = \frac{1}{n} \left( \sum_{i=1}^n x_i^2 \right) – \bar{x}^2 \\其中 \bar{x} = S/n 是常数,所以「方差」这个辅助函数其实等效于「所有数的平方和」。

  「平方和」这个辅助函数是单调递减的吗?我们从最简单的情况看起。设 n 角形上只有一个正数(不妨设为 7)和一个负数(不妨设为 -5),两个数相距很远。第一步操作,只能把 -5 和它旁边的两个 0 变成 -5, +5, -5。注意,在这步操作中「平方和」增加了!最朴素的辅助函数构造失败。

  我们不妨看看,如果继续操作会发生什么。经过第一步操作后,我们有了两个 -5。如果我们左右开弓,同时处理这两个 -5,同时按照「先出现先处理」的原则处理操作过程中又会出现的负数,就会产生图 2 动画所示的局面。可以看到,最初的 -5 就像哪吒闹海一般,源源不断地在左右两侧掀起 +5、-5 交替的波澜,「平方和」反倒是在不断增大的!

图 2:哪吒闹海

  另一方面,如果我们专心处理一侧的 -5,我们就会发现,这个 -5 会拖着一个 +5,像火车一样行驶出去,直到与远处的 7 相撞为止(如图 3 动画)。在火车行驶过程中,「平方和」是保持不变的。注意:我们要构造的辅助函数,必须在每一步操作中都严格减小。如果允许保持不变,那么就无法排除「辅助函数一直保持不变,操作过程永远结束不了」的可能。

图 3:一往无前

  「平方和」失败了没关系,我们还可以构造其它的辅助函数。比如:所有相邻两个数之和的平方和 \sum_{i=1}^n (x_i + x_{i+1})^2 ,所有相邻两个数之差的平方和 \sum_{i=1}^n (x_i – x_{i+1})^2 ,等等。注意:如果下标超过了 n,则自动减去 n。只不过,这些辅助函数都无法应对「火车行驶」的过程:「火车」的具体位置不影响辅助函数整体的值,辅助函数在火车行驶过程中一直保持不变。这让我有些灰心,于是我去看了答案。

标准答案

  上面的视频介绍了两种辅助函数。第一种是标准答案的辅助函数:

\begin{aligned} F_1 &= \sum_{i=1}^5 (x_i – x_{i+2})^2 \\ &= 2(x_1^2 + x_2^2 + x_3^2 + x_4^2 + x_5^2 – x_1x_3 – x_2x_4 – x_3x_5 – x_4x_1 – x_5x_2) \end{aligned} \\ 它是「所有相隔一个数的两个数之差的平方和」。假设 x_4<0,一步操作把 x_3, x_4, x_5 变成了 x_3+x_4, -x_4, x_4+x_5,可以验证,辅助函数的变化量为:

\begin{aligned} \Delta F_1 &= 2[x_1^2 + x_2^2 + (x_3+x_4)^2 + x_4^2 + (x_4+x_5)^2 \\ &\qquad – x_1(x_3+x_4) + x_2x_4 – (x_3+x_4)(x_4+x_5) + x_4x_1 – (x_4+x_5)x_2] \\ &- 2(x_1^2 + x_2^2 + x_3^2 + x_4^2 + x_5^2 – x_1x_3 – x_2x_4 – x_3x_5 – x_4x_1 – x_5x_2) \\ &= 2(2x_3x_4 + 2x_4^2 + 2x_4x_5 – x_1x_4 + 2x_2x_4 – x_3x_4 – x_4^2 – x_4x_5 + 2x_1x_4 – x_2x_4) \\ &= 2(x_1x_4 + x_2x_4 + x_3x_4 + x_4^2 + x_4x_5) \\ &= 2Sx_4 \end{aligned} \\ 因为 S>0, x_4<0,所以 \Delta F_1<0,辅助函数确实单调递减。这个辅助函数确实不是一般人能想到的;然而验证过程却毫无美感,并且它也无法推广到一般的 n 角形(感兴趣的读者可以自己试一试为什么不行)。我并不想深究下去。

  第二种辅助函数,就是 Joseph Keane 在赛场上提出的了:\begin{aligned} F_2 &= |x_1| + |x_1 + x_2| + |x_1 + x_2 + x_3| + |x_1 + x_2 + x_3 + x_4| \\&+ |x_2| + |x_2 + x_3| + |x_2 + x_3 + x_4| + |x_2 + x_3 + x_4 + x_5| \\&+ |x_3| + |x_3 + x_4| + |x_3 + x_4 + x_5| + |x_3 + x_4 + x_5 + x_1| \\&+ |x_4| + |x_4 + x_5| + |x_4 + x_5 + x_1| + |x_4 + x_5 + x_1 + x_2| \\&+ |x_5| + |x_5 + x_1| + |x_5 + x_1 + x_2| + |x_5 + x_1 + x_2 + x_3| \\ \end{aligned} \\ 好家伙,足足有 20 项!其中的每一项,对应的都是 n 边形上连续的若干个数之和;而整个辅助函数,则囊括了所有连续的段落(包含了所有数的 |x_1 + x_2 + x_3 + x_4 + x_5| 为常数,不必计入)。这个辅助函数的优点在于它可以推广到任意 n 角形,Joseph Keane 也正是因此获得了 IMO 1986 的特别奖。要验证 F_2 单调递减并不容易,但我看到它之后不禁感叹:我之前的思路明明是对的!只要再往前探索一步,我也能得出 F_2 的形式!

反思

  前面说过,那些朴素的辅助函数的失败,都是因为它们在「火车行驶」的过程中,对火车的位置不敏感,因此值保持不变。而它们对火车的位置不敏感的原因,在于它们中的每一项都是「局部」的:它们只是对整个 n 角形的某个局部上有限的几个角上的数去加加减减。若要造出一个步步单调递减的辅助函数,其中各项涉及的角的个数就不能是固定的,而是应该随 n 的增加而增加,有些项甚至应该涉及到绝大多数的角!

  受此启发,我考虑了这样一个函数: f = |x_1| + |S – x_1| 。它也有一种「均贫富」的意味:如果 x_1 特别正,或者特别负,两个绝对值之和就会很大;只有 x_1 比较接近 0 时, f 才会小。最重要的是,如果 x_1 恰是某一步操作中中间的那个负数, f 一定是减小的:第一项由 |x_1| 变成 |-x_1| ,实际上不变;第二项由 |S-x_1| 变成了 |S + x_1| ,由于 Sx_1 异号,第二项会减小。有戏!

  考虑到辅助函数应该是轮换对称的,我们把 f 扩展成如下形式:

F_3 = \sum_{i=1}^n |x_i| + \sum_{i=1}^n |S – x_i| \\F_2 相比, F_3 目前只包含了「长度为 1」和「长度为 n-1」两种段落上各数之和的绝对值。

  现在考虑把连续的三个数 x,y,z(其中 y<0 )变成 x+y, -y, y+z 的操作。很明显,在 F_3 中,除了以下六项以外,所有项都是不变的:|x|, |y|, |z|, |S-x|, |S-y|, |S-z|。上面说过了,经过这步操作,|y| 不变,而 |S-y| 会减小,但剩下的四项会怎么变化,就没有固定的规律了:比如,|x| 会变成 |x+y|。这启发我们:如果把 |x+y| 也包括进辅助函数会怎样?我们发现,在 |x| 变成 |x+y| 的同时,|x+y| 也变成了 |x|,二者的值恰好交换了,而总和不变!

  为了保持辅助函数的轮换对称性,既然要把 |x+y| 包括进辅助函数,那就要把「所有相邻两项之和的绝对值」都包括进去。于是,辅助函数中就会出现 |w+x| 这一项(w 是 x 左边的数),它是变大还是变小没有规律。但我们知道它会变成 |w+x+y| ,同时 |w+x+y| 会变成 |w+x| —— 二者又配成一对,总和不变。于是,我们就想到把「所有连续三项之和的绝对值」也包括进辅助函数里去。如此类推,所有连续四项、五项……之和的绝对值,也都应该统统包括进来。这个过程不会无穷无尽 —— F_3 本就已经包括了「所有连续 n-1 项之和的绝对值」。而包括了「所有连续段落上各数之和的绝对值」的辅助函数,恰恰就是 Joseph Keane 提出的 F_2!对于一般的 n,这个辅助函数可以表达为: F_2 = \sum_{i=1}^n \sum_{j=1}^{n-1} \left| \sum_{k=i}^{i+j-1} x_k\right| \\

它一共由 n(n-1) 个绝对值相加而成,每个绝对值内部都是一个连续段落上所有数之和,下标 i 表示这个段落从第几个数开始,下标 j 表示段落包含几个数。

  上面的推理过程,也给我们提供了证明 F_2 单调递减的思路。设某一步操作把连续的三个数 x,y,z(其中 y<0 )变成了 x+y, -y, y+z。我们以「包含了 x,y,z 中的哪几个数」为标准,把 F_2 中的所有项分成八类:

  - x,y,z 全都包含;
  - x, y, z 全都不包含;
  - 仅含 y —— 这样的项只有 |y|;
  - 仅含 x,z —— 这样的项只有 |S-y|;
  - 仅含 x,例如 |w+x|;
  - 仅含 x,y,例如 |w+x+y|;
  - 仅含 z;
  - 仅含 y,z。

  根据上文的分析,第 1、2、3 类项的值不变,而第 4 类项的值减小。第 5、6 类项两两配对,总和不变;第 7、8 类项两两配对,总和也不变。于是,所有项的总和 F_2 就是单调递减的,因此必能在有限步之内把 n 角形上的所有数都变成非负!

  顺便我们也能发现,把 F_2 中的所有绝对值都换成平方,甚至绝对值的任意正数次方,都不会破坏它「单调递减」的性质。

  到此,我算是解答了「辅助函数是怎么想出来的」这一问题。我的思路带有一定「事后诸葛亮」的成分,也不见得与 Joseph Keane 在赛场上的思考过程一致,但从中我们还是可以总结出辅助函数应当满足的一些条件,作为以后面对此类问题时的经验。为了保证收敛,辅助函数应该是单调、有界(非负)的,这是此类问题的常见套路;本题中的「整数」这一条件,则保证了收敛所需的步数有限。同时,由于 n 角形是旋转对称的,辅助函数也应该轮换对称。而本题的特色在于,辅助函数必须是非局部的 —— 我们通过推演最简单的情况嗅到了这样的信号,并抓住这一线索,成功地构造出了一个非局部的辅助函数。

  • # 扩展

  「五角形游戏」,或者更一般地称为「多角形游戏」,还有许多有趣的性质和扩展。我们费了好大力气,证明了在「各个顶点上的数都是整数,且总和为正」的条件下,能用有限步操作把所有数都变成非负的。而这篇短小精悍的论文 [1],则证明了以下这些结论:

  1. 「所有数都是整数」的条件可以放宽,哪怕是任意实数,也能在有限步操作之内把所有数变为非负;
  2. 把所有数变为非负需要的操作次数完全由初始状态决定,与操作过程中的选择无关;
  3. 所有数都变成非负后的最终状态,也完全由初始状态决定;
  4. 每个角上是会在某个时刻出现负数,还是始终为非负,也完全由初始状态决定。

  举个例子,如果我们把图 2、图 3 中的操作过程继续下去,直到所有数都变成非负为止,我们会得到图 4 中的两种操作过程。它们在漫长的 75 步操作后达到相同的最终状态:最初的 7 和 -5 都变成了 1,其余数仍为 0。

图 4:殊途同归https://www.zhihu.com/video/1563782893683564544

  「多角形游戏」的命题人 Elias Wegert 在这篇论文 [2] 中提到了命题的动机:这是作者在研究「等周定理」时,得到的一个副产品。「等周定理」说的是:在周长相等的图形中,圆的面积最大。一个与之类似的定理是:在周长相等的 n 边形中,正 n 边形的面积最大。这两个定理的证明过程中,第一步都是证明面积最大的图形必定是凸的:如果图形是凹的,那么总可以把凹的部分翻转出来,使得面积变大。「多角形游戏」中各个数的一种实际意义,就与一种翻转过程有关。

  设多边形上有一个角 \angle ABC 是凹进去的。我们考虑这样的翻转过程:连结 AC,取其中点 O ,以 O 为对称中心,把边 AB、BC 旋转 180 度,得到边 CB’、B’A(注意:并非以 AC 为镜面翻转)。我们关注各个顶点处的外角,并规定凸顶点处的外角为正,凹顶点处的外角为负。不难发现, A,B,C 三个顶点处的外角分别从 \alpha, \beta, \gamma(其中 \beta<0)变成了 \alpha + \beta, -\beta, \beta + \gamma —— 这跟「多角形游戏」中的操作规则一模一样!同时,多边形的各个外角和为 2\pi,是个正数。所以「多角形游戏」的结论告诉我们:

  1. 经过有限次翻转,一定能把一个凹多边形变成凸的。
  2. 翻转过程可能多种多样,但翻转次数,以及最终得到的凸多边形的形状,都是唯一的,并且哪些顶点在翻转过程中从来没有动过也是确定的。

当然,这些结论对于等周定理的证明,并没有什么用处。

  论文[2] 一共给出了「多角形游戏」收敛性的六种证明方法,很有启发性。它还把「多角形」推广到了一般的无向图:每个顶点可以与任意多的其它顶点相连,如果一个顶点上的数 -a 为负,那么它可以从它的 m 个邻居那里各抢来 2a/m 加到自己身上,把自己变成 +a。这样的操作不改变所有数的总和。作者证明了:只要图整体连通,且所有数的总和为正,那么必然可以在有限步操作之内把所有数都变为非负。只不过,操作次数和最终状态不再是唯一确定的了。

  上面的操作过程又称为「松弛过程」,它居然在 circle packing(圆形装填)问题上有应用。圆形装填问题指的是,怎样在给定的图形(如矩形、圆形中)填充尽可能多的指定大小的圆。很明显,研究圆形装填问题,可以指导在工业生产中节省物料。

  论文[3] 研究了另外一种「松弛过程」:一个负数 -a 可以让它的所有邻居都减小 a,同时自己变成 +a。这样的操作不再保持所有数的总和相等。该论文的作者证明了,当初始状态满足某种条件时,操作可以在有限步内结束,且操作次数和最终状态都完全由初始状态决定。只不过证明过程用到了许多以人名命名的、高深的代数理论,我就看不懂了。

本文转自 https://zhuanlan.zhihu.com/p/572123665,如有侵权,请联系删除。

参考

  1. ^Alon, N., I. Krasikov, and Y. Peres. “Reflection sequences.” The American Mathematical Monthly 96.9 (1989): 820-823. pdf
  2. ^abWegert, Elias, and Christian Reiher. “Relaxation procedures on graphs.” Discrete applied mathematics 157.9 (2009): 2207-2216. pdf
  3. ^Mozes, Shahar. “Reflection processes on graphs and Weyl groups.” Journal of Combinatorial Theory, Series A 53.1 (1990): 128-142. pdf
暂无评论

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇