Неравенство [Теория чисел]

[Whitaker]

Здравствуйте, друзья!

Помогите доказать такое неравенство.
Доказать, что при любом $x\geqslant 0$ и натуральном $n$ справедливо неравенство

$$\lfloor nx\rfloor\geqslant \dfrac{\lfloor x\rfloor}{1}+\dfrac{\lfloor 2x\rfloor}{2}+\cdots+\dfrac{\lfloor nx\rfloor}{n}$$

(Оффтоп)

USAMO 1981

С уважением, Whitaker.

[kw_artem]

В задачнике вообще написано "... справедливо равенство"

[Sonic86]

Можно, например, попробовать перейти от целых частей к дробным и рассмотреть значения $x$ на интервалах $[\frac{k}{n};\frac{k+1}{n})$. Пробовали?
Возможно, полезно нарисовать график.

[Whitaker]

Sonic86
Я перешел к дробным частям. Получается, что нужно доказать нижеуказанное неравенство:
$\{nx\}\leqslant \dfrac{\{x\}}{1}+\dfrac{\{2x\}}{2}+\cdots+\dfrac{\{nx\}}{n}$
Вы предлагаете исследовать неравенство на полуинтервалах вида $[\frac{k}{n}, \frac{k+1}{n})$, где $0\leqslant k \leqslant n-1$?

[kw_artem]

Достаточно доказать для любого $0\leq x <1 $ неравенство

$$\lfloor nx\rfloor\geqslant \dfrac{\lfloor x\rfloor}{1}+\dfrac{\lfloor 2x\rfloor}{2}+\cdots+\dfrac{\lfloor nx\rfloor}{n}.$$

Если за $k_i$ обозначить такие числа, что при $k_i\leq n\ < k_{k+1}$ выполняется $\lfloor nx \rfloor =i$, при этом пускай $\lfloor nx\rfloor = m$, то все числа $1, 2, 3, \ldots, n$ разделятся в случае $k_m=n+1$ на $m$ частей (всмысле $1,2,\ldots,k_{1}-1$ -- первая часть, $k_1, k_{1}+1,\ldots,k_{2}-1$ -- вторая и т.д.), либо, если $k_m\neq n+1$ на $m+1$ частей. Для суммы можно будет записать

$$\dfrac{\lfloor x\rfloor}{1}+\dfrac{\lfloor 2x\rfloor}{2}+\cdots+\dfrac{\lfloor nx\rfloor}{n}=\frac {k_2-k_1} {k_1} +2\frac {k_3-k_2} {k_2} +\ldots+m\frac {n-k_m+1} {k_m} .$$

Числа $k_i$ будут попадаться в ряду $1, 2, 3, \ldots, n$ почти через одинаковое кол-во чисел, лишь иногда "перескакивая" на число вперед или назад, поэтому, если можно (не нарушая условия количества отрезков $m+1$) из всех "отрезков" $k_1-1,k_2-k_1,\ldots,k_{m}-k_{m-1}$ взять наименьший, приняв его за $k$ (тогда и разбиение получится другим), то вроде неравенство доказывается:

$$\frac {2k-k} {k} +2\frac {3k-2k} {2k} +\ldots+m\frac {n-mk} {mk}\geq m=\lfloor nx \rfloor\geq\frac {k_2-k_1} {k_1} +2\frac {k_3-k_2} {k_2} +\ldots+m\frac {n-k_m+1} {k_m} $$

[Whitaker]

kw_artem
Прочитал Ваше решение несколько раз, но абсолютно ничего не понял.
Есть ли другой метод решения?

[kw_artem]

Наверняка есть простой, но его не знаю.
А неравенство с дробными частями? Не доказали?

(Оффтоп)

с какого места Вы не поняли

[Whitaker]

kw_artem
неравенство с дробными частями я тоже не смог доказать.
Рассмотрел сначала полуинтервал $[0, \frac{1}{n})$ для него вроде получилось.
А для $[\frac{1}{n}, \frac{2}{n})$ не смог ничего сделать

[Whitaker]

Нашел интересное и очень красивое решение к этой задаче.

Лемма: $\lfloor{nx}\rfloor\geqslant \lfloor{ax}\rfloor+\lfloor{(n-a)x}\rfloor$

Пусть $S_1=\lfloor{x}\rfloor$, a $S_n=\sum \limits_{i=1}^{n}\dfrac{\lfloor{ix}\rfloor}{i}$
Докажем индукцией по $n$, что $S_n\leqslant \lfloor{nx}\rfloor$
При $n=1$ получаем, что $S_1\leqslant \lfloor{x}\rfloor$.
Допустим, что для $n\leqslant k$ верно $S_n\leqslant \lfloor{nx}\rfloor$
Докажем утверждение для $n=k+1$
Так как $S_n-S_{n-1}=\dfrac{\lfloor{nx}\rfloor}{n}$, то:
$nS_n-(n-1)S_{n-1}=n(S_n-S_{n-1})+S_{n-1}=\lfloor{nx}\rfloor+S_{n-1}\leqslant \lfloor{nx}\rfloor+\lfloor{(n-1)x}\rfloor$ для $n\leqslant k+1$
Оценим следующую сумму:
$S_1+\sum \limits_{i=2}^{k+1}\left(iS_i-(i-1)S_{i-1}\right)$
Эта сумма есть в точности $(k+1)S_{k+1}$
$S_1+\sum \limits_{i=2}^{k+1}\left(iS_i-(i-1)S_{i-1}\right)\leqslant S_1+\sum \limits_{i=2}^{k+1}\left(\lfloor{ix}\rfloor+\lfloor{(i-1)x}\rfloor\right)=2\sum \limits_{i=1}^{k}\lfloor{ix}\rfloor+\lfloor{(k+1)x}\rfloor\leqslant(k+1)\lfloor{(k+1)x}\rfloor$
Получаем, что:
$(k+1)S_{k+1}\leqslant(k+1)\lfloor{(k+1)x}\rfloor$
$S_{k+1}\leqslant\lfloor{(k+1)x}\rfloor$
Утверждение доказано.