Клетчатые задачи и комбинаторные подсчёты на СПБГУ
Ошибка.
Попробуйте повторить позже
В школе 
учеников. У директора есть много карточек с числами от 
до 
Он раздал карточки ученикам так, что ученик
мог получить несколько карточек (возможно, ни одной или одну), при этом каждый ученик получил не более чем одну
карточку каждого вида. Любые два ученика получили разные наборы карточек. Оказалось, что если карточка с числом 
есть более чем у 
учеников, то она есть хотя бы у 
учеников. При каком наибольшем 
такое
возможно?
Источники:
Подсказка 1
Исходя из условия про m-100 учеников, можно сделать одну хитрую махинацию с карточкой, которая есть у хотя бы 101 ученика, которая приведёт к тому, что карточка с любым номером будет не более чем у 100 учеников.
Подсказка 2
Что, если все такие карточки отнять у учеников, у которых они есть и отдать тем, у кого их нет? Почему условие задачи не нарушится?
Подсказка 3
Пусть у l учеников одна карточка. Сколько тогда максимум может быть учеников, у которых их хотя бы две? Попробуйте, учитывая предыдущие подсказки, оценить суммарное количество карточек у учеников. Также оцените l.
Пусть карточка с числом 
есть более чем у 
ученика. Отберём её у всех учеников, у кого она есть, и дадим по одной карточке с
числом 
каждому из остальных учеников. Несложно видеть, что после такой замены всё ещё любые два ученика получили разные наборы
карточек. После такой замены карточка с любым числом будет не более чем у 
учеников, т.е. всего карточек у всех учеников не более
Пусть есть 
учеников, у которых не более одной карточки. Тогда оставшиеся не более чем 
карточек находятся у
учеников, у которых хотя бы две карточки. Поэтому всего учеников не более
где 
отвечает за, возможно, одного ученика совсем без карточек, а 
поскольку всего сто разных карточек и нет учеников с
одинаковым набором из одной карточки.
Пример легко построить из оценки: возьмём ученика без карточек, 
учеников с одной карточкой, а также 
учеников со всеми возможными 
парами карточек. Тогда каждое конкретное число встречается ровно у 
учеников.
Специальные программы
Программа
лояльности v2.0
Приглашай друзей в Школково и получай вознаграждение до 10%!
Крути рулетку
и выигрывай призы!
Крути рулетку и покупай курсы со скидкой, которая привязывается к вашему аккаунту.
Бесплатное онлайн-обучение
Для школьников из приграничных территорий России, проживающих в ДНР, ЛНР, Херсонской, Запорожской, Белгородской, Курской, Брянской областях и Крыму.
Налоговые вычеты
Узнай, как получить налоговый вычет при оплате обучения в «Школково».
Специальное предложение
для учителей
Бесплатный доступ к любому курсу подготовки к ЕГЭ, ОГЭ и олимпиадам от «Школково». Мы с вами делаем общее и важное дело, а потому для нас очень значимо быть чем-то полезными для учителей по всей России!
Вернём деньги за курс
за твою сотку на ЕГЭ
Сдать экзамен на сотку и получить обратно деньги за подготовку теперь вполне реально!
