СПбГУ 2025, 10-11 классы, задача 5
( баллов) В школе учеников. У директора есть много карточек с числами от до . Он раздал карточки ученикам так, что ученик мог получить несколько карточек (возможно, ни одной или одну), при этом каждый ученик получил не более чем одну карточку каждого вида. Любые два ученика получили разные наборы карточек. Оказалось, что если карточка с числом () есть более чем у учеников, то она есть хотя бы у учеников. При каком наибольшем такое возможно?
Ответ: .
Решение. Пусть карточка с числом есть более чем у ученика. Отберём её у всех учеников, у кого она есть, и дадим по одной карточке с числом каждому из остальных учеников. Несложно видеть, что после такой замены всё ещё любые два ученика получили разные наборы карточек. После такой замены карточка с любым числом будет не более чем у учеников, т. е. всего карточек у всех учеников не более .
Пусть есть учеников, у которых не более одна карточки. Тогда оставшиеся не более чем карточек находятся у учеников, у которых хотя бы две карточки. Поэтому всего учеников не более
где отвечает за возможно одного ученика совсем без карточек, а , поскольку всего сто разных карточек и нет учеников с одинаковым набором из одной карточки.
Пример легко построить из оценки: возьмём ученика без карточек, учеников с одной карточкой, а также учеников со всеми возможными парами карточек. Тогда каждое конкретное число встречается ровно у учеников.