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