Решаю школьную задачу на тему "индукция". Вроде бы достаточно тривиальная, но смутил один момент в условии.
Условие:На плоскости расположено несколько треножников (фигур, состоящих из 3 лучей с общей вершиной). Докажите, что
если никакие два из ограничивающих треножники лучей не параллельны, то части, на которые они разбивают плоскость, можно выкрасить тремя красками так, чтобы части, граничащие по отрезку или лучу, оказались бы выкрашены в разные цвета.
Мое решение:При одном треножнике понятно, просто красим в разные цвета все три части.
Предположим, что для
треножников условие доказано. Нарисуем на плоскости
треножников и покрасим в три цвета в соответствии с условием задачи. Нарисуем еще один треножник. Он как-то разделит плоскость на три части. Одну из частей не трогаем, во второй меняем цвета в таком порядке: 1й на 2й, 2й на 3й, 3й на 1й (циклично увеличиваем номер цвета на единицу), а в третьей - 1й на 3й, 2й на 1й, 3й на 2й (увеличиваем на два). Внутри этих трёх частей условие выполнено, т.к. одинаковые цвета перешли в одинаковые, а разные - в разные. На границах же этих частей -
т.к. ни один луч нового треножника больше чем на точку не совпал ни с одним лучом старых - до изменения цвета были одинаковыми, но после - гарантированно разными, т.к. в каждой части номер одного и тот же цвета поменялся на разную величину: 0, 1 и 2.
Развитие темы:Если не использовать часть условия про недопустимость параллельности, то можно придумать вот такой контрпример, который разрушает мое доказательство:
(здесь вертикальный луч верхнего треножника - часть вертикального луча нижнего)
Код:
|
*
/|\
*
/ \
Тогда при циклической замене цветов две верхних части вполне могут получить одинаковый цвет. Но при этом раскрасить такую картинку в соответствии с условием все ещё можно, просто доказательство на этот случай не обобщается. В связи с чем у меня возник вопрос:
1. Можно ли (в теории) опустить эту часть условия про параллельность, и утверждение задачи все ещё останется верным, ИЛИ
2. Есть ли контрпример, где какие-то несколько лучей этих проклятых треножников параллельны, и который действительно нельзя раскрасить в три цвета. Я не смог придумать такого.
Надеюсь это не равносильно теореме четырех красок
. Хотя не должно, т.к. цвета всего три.