玖玖小说 > 其他类型 > 1986:学霸的黄金年代 > 第73章 压轴题(3/3)
非偶然,而是有意为之。

    第1题通常是最简单的入门题,旨在让大部分参赛者都能有所得分,而第3题则成为区分顶尖选手的关键,往往涉及更复杂的数学思想和更具创新性的解题技巧。

    包括裴瑜在内的许多参赛者事后回忆,第3题确实是他们耗费时间最长、绞尽脑汁的一道题,也是选题委员会心目中最难的一道压轴题。

    考场上,第三题的题目是这样的:

    【假设为一个五边形的每个顶点赋值,使得每个值都是整数,且它们的总和是正数。现在介绍以下操作:如果连续三个顶点的取值(记作x,y,z)中位于中间的顶点的值y<0,则将它们的值变成x+y,y,y+z。证明或推翻:不断执行上述操作,一定会在有限步内终止。】

    裴瑜看完题目之后,直觉是“证明”和“推翻”八二开。但在实际手算了一会儿之后,她觉得这个题目100是“证明”而不是“推翻”了。问题只在于怎么证明。

    她接下来想出了三种解法。

    第一个做法是构造一个函数来衡量数组的“不均匀性”,并证明每次合法的翻转操作后该函数值必然减小,从而证明操作会在有限步内终止。

    第二个做法是使用绝对值来衡量数组的“均匀”程度,通过计算翻转操作前后函数值的变化,证明操作会在有限步内终止。

    第三个做法是通过观察翻转操作实际上是在交换序列中的元素,将问题转化为消除序列中的逆序对,从而证明操作会在有限步内终止。

    裴瑜的做题经验告诉她,这个问题的本质应该与weyl群和dynk图有关。