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