Задача 66744

Темы:    [ Деление с остатком. Арифметика остатков ] [ Последовательности (прочее) ]

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

Условие

Автор: Шаповалов А.В.

В ряд выписаны несколько натуральных чисел с суммой 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 чисел.

Замечания

5 баллов

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

олимпиада
Название	Турнир городов
номер/год
Дата	2018/19
Номер	40
вариант
Вариант	весенний тур, базовый вариант, 10-11 класс
задача
Номер	5