Таблицы Брадиса

Пусть для определенности это автомобиль.

Пусть для определенности это автомобиль.

Элементы математики в задачах - Г. А. Мерзон

Задача 4. На острове Буяне каждые два города соединены напрямую автомобильной либо железной дорогой. Докажите, что или из любо­го города в любой другой можно добраться на автомобиле, или из любого города в любой другой можно добраться на поезде.

Решение. База индукции. Если на острове Буяне есть всего один го­род, то утверждение задачи, очевидно, выполняется.

Шаг индукции. Предположим, что утверждение задачи выполнено для некоторого п. То есть если имеется п городов, то из любого города в любой другой можно добраться на автомобиле, или из любого города в любой другой можно добраться на поезде.

Пусть теперь имеется п + 1 город. Выкинем из рассмотрения какой-нибудь один из них. По предположению мы знаем, что по оставшимся п городам можно проехать, используя лишь один вид транспорта. Пусть для определенности это автомобиль. Теперь рас­смотрим коммуникации, соединяющие выкинутый нами (п + 1)-й город со всеми остальными. Если все дороги, ведущие из него во все остальные — железные, то мы берем поезд и проезжаем по всей системе из (п +1) города (транзитом через выкинутый нами). Если же есть хоть одна автомобильная дорога, ведущая в выкинутый город, то мы можем смело выбирать автомобиль и кататься по всей стране.

Задача 5. Докажите, что части, на которые п прямых делят плос­кость, всегда можно раскрасить в два цвета так, чтобы соседние части (то есть части, имеющие общий отрезок или луч) были окрашены в разные цвета.

110                      Метод математической индукции

Решение. База индукции. Рассмотрим случай п = 1. Если у нас имеется всего одна прямая, то мы красим одну полуплоскость в один цвет (например, в черный), а другую — в другой (например, в белый).