Question

В городе 10 перекрёстков, пары перекрёстков соединены не более, чем одной односторонней дорогой. Известно, что, выехав с любого перекрёстка по любой дороге, на него можно будет вернуться, проехав по трём дорогам. Вдоль некоторой дороги (не на перекрёстке) стоит администрация. С любого перекрёстка можно добраться до администрации. При каком наименьшем к обязательно верно, что с любого перекрёстка можно доехать до администрации и вернуться, проехав не более, чем по к дорогам?

Answer 1

Дано:  
10 перекрёстков  
Пары перекрёстков соединены не более, чем одной односторонней дорогой  
Из любого перекрёстка можно вернуться, проехав по трём дорогам  

Найти:  
Наименьшее k, при котором обязательно верно, что с любого перекрёстка можно доехать до администрации и вернуться, проехав не более, чем по k дорогам  

Решение:  
Исследуем минимальный маршрут от каждого перекрёстка до администрации и обратно. Маршрут "туда" не может содержать повторяющихся вершин, и то же самое касается маршрута "обратно". Таким образом, весь маршрут содержит не более 19 дорог.  
Докажем от противного, что минимальный маршрут не может содержать ровно 19 дорог. Предположим, что это так, и в маршруте "обратно" снова есть вершина, которая уже содержится в маршруте "туда". Это приводит к противоречию, следовательно, минимальный маршрут содержит менее 19 дорог.  
Таким образом, минимальное значение k равно 19 - 1 = 18.

Ответ:  
k = 18