одна олимпиадная задача)

[NiGHTeR]

Помогите пожалуйста решить или хотя бы подскажите с чего начать решение следующей задачи:
Докажите, что для любых действительных чисел $x_1; x_2; ... x_n$ , таких, что $x_1^2+x_2^2+...+x_n^2=1$ и для любого $k\in N$$ существуют такие целые $a_1; a_2; ...; a_n$ и $|a_i|\leqslant k-1$ , что выполняется:

$$|a_1x_1+a_2x_2+...+a_nx_n| \leqslant ((k-1)\sqrt[]{n})/(k^n-1)$$

извините, с дробями еще не разобрался)

\dfrac{верх}{низ}: $\dfrac{(k-1)\sqrt n}{k^n-1}$

[Sasha2]

Что-то не то в этой задаче.
Очевидно, что все нули подходят, но это слишком просто.

[RIP]

В задаче пропущено условие, чтобы не все $a_i$ равнялись нулю (и, соответственно, требование $k>1$). Стандартная zasada pudełkowa. Пусть числа $y_1,\ldots,y_n$ пробегают независимо числа $0,1,\ldots,k-1$. Тогда все $k^n$ чисел $x_1y_1+\ldots+x_ny_n$ живут на неком отрезке длины $(k-1)(|x_1|+\ldots+|x_n|)\le(k-1)\sqrt n$. Собственно, и всё.

[NiGHTeR]

да, ограничение не все $a_i$ равны нулю

RIP в сообщении #271555 писал(а):

Пусть числа $y_1,\ldots,y_n$ пробегают независимо числа $0,1,\ldots,k-1$. Тогда все $k^n$ чисел $x_1y_1+\ldots+x_ny_n$ живут на неком отрезке длины $(k-1)(|x_1|+\ldots+|x_n|)\le(k-1)\sqrt n$.

ну это почти очевидный факт)
но как с помощью него решить задачу?
дальше частного случая n=2 не идет, и то не уверен в решении

[RIP]

NiGHTeR в сообщении #271744 писал(а):

но как с помощью него решить задачу?

Среди этих чисел найдутся 2 (с разл. наборами игреков), которые отличаются не более чем на $(k-1)\sqrt n/(k^n-1)$. Ровно это и требуется доказать.

[NiGHTeR]

понял, спасибо