Problem 3

Let

x_1, x_2, \ldots, x_n

be real numbers satisfying

x_1^2 + x_2^2 + \cdots + x_n^2 = 1

. Prove that for every integer

k \ge 2

there are integers

a_1, a_2, \ldots, a_n

, not all

0

, such that

|a_i| \le k - 1

for all

i

and

|a_1 x_1 + a_2 x_2 + \cdots + a_n x_n| \le \dfrac{(k-1)\sqrt{n}}{k^n - 1}

Step 4 of 6: Pigeonhole: two sums land in the same subinterval

Previous step Next step

In plain words

More pigeons ( $k^n$ sums) than pigeonholes ( $k^n-1$ boxes) forces two sums to be squeezed uncomfortably close together.

\text{Partition } [0,(k-1)\sqrt n] \text{ into } k^n-1 \text{ intervals of length } \frac{(k-1)\sqrt n}{k^n-1}

Detailed analysis

Divide $[0,(k-1)\sqrt n]$ into $k^n-1$ consecutive subintervals of equal length $\frac{(k-1)\sqrt n}{k^n-1}$ . There are $k^n$ values $S(c)$ (Step 2) but only $k^n-1$ subintervals to hold them, so by the pigeonhole principle at least two distinct tuples $c\ne c'$ give values $S(c)$ and $S(c')$ lying in the same subinterval.