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 5 of 6: Take the difference of the two colliding tuples

Previous step Next step

In plain words

Subtracting two nearly-equal sums cancels most of the bulk and leaves a genuinely tiny quantity — exactly the bound we were asked to achieve.

d_i = c_i - c'_i, \qquad d \ne 0, \quad |d_i|\le k-1, \qquad |S(c)-S(c')| = \left|\sum d_i y_i\right| \le \frac{(k-1)\sqrt n}{k^n-1}

Detailed analysis

Let $d_i=c_i-c_i'$ . Since $c\ne c'$ , not all $d_i$ are zero; since $c_i,c_i'\in\{0,\ldots,k-1\}$ , each $|d_i|\le k-1$ . Because $S(c)$ and $S(c')$ lie in the same subinterval of length $\frac{(k-1)\sqrt n}{k^n-1}$ , their difference satisfies $\left|\sum_i d_iy_i\right|=|S(c)-S(c')|\le\frac{(k-1)\sqrt n}{k^n-1}$ .