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 2 of 6: List all k^n integer-weighted sums

Previous step Next step

In plain words

Instead of guessing the right integers directly, list every possible 'small' integer combination and see where all their values land.

S(c) = \sum_{i=1}^{n} c_i y_i, \qquad c=(c_1,\ldots,c_n)\in\{0,1,\ldots,k-1\}^n

Detailed analysis

Consider every tuple $c=(c_1,\ldots,c_n)$ with each $c_i$ an integer in $\{0,1,\ldots,k-1\}$ ; there are $k^n$ such tuples ( $k$ choices for each of the $n$ coordinates). For each, define the real number $S(c)=\sum_{i=1}^n c_iy_i$ .