MathLabs

第3問

実数 x1,x2,…,xnx_1, x_2, \ldots, x_n が x12+x22+⋯+xn2=1x_1^2 + x_2^2 + \cdots + x_n^2 = 1 を満たすとする。k≥2k \ge 2 を満たす任意の整数 k に対し、すべてが 00 ではない整数 a1,a2,…,ana_1, a_2, \ldots, a_n で、すべての ii について ∣ai∣≤k−1|a_i| \le k - 1 を満たし、かつ ∣a1x1+a2x2+⋯+anxn∣≤(k−1)nkn−1|a_1 x_1 + a_2 x_2 + \cdots + a_n x_n| \le \dfrac{(k-1)\sqrt{n}}{k^n - 1} を満たすものが存在することを証明せよ。
ステップ 4/6: 鳩の巣原理:二つの和が同じ小区間に落ちる
前のステップ次のステップ
ざっくり言うと

『鳩』(knk^n 個の和)の数が『巣』(kn−1k^n-1 個の箱)の数より多いため、二つの和は窮屈なほど近くに押し込められることになる。

Partition [0,(k−1)n] into kn−1 intervals of length (k−1)nkn−1\text{Partition } [0,(k-1)\sqrt n] \text{ into } k^n-1 \text{ intervals of length } \frac{(k-1)\sqrt n}{k^n-1}
詳しい解説

区間 [0,(k−1)n][0,(k-1)\sqrt n] を、長さがすべて等しい (k−1)nkn−1\frac{(k-1)\sqrt n}{k^n-1} の kn−1k^n-1 個の連続する小区間に分割する。値 S(c)S(c)(ステップ2)は knk^n 個あるが、それらを収める小区間は kn−1k^n-1 個しかないので、鳩の巣原理により、少なくとも二つの異なる組 c≠c′c\ne c' が存在して、S(c)S(c) と S(c′)S(c') が同じ小区間に属する。