Задача
В ряд выписаны несколько натуральных чисел с суммой 2019. Никакое число и никакая сумма нескольких подряд записанных чисел не равна 40. Какое наибольшее количество чисел могло быть выписано?
Решение
Лемма. Сумма любых сорока подряд записанных чисел не меньше 80.
Доказательство. Пусть числа $a_{1}, ..., a_{40}$ записаны подряд. Cреди чисел $b_{0}=0, b_{1}=a_{1}, b_{2} = a_{1} + a_{2}, ..., b_{40} = a_{1} + a_{2} + ... + a_{40}$ найдутся два – $b_i$ и $b_j$ ($i < j$) – с одинаковым остатком при делении на 40. Тогда сумма $a_{i+1} + a_{i+2} + ... + a_j$ кратна 40, а значит, не меньше 80. Оценка. Пусть выписано $n$ > 1019 чисел. По лемме, сумма первых 1000 = 25·40 из них не меньше 25·80 = 2000. Сумма оставшихся чисел (их по крайней мере 20) не меньше 20. Значит, вся сумма не меньше 2020. Противоречие.
Пример. 25 групп 1, ..., 1, 41 (в каждой группе 39 единиц и число 41) и затем 19 единиц.
Ответ
1019 чисел.
Чтобы оставлять комментарии, войдите или зарегистрируйтесь