Олимпиада имени Леонарда Эйлера 2025-2026 учебный год, I тур дистанционного этапа

В каждой из 600 коробок лежит либо 5, либо 18, либо 22 шарика, причём все три типа присутствуют. Докажите, что можно выбрать несколько коробок, в которых суммарно ровно 2025 шариков. ( И. Богданов )

Комментарий/решение

Из принципа Дирихле мы знаем то что есть коробка с каким-то кол во шаров, которых больше 200. Разберем три случая

1) Есть хотя бы 200 коробок с 22 шарами.

Тогда мы возьмем 91 из них, и по условию у нас есть хотя бы одна коробка где есть 5 и 18 шаров. 91*22+5+8=2025

2) Есть хотя бы 200 коробок с 18 шарами

Тогда возьмем 111 из них, и получим

111*18+22+5=2025

3) Есть хотя бы 200 шаров с 5 шарами

Из 1 и 2 мы знаем, что если есть хотя бы 91 коробок с 22 шарами или же 111 коробок с 18, то условие выполняются. Тогда разберем случай где кол во коробок с 22 шарами меньше 91, и кол во коробок с 18 меньше 91.

Т.е. коробок с 5 шарами хотя бы 600-110-90=400

397*5+22+18=2025 чтд

Доказательство:

Важное примечание в задаче: Есть все типы коробок. Это важно.

Сумма 5,18,22 равна 45. Мы должны расматривать все худшие состояния. Например:

1) Все коробки наполнены по 5 шариков, кроме 2, которые наполнены по 18 и 22.

2025-(18+22+5)=1980

1980 mod 5 = 0 В этом случие мы можем собрать 2025 шариков.

2) Все коробки наполнены по 18 шариков, кроме 2, которые наполнены по 5 и 22.

2025-(5+22+18)=1980

1980 mod 18 = 0 Мы тоже можем собрать 2025 шариков.

3) Все коробки наполнены по 22 шариков, кроме 2, которые наполнены по 18 и 5.

2025-(5+22+18)=1980

1980 mod 22 = 0 Здесь мы тоже можем.

Все доказано

P.S.

Почему я отнимал 45. Потому что в задаче говорится, что как минимум есть 1 коробка каждого типа. К тому же, 5,18,22 делятся на 1980, из-за этого условия задачи реальны