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