Разделы 
Дополнительно
Задача по математике - 1940
2019-01-22 
Дана последовательность неотрицательных чисел $a_1, a_2, \cdots, a_n$. Для любого $k$ от 1 до $n$ обозначим через $m_k$ величину $ \underset {l=1,2,\cdots,k}{max} \frac {a_{k-l+1}+a_{k-l+2}+\cdots+a_k}{l}$. Докажите, что при любом $a > 0$ число тех $k$, для которых $mk > a$, меньше, чем $ \frac {a_1+a_2+\cdots+a_n}{a}$.
Решение:
Первое решение. Для $1 \leq i \leq j \leq n$ обозначим через $[i, j]$ отрезок натурального ряда от $i$ до $j$. Пусть
$S(i, j) = \frac{a_i + a_{i +1} + \cdots + a_j}{j - i +1}$.
Заметим, что из $S(i,j) > \alpha$ и $S(j + 1, l) > \alpha$ следует $S(i, l) > \alpha$.
Выделим в отрезке $[1,n]$ несколько отрезков $[p_i,q_i]$ по следующему принципу: $i$-й отрезок начинается с минимального числа $p$ такого, что $a_p$ превосходит $a$ и не лежит в ранее построенных отрезках (если такого нет, то построение закончено); заканчивается он таким максимальным $q$, что при любом $j$ из $[p_i, q]$ среднее чисел от $a_{p_i}$ до $a_j$ превосходит $\alpha$. По построению $p_{i+1} > q_i + 1$.
Назовем натуральное число $k$ хорошим, если $m_k > \alpha$. Докажем, что все хорошие числа лежат в построенных отрезках. Предположим противное и рассмотрим минимальное хорошее $k$, для которого это не так. Поскольку $m_k > \alpha$, то найдется $l \leq к$, для которого $S(1,k) > \alpha$. Так как любое число вне построенных отрезков не превосходит $а$, то отрезок $[l, k]$ пересекается с каким-то отрезком $[p_j, q_j]$. Пусть $[p_i, q_i]$ - самый правый отрезок, лежащий левее $k$. Если $k > q_i + 1,$ то $S(q_i + 2,k) \leq \alpha,$ откуда $S(l, q_i + 1) > \alpha$, что противоречит выбору $k$. Поэтому $k = q_i + 1$. Из принципа выбора отрезков следует, что $l = p_i$ (иначе получаем противоречие с выбором $q_i$). Если $l > p_i,$ то $S(p_i, l - 1) > \alpha,$ откуда $S(p_i, q_i + 1) > \alpha$, чего не может быть. Если же $l < p_i$, то из $S(p_i, q_i + 1) \leq \alpha$ следует $S(l, p_i - 1) > \alpha$, т. е. $p_i - 1$ - хорошее число, не принадлежащее ни одному из отрезков $[p_j, q_j]$ и меньшее $k$, что противоречит сделанному предположению. Таким образом, все хорошие $k$ лежат в построенных отрезках.
Получается, что количество хороших чисел не превосходит $\sum_{ }^{ }(q_i - p_i + 1)$. Учитывая, что по построению отрезков
$ \sum_{ }^{ }a_k \geq \sum_{k \in [p_i, q_i]}^{ } > a \cdot \sum_{ }^{ }(q_i - p_i +1)$,
мы получаем утверждение задачи.
Второе решение. Пусть $b_i = а_1 + \cdots + a_i$. Ясно, что $b_1 \leq b_2 \leq \cdots \leq b_n$. Тогда
$\frac{a_{l+1} +a_{k-m+2} + \cdots + a_k}{m} = \frac{b_k - b_l}{k-l}$.
Рассмотрим на координатной плоскости точки $B_0(0,0), B_1(1,b_1), B_2(2, b_2), \cdots, В_n(n, b_n)$. Тогда отношение $\frac{b_k - b_l}{k-l}$ будет равно тангенсу угла наклона прямой $B_iB_k$. Значит, условие $m_k > а$ будет равносильно тому, что прямая, проходящая через $B_k$ с углом наклона $arctg \alpha$ (эту прямую назовем $l_k$) будет проходить выше хотя бы одной из точек $B_l$ при $l < к$ (такую точку $B_k$ будем называть хорошей). Выражение $\frac{a_1 + a_2 + \cdots + a_n}{ \alpha}$ будет равно $b_n/ \alpha$, и это будет расстояние между точкой $(n, 0)$ и точкой пересечения $l_n$ с осью абсцисс.
Докажем индукцией по количеству точек $n$, что это расстояние больше числа хороших точек. База очевидна. Если точка $B_n$ не хорошая, то выбросим ее, при этом число хороших точек не изменится, а отрезок уменьшится (так как $b_{n-1} \leq b_n$). Если же она хорошая, то пусть $B_k$ - ближайшая (по оси абсцисс) точка, лежащая под $l_n$. Тогда выбросим все точки от $B_{k+1}$ до $B_n$ (они все хорошие), количество хороших точек уменьшится на $n - k$, а отрезок - больше, чем на $n - k$.
Дана последовательность неотрицательных чисел $a_1, a_2, \cdots, a_n$. Для любого $k$ от 1 до $n$ обозначим через $m_k$ величину $ \underset {l=1,2,\cdots,k}{max} \frac {a_{k-l+1}+a_{k-l+2}+\cdots+a_k}{l}$. Докажите, что при любом $a > 0$ число тех $k$, для которых $mk > a$, меньше, чем $ \frac {a_1+a_2+\cdots+a_n}{a}$.
Решение:
Первое решение. Для $1 \leq i \leq j \leq n$ обозначим через $[i, j]$ отрезок натурального ряда от $i$ до $j$. Пусть
$S(i, j) = \frac{a_i + a_{i +1} + \cdots + a_j}{j - i +1}$.
Заметим, что из $S(i,j) > \alpha$ и $S(j + 1, l) > \alpha$ следует $S(i, l) > \alpha$.
Выделим в отрезке $[1,n]$ несколько отрезков $[p_i,q_i]$ по следующему принципу: $i$-й отрезок начинается с минимального числа $p$ такого, что $a_p$ превосходит $a$ и не лежит в ранее построенных отрезках (если такого нет, то построение закончено); заканчивается он таким максимальным $q$, что при любом $j$ из $[p_i, q]$ среднее чисел от $a_{p_i}$ до $a_j$ превосходит $\alpha$. По построению $p_{i+1} > q_i + 1$.
Назовем натуральное число $k$ хорошим, если $m_k > \alpha$. Докажем, что все хорошие числа лежат в построенных отрезках. Предположим противное и рассмотрим минимальное хорошее $k$, для которого это не так. Поскольку $m_k > \alpha$, то найдется $l \leq к$, для которого $S(1,k) > \alpha$. Так как любое число вне построенных отрезков не превосходит $а$, то отрезок $[l, k]$ пересекается с каким-то отрезком $[p_j, q_j]$. Пусть $[p_i, q_i]$ - самый правый отрезок, лежащий левее $k$. Если $k > q_i + 1,$ то $S(q_i + 2,k) \leq \alpha,$ откуда $S(l, q_i + 1) > \alpha$, что противоречит выбору $k$. Поэтому $k = q_i + 1$. Из принципа выбора отрезков следует, что $l = p_i$ (иначе получаем противоречие с выбором $q_i$). Если $l > p_i,$ то $S(p_i, l - 1) > \alpha,$ откуда $S(p_i, q_i + 1) > \alpha$, чего не может быть. Если же $l < p_i$, то из $S(p_i, q_i + 1) \leq \alpha$ следует $S(l, p_i - 1) > \alpha$, т. е. $p_i - 1$ - хорошее число, не принадлежащее ни одному из отрезков $[p_j, q_j]$ и меньшее $k$, что противоречит сделанному предположению. Таким образом, все хорошие $k$ лежат в построенных отрезках.
Получается, что количество хороших чисел не превосходит $\sum_{ }^{ }(q_i - p_i + 1)$. Учитывая, что по построению отрезков
$ \sum_{ }^{ }a_k \geq \sum_{k \in [p_i, q_i]}^{ } > a \cdot \sum_{ }^{ }(q_i - p_i +1)$,
мы получаем утверждение задачи.
Второе решение. Пусть $b_i = а_1 + \cdots + a_i$. Ясно, что $b_1 \leq b_2 \leq \cdots \leq b_n$. Тогда
$\frac{a_{l+1} +a_{k-m+2} + \cdots + a_k}{m} = \frac{b_k - b_l}{k-l}$.
Рассмотрим на координатной плоскости точки $B_0(0,0), B_1(1,b_1), B_2(2, b_2), \cdots, В_n(n, b_n)$. Тогда отношение $\frac{b_k - b_l}{k-l}$ будет равно тангенсу угла наклона прямой $B_iB_k$. Значит, условие $m_k > а$ будет равносильно тому, что прямая, проходящая через $B_k$ с углом наклона $arctg \alpha$ (эту прямую назовем $l_k$) будет проходить выше хотя бы одной из точек $B_l$ при $l < к$ (такую точку $B_k$ будем называть хорошей). Выражение $\frac{a_1 + a_2 + \cdots + a_n}{ \alpha}$ будет равно $b_n/ \alpha$, и это будет расстояние между точкой $(n, 0)$ и точкой пересечения $l_n$ с осью абсцисс.
Докажем индукцией по количеству точек $n$, что это расстояние больше числа хороших точек. База очевидна. Если точка $B_n$ не хорошая, то выбросим ее, при этом число хороших точек не изменится, а отрезок уменьшится (так как $b_{n-1} \leq b_n$). Если же она хорошая, то пусть $B_k$ - ближайшая (по оси абсцисс) точка, лежащая под $l_n$. Тогда выбросим все точки от $B_{k+1}$ до $B_n$ (они все хорошие), количество хороших точек уменьшится на $n - k$, а отрезок - больше, чем на $n - k$.
