В магазин привезли 25 ящиков конфет трёх разных сортов (в каждом ящике – только один сорт). Докажите, что есть хотя бы 9 ящиков с одним и тем же сортом конфет.

Решение по принципу Дирихле (толкование задач распределения по корзинам).

1. Обозначим три сорта конфет как A, B, C. Пусть в ящиках встречается количество ящиков каждого сорта: xA, xB, xC. Тогда xA + xB + xC = 25.

2. Предположим противное: каждый сорт встречается в не более чем 8 ящиках, то есть xA ≤ 8, xB ≤ 8, xC ≤ 8.

3. Тогда суммарное число ящиков не может превышать 8 + 8 + 8 = 24. Но по условию всего 25 ящиков, это противоречит равенству xA + xB + xC = 25.

4. Следовательно, наше предположение неверно: существует такой сорт, который встречается в как минимум 9 ящиках. То есть какое-то x рано или поздно ≥ 9.

5. Пример достижения минимума максимального значения: распределение 9 ящиков одного сорта, 8 — второго, 8 — третьего. Тогда максимум равен 9, что и совпадает с полученным доказательством.

Вывод: существует как минимум 9 ящиков с одним и тем же сортом конфет. (Общее правило: при разбиении n объектов на k категорий максимум в одной категории ≥ ceil(n/k). Здесь ceil(25/3) = 9.)