Пример 4. На плоскости дано n окружностей. Доказать, что при любом расположении этих окружностей образуемую ими карту можно правильно раскрасить двумя красками.

Решение.

При n=1 наше утверждение очевидно.

Предположим, что наше утверждение справедливо для любой карты, образованной n окружностями, и пусть на плоскости задано n+1 окружностей. Удалив одну из этих окружностей, мы получим карту, которую в силу сделанного предположения можно правильно раскрасить двумя красками, например черной и белой.

Восстановим затем отброшенную окружность и по одну сторону от нее (например, внутри) изменим цвет каждой области на противоположный (т.е. черный – на белый и наоборот); легко видеть, что при этом мы получим карту, правильную раскрашенную двумя красками.

Пример 5. Для того чтобы карту можно было правильно раскрасить двумя красками, необходимо и достаточно, чтобы в каждой ее вершине сходилось четное число границ.

Решение.

Необходимость этого условия очевидно, так как если в какой-нибудь вершине карты сходится нечетное число границ, то уже страны, окружающие эту вершину, нельзя правильно раскрасить двумя красками.

А В

Для доказательства достаточности условия проведем индукцию по числу границ карты.

Для карты с двумя границами утверждение очевидно.

Предположим, что утверждение справедливо для любой карты, в каждой вершине которой сходится четное число границ и общее число границ которой не превосходит n, и пусть дана карта S, имеющая n+1 границ и удовлетворяющая тому же условию. Начиная с произвольной вершины А карты S, станем двигаться в произвольном направлении вдоль границ карты. Ввиду конечности числа вершин карты мы вернемся в конце концов в одну из уже проведенных вершин (карта не имеет крайних вершин, потому что на ней нет неразделяющих границ) и сможем выделить некоторый не имеющий самопересечений замкнутый контур, состоящий из границ карты. Удалив этот контур, мы получим контур S1 с меньшим числом границ, в каждой вершине которой также сходится четное число границ (потому что в каждой вершине карты S отбрасывается четное число границ – 0 или 2). В силу индуктивного предположения карту S1 можно правильно раскрасить двумя красками.

Восстановив отброшенный контур и изменив все цвета с одной стороны от него (например, внутри), мы и получим правильную раскраску карты S.

Список использованной литературы.

1. Вавилов В.В. и др. Задачи по математике / Вавилов В.В., Мельников И.И., Олехник С.Н., Пасиченко П.И. - М.: Наука. - 1987. - С.396.

2. Виленкин Н.Я. Индукция. Комбинаторика/ Пособие для учителей. - М.: Просвещение. – 1976. - С.4 - 18.

3. Головина Л.И., Яглом И.М. Индукция в геометрии. - М.: Госуд. издат. т-теор литер. - 1956 - С.100.

4. Пособие по математике для поступающих в вузы/ Под ред. Яковлева Г.Н. - М.: Наука. – 1981. - С.47-51.

5. Рубанов И.С. Как обучать методу математической индукции/ Математика в школе. - N1. – 1996. - С. 14-20.

6. Соломинский И.С. Метод математической индукции. - М.: Наука. - 1974. - 63с.

7. Соломинский И.С., Головина Л.И., Яглом И.М. О математической индукции. - М.:Наука. – 1967. - С.7-59.