Question

По кругу стоят 2007 целых неотрицательных чисел, сумма которых равна 7025. Докажите, что среди них есть четыре идущих подряд числа, сумма которых больше 14. Можно побистрее?

Answer 1

Предположим, что сумма любых четырёх подряд идущих чисел не более 14. Рассмотрим все возможные четвёрки подряд идущих чисел и посчитаем сумму всех чисел в них. С одной стороны, эта сумма равна 7025 * 4 = 28100, так как каждое число было посчитано ровно 4 раза, а сумма всех чисел в круге равна 7025. С другой стороны, эта сумма не больше 14 * 2007 = 28098, так как всего всевозможных четвёрок чисел ровно 2007. Противоречие. Значит, найдётся четвёрка подряд идущих чисел, сумма которых больше 14.

Answer 2

Да, можно доказать это побыстрее, используя принцип Дирихле (Принцип ящиков Дирихле).

Принцип Дирихле утверждает следующее: если n+1 объектов размещены в n ящиках, то хотя бы в одном из ящиков будет не менее двух объектов.

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

Разобьем последовательность на группы по 4 числа (первые 4, следующие 4, и так далее). Поскольку каждая группа содержит 4 числа, и сумма четырех идущих подряд чисел не превышает 14, то сумма каждой группы не превышает 14.

Теперь посчитаем сумму всех чисел в последовательности: 7025. Если мы поделим эту сумму на 4 (число чисел в каждой группе), получим 7025 / 4 = 1756.25.

Теперь заметим, что 1756.25 > 14, и это означает, что хотя бы в одной из групп сумма чисел должна быть больше 14. Но это противоречит нашему предположению о том, что ни у каких четырех идущих подряд чисел сумма не превышает 14.

Таким образом, наше предположение неверно, и среди 2007 целых неотрицательных чисел, сумма которых равна 7025, обязательно найдутся четыре идущих подряд числа, сумма которых больше 14.