Задача
В одном государстве 100 городов и каждый соединён с каждым дорогой с односторонним движением. Докажите, что можно поменять направление движения не более чем на одной дороге так, чтобы от каждого города можно было доехать до любого другого.
Решение
Докажем по индукции, что утверждение верно для любого числа n городов, большего 2.
База – для трёх городов – очевидна.
Шаг индукции. Удалим город A, имеющий и входящие и выходящие дороги (такой найдётся, так как городов, из которых дороги только выходят, не больше одного; аналогично для городов, в которые дороги только входят). По предположению индукции в оставшемся графе можно добиться требуемого, поменяв направление не более чем одной дороги. Присоединение города A и соответствующих дорог сохраняет это свойство.
Ответ
Ответ задачи отсутствует
Чтобы оставлять комментарии, войдите или зарегистрируйтесь