Title

在前 $3n$ 个自然数中($n >1$),任取 $n+2$ 个数,试证:其中必存在两个数,这两个数的差的绝对值在 $[n,2n)$ 之内.

Proof

不妨将选出来的 $n+2$ 个数按从小到大的顺序排列,记为

$$1 \leq a_1 < a_{2}^{} < \cdots < a_{n+2}^{} \leq 3n$$

构造序列 $\{a_i-a_1\}$,其中 $1 \leq i \leq 3n$,且第一项恒为 $0$,序列严格递增.

  1. 若序列中的最大项 $a_{n+2}-a_1 < n$

    由抽屉原理可知,序列 $\{a_i\}$ 中显然有两项相同,矛盾;

  2. 若序列中的最大项满足 $n \leq a_{n+2}^{}-a_1 < 2n$,则命题显然成立

  3. 若序列中最大项满足 $a_{n+2}^{}-a_1 \geq 2n$,继续讨论如下:

    1. 存在某一项满足 $n \leq a_{i}^{}-a_1 < 2n$$1 < i < n+2$) ,那么命题自然也成立

    2. 否则,必存在某自然数 $1 \leq i \leq 3n-1$,恰好使得:$a_i-a_1 < n\quad \And \quad a_{i+1}^{}-a_1 \geq 2n$,于是可知 $a_{i+1}-a_i > n$

      我们再证明 $a_{i}$$a_{i+1}$ 的差小于 $2n$. 假设不然,则有 $a_{i+1}-a_i \geq 2n$,注意到这两项是相邻的,从而选中的其他数不会夹在它们中间,那么剩下的 $n$ 个数的可取值的数目为 $n-1$ 个,产生矛盾.

综上,命题得证.

Q.E.D.

Original Title

在前 $3n$ 个自然数中($n >1$),任取 $n+2$ 个数,试证:其中必存在两个数,这两个数的差的绝对值在 $(n,2n)$ 之内.

Proof

不妨将选出来的 $n+2$ 个数按从小到大的顺序排列,记为

$$1 \leq a_1 < a_{2}^{} < \cdots < a_{n+2}^{} \leq 3n$$

显然有 $a_{n+2} \leq 3n$,把选择的每个数都加上 $3n-a_{n+2}$,这样处理后不改变任何两数差的绝对值,于是总可以认为取出的 $n+2$ 个数中包含 $3n$.

若除了 $3n$ 外,取出的 $n+1$ 个数中不含 $n+1$, $n+2$, $n+3$, $\ldots$, $2n-1$,把这些数之外的 $2n$ 个数划分成 $n$ 个集合: $\{1,2n\}$, $\{2,2n+1\}$, $\{3,3n+1\}$, $\cdots$, $\{n,3n-1\}$,这样剩下的 $n+1$ 个数就必须在这 $n$ 个集合中取,由抽屉原理可知,必定有两个数在同一个集合中,他们的差为 $2n-1$,于是命题得证.

Q.E.D.

Conclusion

非常遗憾,笔者没有完整地做出本问题,想了很久尝试了几种方法才证明了一个较弱的命题.

原问题(original title)的解法使用了几个技巧值得注意:

  1. 把选取的序列进行了 “整体平移",这样不影响核心的要素:两数之差,又能使解答的过程的表述更为简化;

  2. 关键的一点在于,其把 $n+1$, $n+2$, $n+3$, $\ldots$, $2n-1$ 单独考虑,是把 ”空抽屉“ 先拎出来考虑,剩下的抽屉(可取值的数目)就大幅减小了,于是再应用抽屉原理——这是抽屉原理类型问题的 “优化思路” 的一种

注意,不能直接把 $3n$ 个数作为抽屉直接划分——如果你试过之后,就会发现每个抽屉的容量不能小于 $3$,否则可取值无法全部遍历;但也不能大于等于 $3$,因为每个抽屉里的数必须两两差值大于 $n$,绝对无法保持在 $3n$ 这个上限内.

另外,笔者的方法虽然也有一定的参考意义,但是是无法证明原来较强版本的命题的,伤心……