Условие
На плоскости проведено
n прямых линий. Доказать, что области, на которые эти
прямые разбивают плоскость, можно так закрасить двумя красками (каждая область
закрашивается только одной краской), что никакие две соседние области (т.е.
области, соприкасающиеся только по отрезку прямой) не будут закрашены одной и
той же краской.
Решение
Применим индукцию по
n. При
n = 1 утверждение очевидно. Предположим, что
утверждение доказано для любой конфигурации из
n прямых. Рассмотрим
конфигурацию из
n + 1 прямых, выбросим одну прямую и раскрасим требуемым
способом плоскость, разбитую оставшимися
n прямыми. По одну сторону от
выброшенной прямой эту раскраску мы сохраним, а по другую сторону — заменим
на противоположную.
Источники и прецеденты использования
