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

600 қораптың әрқайсысында не 5, не 18, не 22 шар бар (және барлық 5, 18, 22 шары бар қораптың үш түрі де кездеседі). Ішінде жалпы 2025 шар болатындай, осы 600 қораптан бірнеше қорап таңдап алуға болатынын дәлелдеңіз. ( И. Богданов )

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

Из принципа Дирихле мы знаем то что есть коробка с каким-то кол во шаров, которых больше 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, из-за этого условия задачи реальны