Решение задачи 455

Условие:

Лиза Яковлева поет в течение месяца не менее одной песни в день, но не более 12 песен в любую неделю. Докажите, что найдётся несколько последовательных дней, в течение которых она споет ровно 20 песен.

Решение:

Рассмотрим следующие 21 чисел: количество песен, спетых в первый день, число песен, спетых за первые два дня, ..., число песен, спетых за первые 21 день. Рассмотрим эти числа по модулю 20. По принципу Дирихле найдутся два одинаковых числах, пусть они с номерами i и j (i<j). Это значит, что за первые i дней и за первые j дней Лиза спела одинаковое число песен по модулю 20. То есть с i+1-го дня по j-ый она спела кратное число песен, кратное 20. Это точно не ноль, потому что каждый день Лиза поет хотя бы одну песню, и точно меньше 40, потому что за первые 21 день она споет максимум 3*12=36 песен. Значит, с i+1-го дня по j-ый она спела ровно 20 песен.