这个就是当年韦东奕封神收官之题,韦神当年满分.不少网友表示题都没看懂(证明:存在一种跳法,使得蚱蜢不落在任何一个 M 中的点上)

MoMo 2021年5月31日12:44:37
评论
130

设 a[1],...,a[n] 是 n 个互不相同的正整数, M 是一个不包含 s=a[1]+a[2]+...+a[n] 的 n-1 元正整数集。

一只蚱蜢在实轴上跳跃,它从 0 点开始,向右跳跃 n 次,其长度为 a[1],a[2],...,a[n] 的一个排列。

证明:存在一种跳法,使得蚱蜢不落在任何一个 M 中的点上。

 

证明:

a1,a2,...,an是不同的正整数,M是一个由n−1个正整数构成的集合,但是M中不包含

s = a1 + a2 +...+ an。一只蚱蜢在实数轴的整数点上跳动,开始时它在0点,然后向右跳n次,

n次的步长恰好是 a1,a2,...,an的一个排列。证明:可以适当调整 a1,a2,...,an的顺序,使得期间蚱蜢不会跳到M中的数所在的任何整点上。

证明: n =1时, M = ∅,结论当然成立; n = 2时, M只有一个数 m,a1,a2中必有一个不等于m,把它放在第一步即可。以下假设k ≥ 3,并且对于任意n < k结论都成立。

不失一般性假设 a1 < a2 < ...< ak,令 si =∑aj,则 sk = s。假设蚱蜢先按照

j=1

a1,a2,...,ak的顺序来跳,如果(0,s] = ( 0,sk]

中只有k − 2个M中的数,则依据归纳假设结

论成立,以下设 0,sk中有k −1个M中的数。这k −1个数为0 < m1 < m2 < ...< mk−1

< s。

㈠如果对于所有1≤ i ≤ k −1都有si < mi,特别的有sk−1 < mk−1。

①如果sk−1 ∉M,则由归纳假设可以对前k −1步重新调整,使得蚱蜢没遇到M中的数;

②如果sk−1 ∈M,对于任意1≤ i ≤ k −1,都有sk−1 −ai < sk−1 < sk −ai,由于除了sk−1之外

只有k − 2个M中的数,因此存在一个i0,使得sk−1 −ai ,sk −ai 都不属于M。我们将ai 换

到最后一步, an为倒数第二步,这样从目的地倒退两步都没遇到 M中的数,由于

sk −ak − ai < sk−1 ≤ mk−2,由归纳假设可以调整前k − 2步使得蚱蜢没遇到M中的数。

㈡存在一个i使得si ≥ mi。假设t是最小的正整数,使得st ≥ mt。则st−1 < mt−1 < st,

①如果t =1,也即 s1 = a1∈M,由于 M < k,因此必有一个 ai ∉M,我们将 ai调整到

第一步,由于m1 ≤ a1 < ai。由归纳假设可以调整后k −1步使得蚱蜢没遇到M中的数;

②如果 t >1,由 t的最小性可知 st−1 < mt−1 < mt ≤ st,令 A ={m1,m2,..., mt−1},

B ={mt,mt+1,...,mk−1},则 M = A∪ B,由于 mt−1 < st,而 st是最短的 t步之和,所以无

论如何调整,从第t步开始的后k −t +1步都不可能遇到 A中的数。

由归纳假设可以调整前t步的顺序使得它们得以避开 A中的t −1个数,而且同㈠②我们

还可以使得at位于第t步或第t −1步,故调整后前t − 2步所走距离< st −at = st−1 < mt−1,

因此前t − 2步也不可能遇到 B中的数。

如果第t −1步也没有走到 M中的数上,由归纳假设可以调整后 k −t +1步使得它们避

开 B中的n−t个数,因此它们也就避开了所有M中的数,故结论成立。

如果第t −1步恰好走到 M中的数上,由于它已经避开了 M中的前t −1个数,因此这

个数属于 B,这从另一方面说明此时的t −1步所走总距离> mt−1。此时后面的n−t步中的

任意第 r步都比第t −1步长,因此将第 r步和第t −1步对换位置之后也肯定避开了 A中的

数。由于此时第t −1步已经遇到了 B中的一个数,因此肯定可以选到后k −t步中的一步,

使得它与第t −1步对换之后,第t −1步没有遇到 B中的数,故此时前t −1步都成功避开了

M中的所有数。由归纳假设可以调整后k −t +1步使得它们避开 B中的n−t个数,因此它

们也就避开了所有M中的数,故结论成立。

综上所述,结论成立。

https://xpanx.com/
MoMo
  • 本文由 发表于 2021年5月31日12:44:37
  • 转载请务必保留本文链接:https://xpanx.com/1638.html
匿名

发表评论

匿名网友 填写信息

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: