Разделы 
Дополнительно
Задача по математике - 3753
2019-06-16 
На окружности расположены $n$ действительных чисел, сумма которых равна нулю. Одно из этих чисел равно 1.
а) Докажите, что есть два соседних числа, различающихся не менее чем на $4/n$.
б) Докажите, что есть число, отличающееся от среднего арифметического двух своих соседей не менее чем на $8/n^2$.
в) Оценку,предложенную в предыдущем пункте, можно улучшить. Попробуйте заменить в ней число 8 каким-нибудь большим числом так, чтобы утверждение этой задачи по-прежнему выполнялось для всех натуральных чисел.
г) Докажите, что для $n = 30$ на окружности есть число, отличающееся от среднего арифметического двух своих соседей не менее чем на 2/113. Приведите пример набора из 30 чисел на окружности, в котором ни одно число не отличается от среднего арифметического двух своих соседей более чем на 2/113.
Решение:
Пусть $m [n/2]$, так что $n = 2m$ или $n = 2m + 1$. Занумеруем данные числа следующим образом: $x_0 = 1$, - «начальное» число; $x_1, x_2, \cdots, x_m$ - идущие подряд по часовой стрелка от $x_0; x_{-1}, x_{-2}, \cdots, x_{-m+1}$ (и $x_{-m}$, если $n$ нечетно) - идущие подряд против часовой стрелки от $x_0$.
а) Если любые два соседние числа различаются не более чем на $\epsilon$, то
$x_1 \geq 1 - \epsilon$,
$x_2 \geq 1 - 2 \epsilon$,
$\cdots$,
$x_{m-1} \geq 1 - (m-1) \epsilon$,
$x_m \geq 1 - m \epsilon$,
$x_{-1} \geq 1 - \epsilon$,
$x_{-2} \geq 1 - 2 \epsilon$,
$\cdots$
$x_{-m+1} \geq 1 - (m-1) \epsilon$,
$(x_{-m} \geq 1 - m \epsilon)$.
Сложив эти неравенства, включая также равенство $x_0 = 1$, и учитывая, что сумма всех $n$ чисел равна 0, получим
$0 \geq n - (1 + 2 + \cdots + (m-1) + m + (m-1) + \cdots + 2 + 1) \epsilon = n - m^2 \epsilon$,
откуда $\epsilon \geq \frac{n}{m^2} \geq \frac{4}{n}$ (поскольку $m^2 \leq \frac{n^2}{4}$).
При четном $n$ оценка точная. При нечетном $n = 2m + 1$ ее можно, используя еще $x_{-m}$ слегка уточнить: $\epsilon \geq \frac{n}{m^2 + m} = \frac{4n}{n^2 - 1}$.
б) Здесь можно дважды воспользоваться результатом а) Пусть наибольшая по модулю разность соседних чисел на окружности равна $\epsilon$. Согласно а) $\epsilon \geq \frac{4}{n}$. С другой стороны, «нормированные» разности соседних чисел набора $(x_1, x_2, \cdots, x_n)$ - числа $y_k = \frac{x_k - x_{k-1}}{\epsilon}$ - в свою очередь удовлетворяют всем условиям задачи а), поэтому для некоторого $k$
$\left | \frac {x_{k+1} + x_{k-1}}{2} - x_k \right | = \left | \frac {x_{k+1} - x_k}{2} - \frac {x_k - x_{k-1}}{2} \right | = |y_{k+1} - y_k| \frac{ \epsilon}{2} \geq \frac{8}{n^2}$
(здесь иногда индекс нужно, конечно, уменьшить или увеличить на $n$, так как числа расположены на окружности).
в) и г) Покажем, как для любого $n$ получить наилучшую возможную оценку сверху для величины б - максимальной по модулю разности между числом на окружности и средним арифметическим двух его соседей и построить оптимальный (с наименьшим значением б) набор. При этом набор $(x_k)$ можно сразу считать симметричным: $x_k = x_{-k}$ поскольку замена $x_k$ на $\frac{x_k + x_{-k}}{2}$ сохраняет все свойства, оговоренные в условии задачи, и оценку $|x_{k-1} - 2x_k + x_{k+1}| \leq 2 \delta$. Прежде чем оценивать сами числа $x_k$ оценим разности $x_{k-1} - x_k$, начиная с $x_0$, а затем - начиная с противоположной точки (середины набора). Поскольку $x_1 = x_{-1}$,
$x_0 - x_1 \leq \frac{|-x_{-1} + 2x_0 - x_1|}{2} \leq \delta$;
$x_1 - x_2 \leq |(x_0 - x_1) + |-x_0 + 2x_1 - x_2| \leq 3 \delta$,
$x_2 - x_3 \leq |(x_1 - x_2) + |-x_1 + 2x_2 - x_3| \leq 5 \delta, \cdots$,
$x_{k-1} - x_k \leq (2k - 1) \delta, \cdots$ (1).
При четном $n = 2m$, когда имеется одно противоположно расположенное по отношению к $x_0$ число $x_m$, аналогично получим
$x_{m-1} - x_m \leq \delta, x_{m-2} - x_{m-1} \leq 3 \delta, \cdots, x_{m-j} - x_{m-j+1} \leq (2j - 1) \delta$. (2)
Если $n = 2m + 1$ нечетно ($x_m = x_{-m}$ - два соседних числа), то
$x_{m-1} - x_m \leq 2 \delta, x_{m-2} - x_{m-1} \leq 4 \delta, \cdots, x_{m-j} - x_{m-j+1} \leq 2j \delta$. ($2^{ \prime}$)
Заметим, что для $k$ меньшего, чем $\frac{m}{2}$, лучшей оценкой для $x_{k-1} - x_k$ будет (1), а для $k$ большего $\frac{m}{2}$ - (2) или $(2^{ \prime})$; для оптимального набора чисел ($x_k$) соответствующие неравенства должны стать равенствами, при этом график оптимальной последовательности будет лежать на кусочках парабол (рис.).
Чтобы доказать это и привести точную оценку $\delta$ для каждого $n$, нужно разобрать отдельно четыре случая, соответствующие разным остаткам $n$ при делении на 4. Пусть, например $n = 4l + 2$. Из (1) и (2) следует, что $x_k = x_{-к} \geq 1 - s_k \delta$, где $s_k$ - сумма первых $k$ чисел в строке:
$1, 3, \cdots, 2l - 1, 2l + 1, 2l- 1, \cdots, 3, 1$.
Точная оценка $\delta$ получится из условия, что сумма всех $x_k$ равна 0, а оптимальным будет набор $x_k = x_{-k} = 1 - s_k \delta$. В частности, для $n = 30 (l = 7)$ получим:
$0 = x_0 + 2 (x_1 + x_2 + \cdots + x_{14}) + x_{15} \geq 30 - S \delta$,
где $S = 2(s_1 + s_2 + \cdots + s_{14}) + s_{15}$. Эту сумму удобно считать так: поскольку
$s_{15} = 1 + 3 + 5 + \cdots + 11 + 13 +11 + \cdots + 3 + 1 = 7^2 + 8^2 = 113 = s_1 + s_{14} = s_2 + s_{13} = \cdots = s_7 + s_8$,
то $S = (2 \cdot 7 + l) s_{15} = 15 \cdot 113$. Таким образом, $\delta \geq \frac{2}{113}$, причем $\delta = \frac{2}{113}$ только для набора (показанного на рисунке)
$x_k = x_{-k} = 1 - s_k \delta = \begin{cases} 1 - k^2 \delta & при 0, 1, \cdots, 7 \\ 1 - (113 - (15 - k)^2) \delta = -1 + (15 - k)^2 \delta & при k = 8, \cdots, 15 \end{cases}$.
Аналогично можно получить точные границы $\delta$ для любого $n$ и убедиться, что при всех $n$ выполнено неравенство $\delta \geq \frac{16}{n^2}$ (при больших $n$ эта оценка близка к точной).
Непрерывный аналог последней задачи: найти наибольшую возможную разность между максимумом и минимумом периодической функции с периодом $T$, у которого вторая производная не превосходит по модулю 1. Эта задача даже проще, чем «дискретный» вариант. График функции, имеющей наибольшее «колебание», также состоит из кусочков парабол.
На окружности расположены $n$ действительных чисел, сумма которых равна нулю. Одно из этих чисел равно 1.
а) Докажите, что есть два соседних числа, различающихся не менее чем на $4/n$.
б) Докажите, что есть число, отличающееся от среднего арифметического двух своих соседей не менее чем на $8/n^2$.
в) Оценку,предложенную в предыдущем пункте, можно улучшить. Попробуйте заменить в ней число 8 каким-нибудь большим числом так, чтобы утверждение этой задачи по-прежнему выполнялось для всех натуральных чисел.
г) Докажите, что для $n = 30$ на окружности есть число, отличающееся от среднего арифметического двух своих соседей не менее чем на 2/113. Приведите пример набора из 30 чисел на окружности, в котором ни одно число не отличается от среднего арифметического двух своих соседей более чем на 2/113.
Решение:
Пусть $m [n/2]$, так что $n = 2m$ или $n = 2m + 1$. Занумеруем данные числа следующим образом: $x_0 = 1$, - «начальное» число; $x_1, x_2, \cdots, x_m$ - идущие подряд по часовой стрелка от $x_0; x_{-1}, x_{-2}, \cdots, x_{-m+1}$ (и $x_{-m}$, если $n$ нечетно) - идущие подряд против часовой стрелки от $x_0$.
а) Если любые два соседние числа различаются не более чем на $\epsilon$, то
$x_1 \geq 1 - \epsilon$,
$x_2 \geq 1 - 2 \epsilon$,
$\cdots$,
$x_{m-1} \geq 1 - (m-1) \epsilon$,
$x_m \geq 1 - m \epsilon$,
$x_{-1} \geq 1 - \epsilon$,
$x_{-2} \geq 1 - 2 \epsilon$,
$\cdots$
$x_{-m+1} \geq 1 - (m-1) \epsilon$,
$(x_{-m} \geq 1 - m \epsilon)$.
Сложив эти неравенства, включая также равенство $x_0 = 1$, и учитывая, что сумма всех $n$ чисел равна 0, получим
$0 \geq n - (1 + 2 + \cdots + (m-1) + m + (m-1) + \cdots + 2 + 1) \epsilon = n - m^2 \epsilon$,
откуда $\epsilon \geq \frac{n}{m^2} \geq \frac{4}{n}$ (поскольку $m^2 \leq \frac{n^2}{4}$).
При четном $n$ оценка точная. При нечетном $n = 2m + 1$ ее можно, используя еще $x_{-m}$ слегка уточнить: $\epsilon \geq \frac{n}{m^2 + m} = \frac{4n}{n^2 - 1}$.
б) Здесь можно дважды воспользоваться результатом а) Пусть наибольшая по модулю разность соседних чисел на окружности равна $\epsilon$. Согласно а) $\epsilon \geq \frac{4}{n}$. С другой стороны, «нормированные» разности соседних чисел набора $(x_1, x_2, \cdots, x_n)$ - числа $y_k = \frac{x_k - x_{k-1}}{\epsilon}$ - в свою очередь удовлетворяют всем условиям задачи а), поэтому для некоторого $k$
$\left | \frac {x_{k+1} + x_{k-1}}{2} - x_k \right | = \left | \frac {x_{k+1} - x_k}{2} - \frac {x_k - x_{k-1}}{2} \right | = |y_{k+1} - y_k| \frac{ \epsilon}{2} \geq \frac{8}{n^2}$
(здесь иногда индекс нужно, конечно, уменьшить или увеличить на $n$, так как числа расположены на окружности).
в) и г) Покажем, как для любого $n$ получить наилучшую возможную оценку сверху для величины б - максимальной по модулю разности между числом на окружности и средним арифметическим двух его соседей и построить оптимальный (с наименьшим значением б) набор. При этом набор $(x_k)$ можно сразу считать симметричным: $x_k = x_{-k}$ поскольку замена $x_k$ на $\frac{x_k + x_{-k}}{2}$ сохраняет все свойства, оговоренные в условии задачи, и оценку $|x_{k-1} - 2x_k + x_{k+1}| \leq 2 \delta$. Прежде чем оценивать сами числа $x_k$ оценим разности $x_{k-1} - x_k$, начиная с $x_0$, а затем - начиная с противоположной точки (середины набора). Поскольку $x_1 = x_{-1}$,
$x_0 - x_1 \leq \frac{|-x_{-1} + 2x_0 - x_1|}{2} \leq \delta$;
$x_1 - x_2 \leq |(x_0 - x_1) + |-x_0 + 2x_1 - x_2| \leq 3 \delta$,
$x_2 - x_3 \leq |(x_1 - x_2) + |-x_1 + 2x_2 - x_3| \leq 5 \delta, \cdots$,
$x_{k-1} - x_k \leq (2k - 1) \delta, \cdots$ (1).
При четном $n = 2m$, когда имеется одно противоположно расположенное по отношению к $x_0$ число $x_m$, аналогично получим
$x_{m-1} - x_m \leq \delta, x_{m-2} - x_{m-1} \leq 3 \delta, \cdots, x_{m-j} - x_{m-j+1} \leq (2j - 1) \delta$. (2)
Если $n = 2m + 1$ нечетно ($x_m = x_{-m}$ - два соседних числа), то
$x_{m-1} - x_m \leq 2 \delta, x_{m-2} - x_{m-1} \leq 4 \delta, \cdots, x_{m-j} - x_{m-j+1} \leq 2j \delta$. ($2^{ \prime}$)
Заметим, что для $k$ меньшего, чем $\frac{m}{2}$, лучшей оценкой для $x_{k-1} - x_k$ будет (1), а для $k$ большего $\frac{m}{2}$ - (2) или $(2^{ \prime})$; для оптимального набора чисел ($x_k$) соответствующие неравенства должны стать равенствами, при этом график оптимальной последовательности будет лежать на кусочках парабол (рис.).
Чтобы доказать это и привести точную оценку $\delta$ для каждого $n$, нужно разобрать отдельно четыре случая, соответствующие разным остаткам $n$ при делении на 4. Пусть, например $n = 4l + 2$. Из (1) и (2) следует, что $x_k = x_{-к} \geq 1 - s_k \delta$, где $s_k$ - сумма первых $k$ чисел в строке:
$1, 3, \cdots, 2l - 1, 2l + 1, 2l- 1, \cdots, 3, 1$.
Точная оценка $\delta$ получится из условия, что сумма всех $x_k$ равна 0, а оптимальным будет набор $x_k = x_{-k} = 1 - s_k \delta$. В частности, для $n = 30 (l = 7)$ получим:
$0 = x_0 + 2 (x_1 + x_2 + \cdots + x_{14}) + x_{15} \geq 30 - S \delta$,
где $S = 2(s_1 + s_2 + \cdots + s_{14}) + s_{15}$. Эту сумму удобно считать так: поскольку
$s_{15} = 1 + 3 + 5 + \cdots + 11 + 13 +11 + \cdots + 3 + 1 = 7^2 + 8^2 = 113 = s_1 + s_{14} = s_2 + s_{13} = \cdots = s_7 + s_8$,
то $S = (2 \cdot 7 + l) s_{15} = 15 \cdot 113$. Таким образом, $\delta \geq \frac{2}{113}$, причем $\delta = \frac{2}{113}$ только для набора (показанного на рисунке)
$x_k = x_{-k} = 1 - s_k \delta = \begin{cases} 1 - k^2 \delta & при 0, 1, \cdots, 7 \\ 1 - (113 - (15 - k)^2) \delta = -1 + (15 - k)^2 \delta & при k = 8, \cdots, 15 \end{cases}$.
Аналогично можно получить точные границы $\delta$ для любого $n$ и убедиться, что при всех $n$ выполнено неравенство $\delta \geq \frac{16}{n^2}$ (при больших $n$ эта оценка близка к точной).
Непрерывный аналог последней задачи: найти наибольшую возможную разность между максимумом и минимумом периодической функции с периодом $T$, у которого вторая производная не превосходит по модулю 1. Эта задача даже проще, чем «дискретный» вариант. График функции, имеющей наибольшее «колебание», также состоит из кусочков парабол.
