На прямоугольном листе бумаги провели несколько отрезков, его сторонам. Эти отрезки разбили лист на параллельных несколько прямоугольников, внутри которых нет проведённых линий. Петя хочет провести в каждом из прямоугольников разбиения одну диагональ, разбив его на два треугольника, и окрасить каждый треугольник либо в чёрный, либо в белый цвет. Верно ли, что он обязательно сможет это сделать так, чтобы никакие два одноцветных треугольника не имели общего отрезка границы?
1 Ответ
Ответ: Да, Петя всегда сможет раскрасить треугольники так, чтобы никакие два одноцветных треугольника не имели общего отрезка границы.
Доказательство:
Рассмотрим граф, вершинами которого являются прямоугольники разбиения. Соединим два прямоугольника ребром, если они имеют общий отрезок границы. Заметим, что этот граф является двудольным. Это можно доказать, раскрасив прямоугольники в шахматном порядке.
Теперь раскрасим диагонали в каждом прямоугольнике следующим образом:
Для прямоугольников из первой доли выберем диагональ, идущую из левого верхнего угла в правый нижний угол. Раскрасим треугольник слева от диагонали в черный цвет, а справа — в белый.
Для прямоугольников из второй доли выберем диагональ, идущую из правого верхнего угла в левый нижний угол. Раскрасим треугольник слева от диагонали в белый цвет, а справа — в черный.
Тогда никакие два одноцветных треугольника не будут иметь общего отрезка границы. Действительно, если два прямоугольника имеют общую границу, то они принадлежат разным долям графа, и, следовательно, диагонали и цвета треугольников будут выбраны так, чтобы смежные треугольники имели разные цвета.