Дано: в стране Ориентация на всех дорогах введено одностороннее движение, из любого города в любой другой можно добраться, проехав не более чем по двум дорогам. Одну дорогу закрыли на ремонт так, что из каждого города по-прежнему можно добраться до каждого.
Найти: доказать, что для любых двух городов это можно сделать, проехав не более, чем по трем дорогам.
Решение:
Если из каждого города до каждого другого можно добраться, проехав не более чем по двум дорогам, то закрытие одной дороги не изменит этого факта. В этом случае можно прокладывать путь через другие города, чтобы добраться от одного города до другого.
Таким образом, даже после закрытия одной дороги из каждого города до каждого другого можно добраться, проехав не более чем по трем дорогам.
Ответ:
Для любых двух городов это можно сделать, проехав не более, чем по трем дорогам.