设 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中的数，故结论成立。
综上所述，结论成立。
评论