Принцип Дирихле
Готовиться с нами - ЛЕГКО!
Ошибка.
Попробуйте повторить позже
Школьники участвовали в олимпиаде, проходящей в два тура. В каждый из двух дней они рассаживались по нескольким кабинетам,
при этом никто не сидел в кабинете в одиночестве. Количество кабинетов в разные дни олимпиады может отличаться.
Докажите, что найдутся два школьника 
и 
такие, что в первый день 
и 
писали олимпиаду в кабинетах с
одинаковым количеством участников, и во второй день 
и 
писали олимпиаду в кабинетах с одинаковым количеством
участников.
Подсказка 1
Предположим, что не существует двух школьников, которые в оба дня писали олимпиаду в кабинетах с одинаковым числом участников. Что это означает для распределения по кабинетам? К каким ограничениям приводит такое предположение?
Подсказка 2
Пусть на первом туре было a₁ кабинетов с b₁ участниками, a₂ с b₂ участниками и т.д., а на втором — c₁ кабинетов с d₁ участниками, c₂ с d₂ и т.д. Подумайте, что можно сказать о школьниках, сидевших в кабинетах с bᵢ участниками в первый день. Куда они могли попасть на второй?
Подсказка 3
Школьников, сидевших в кабинетах с максимальным числом участников bᵢ в первый день, было не меньше чем aᵢ · bᵢ. Если предположить, что все они попали во второй день в кабинеты с числом участников, отличным от bᵢ, то понадобится достаточно много других кабинетов. Оцените, сколько именно.
Подсказка 4
Поскольку bᵢ — максимальное из всех bᵢ и dⱼ, то в кабинете с числом участников, отличным от bᵢ, может сидеть не более bᵢ - 1 школьников. Попробуйте прикинуть, сколько таких кабинетов нужно, чтобы вместить всех школьников из кабинетов с bᵢ участниками. Сравните с тем, сколько всего кабинетов было во второй день, и получите противоречие.
Пусть на первом туре было 
кабинетов с 
участниками, 
кабинетов с 
участниками (все 
и 
по условию).
Аналогично во второй тур пусть было 
кабинетов с 
участниками, 
кабинетов с 
участниками. Также очевидно, что
и 
Предположим, что такие два ученика не найдутся. Рассмотрим участников, писавших первый тур в одном из 
кабинетов с 
числом
участников. Тогда второй тур они должны были писать в кабинетах с разным числом участников, тогда 
должно быть не меньше,
чем
То есть 
Но тогда по аналогичным соображениям 
— противоречие.
Специальные программы
Программа
лояльности v2.0
Приглашай друзей в Школково и получай вознаграждение до 10%!
Крути рулетку
и выигрывай призы!
Крути рулетку и покупай курсы со скидкой, которая привязывается к вашему аккаунту.
Бесплатное онлайн-обучение
Для школьников из приграничных территорий России, проживающих в ДНР, ЛНР, Херсонской, Запорожской, Белгородской, Курской, Брянской областях и Крыму.
Налоговые вычеты
Узнай, как получить налоговый вычет при оплате обучения в «Школково».
Специальное предложение
для учителей
Бесплатный доступ к любому курсу подготовки к ЕГЭ, ОГЭ и олимпиадам от «Школково». Мы с вами делаем общее и важное дело, а потому для нас очень значимо быть чем-то полезными для учителей по всей России!
Вернём деньги за курс
за твою сотку на ЕГЭ
Сдать экзамен на сотку и получить обратно деньги за подготовку теперь вполне реально!
