Задача 109710

Темы:    [ Геометрические интерпретации в алгебре ] [ Графики и ГМТ на координатной плоскости ] [ Индукция в геометрии ] [ Системы отрезков, прямых и окружностей ]

Сложность: 5+ Классы: 9,10,11

Условие

Автор: Дольников В.Л.

Дана последовательность неотрицательных чисел a₁ , a₂ , a_n . Для любого k от 1 до n обозначим через m_k величину

_l=1,2,..,k .
Докажите, что при любом α>0 число тех k , для которых m_k>α , меньше, чем a₁+a₂+...+a_n α.

Решение

Первое решение. Для 1 i j n обозначим через [i,j] отрезок натурального ряда от i до j . Пусть

S(i,j)=(a_i+a_i+1+...+a_j) /(j-i+1).
Заметим, что из S(i,j)>α и S(j+1,l)>α следует S(i,l)>α .

Выделим в отрезке [1,n] несколько отрезков [p_i, q_i] по следующему принципу: i -й отрезок начинается с минимального числа p такого, что a_p превосходит α и не лежит в ранее построенных отрезках (если такого нет, то построение закончено); заканчивается он таким максимальным q , что при любом j из [p_i, q] среднее чисел от a_pi до a_j превосходит α . По построению p_i+1>q_i+1 .

Назовем натуральное число k хорошим} если m_k>α .
Докажем, что все хорошие числа лежат в построенных отрезках.
Предположим противное и рассмотрим минимальное хорошее k , для которого это не так.
Поскольку m_k>α , то найдется l k , для которого S(l,k)>α . Так как любое число вне построенных отрезков не превосходит α , то отрезок [l , k] пересекается с каким-то отрезком [p_j,q_j] .

Пусть [p_i, q_i] – самый правый отрезок, лежащий левее k . Если k>q_i+1 , то S(q_i+2,k)α , откуда S(l,q_i+1)>α , что противоречит выбору k .
Поэтому k=q_i+1 . Из принципа выбора отрезков следует, что l p_i (иначе получаем противоречие с выбором q_i ). Если l>p_i , то S(p_i, l-1)>α , откуда S(p_i, q_i+1)>α , чего не может быть. Если же l<p_i , то из S(p_i,q_i+1) α следует S(l,p_i-1)>α , т.е. p_i-1 – хорошее число, не принадлежащее ни одному из отрезков [p_j,q_j] и меньшее k , что противоречит сделанному предположению.

Таким образом, все хорошие k лежат в построенных отрезках.

Получается, что количество хороших чисел не превосходит (q_i-p_i+1).
Учитывая, что по построению отрезков [p_i,q_i]
a_k a_k>α·(q_i-p_i+1),
мы получаем утверждение задачи.


Второе решение. Пусть b_i=a₁+...+a_i . Ясно, что b₁ b₂ .. b_n . Тогда
=.
Рассмотрим на координатной плоскости точки B₀(0,0) , B₁(1,b₁) , B₂(2,b₂) , B_n(n,b_n) . Тогда отношение будет равно тангенсу угла наклона прямой B_lB_k . Значит, условие m_k>α будет равносильно тому, что прямая, проходящая через B_k с углом наклона arctg, α (эту прямую назовем l_k ) будет проходить выше хотя бы одной из точек B_l при l<k (такую точку B_k будем называть хорошей). Выражение будет равно b_n/α , и это будет расстояние между точкой (n,0) и точкой пересечения l_n с осью абсцисс.

Докажем индукцией по количеству точек n , что это расстояние больше числа хороших точек.
База очевидна. Если точка B_n не хорошая, то выбросим ее, при этом число хороших точек не изменится, а отрезок уменьшится (так как b_n-1 b_n ). Если же она хорошая, то пусть B_k – ближайшая (по оси абсцисс) точка, лежащая под l_n . Тогда выбросим все точки от B_k+1 до B_n (они все хорошие), количество хороших точек уменьшится на n-k , а отрезок – больше, чем на n-k .

Источники и прецеденты использования

олимпиада
Название	Всероссийская олимпиада по математике
год
Год	2000
Этап
Вариант	5
Класс
Класс	11
задача
Номер	00.5.11.4