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