ВсОШ 2022, 10 класс, задача 3

Ответ. .

Решение. Оценка. Докажем, что «не работает». Пусть дан набор из конфет. Назовём сорт критическим, если конфет этого сорта ровно (среди всех данных конфет). Пусть у нас критических сортов, тогда всего конфет не менее : . Уберём по одной конфете каждого критического сорта и организуем группу из оставшихся конфет. Для этой группы нет сорта, представленного ровно конфетами. Кроме того, . Значит, в рассматриваемой группе не менее конфет, поэтому условие задачи не выполняется.

Пример. Теперь приведём пример ситуации, в которой у Васи может быть конфет. Пусть у него есть ровно по конфет сортов. Пусть выбрана группа, для которой нет сорта, представленного ровно конфетами. Тогда в эту группу не входит хотя бы одна конфета каждого сорта (иначе говоря, ни один сорт не будет взят полностью), т. е. группа содержит не более конфет, значит, условие задачи выполнено.

Замечание 1. Оценка может быть доказана также следующим, несколько другим способом. Предположим, что некоторое «работает», т. е. существует набор из конфет, удовлетворяющий условию задачи. Тогда в наборе есть в точности конфет некоторого сорта . Уберём конфету сорта и рассмотрим группу из оставшихся конфет. В группе есть в точности конфет некоторого сорта , при этом сорт отличен от , так как в есть ровно конфет сорта . Уберём из конфету сорта и рассмотрим группу из оставшихся конфет, в котором найдём конфет нового сорта , и т. д., продолжим по шагам убирать по одной конфете и рассматривать группы оставшихся конфет. Так дойдём до группы , состоящей из конфет. При этом, согласно нашему алгоритму, содержит по конфет сортов , значит . Имеем , откуда и .

Замечание 2. Пример при единственный.