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