Задача
В некоторой стране каждый город соединён с каждым дорогой с односторонним движением.
Докажите, что найдётся город, из которого можно добраться в любой другой.
Решение
Индукция по числу городов. База очевидна.
Шаг индукции. Удалим один из городов. В силу предположения индукции есть город А с требуемым свойством. Вспомним теперь про удалённый город. Если в него ведёт хотя бы одна дорога, то город А – искомый. В противном случае сам удалённый город удовлетворяет требуемому свойству.
Ответ
Ответ задачи отсутствует
Чтобы оставлять комментарии, войдите или зарегистрируйтесь
Комментариев нет