Задача 78090

Темы:    [ Теория алгоритмов (прочее) ] [ Разбиения на пары и группы; биекции ]

Сложность: 4+ Классы: 11

Условие

Подряд выписаны n чисел, среди которых есть положительные и отрицательные. Подчеркивается каждое положительное число, а также каждое число, сумма которого с несколькими непосредственно следующими за ним числами положительна. Докажите, что сумма всех подчеркнутых чисел положительна.

Решение

Пусть a₁, a₂, ..., a_n. Подчеркнём число a_i k + 1 чертами, если k — наименьшее число, для которого a_i + a_{i + 1} + a_{i + 2} + ... + a_{i + k} > 0 (положительное число a₁ подчёркивается одной чертой). Ясно, что если число a_i подчёркнуто k + 1 чертами, то числа a_{i + 1}, a_{i + 2}, ... a_{i + k} подчёркнуты соответственно k, k - 1, ..., 2, 1 чертами. Подчёркнутые числа разобьём на группы следующим образом. Сначала возьмём числа, подчёркнутые наибольшим числом черт (пусть это число черт равно K), и следующие за каждым из них K - 1 чисел. Затем возьмём числа, подчёркнутые K - 1 чертами, и следующие за каждым из них K - 2 чисел, и т.д. Сумма чисел в каждой группе положительна.

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

олимпиада
Название	Московская математическая олимпиада
год
Номер	19
Год	1956
вариант
Класс	10
Тур	2
задача
Номер	1