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