|
он прав От n до n(n-1)/2
Ответ: от n до n(n-1)/2
Решение: Заметим, что всего существует n(n-1)/2 различных пар дорог. Поскольку автомобиль добрался до первоначальной вершины, то самый длительный маршрут будет тот, при котором успели закрыться все пары дорог, т.е. n(n-1)/2 минут. Самый быстрый маршрут, очевидно, тот, при котором автомобиль двигался без остановок, т.е. n минут.
Покажем, что такие маршруты существуют. Пусть автомобиль движется по часовой стрелке (возвраты невозможны!) и пронумеруем дороги: 1, 2,…n.
а) Пусть пары дорог открываются в следующем порядке: (1,2), (2,3), (3,4), …, (n-1, n), (n,1). Все это время автомобиль движется без остановок, длительность маршрута n.
б) Пусть сначала открываются всевозможные пары дорог, номера которых со 2-й по (n-1)-ю, все это время автомобиль стоит на месте. Затем будем открывать пары дорог (1,n), (2,n), …, (n-2,n), (1,n-1), все это время он движется без остановок и тормозит перед n-й дорогой. Затем (1,2), (1,3), …, (1,n-2) и все это время он стоит. Наконец открываем последнюю пару дорог (n-1,n) и автомобиль попадает в первоначальную вершину. Поскольку были открыты всевозможные пары дорог, то длительность маршрута n(n-1)/2 минут.
Теперь покажем, что существует маршрут с произвольной длительностью от n до n(n-1)/2. Пусть имеется маршрут длительностью k< n(n-1)/2, тогда из него легко построить маршрут длительностью k+1. Очевидно, что какая-то пара дорог не закрывалась, например (a,b). Достаточно выбрать какую-нибудь вершину X, не смежную ни с a, ни с b, и когда автомобиль будет в этой вершине, закрыть пару дорог (a,b). Остальную последовательность открытия дорог оставить прежней, тогда получим маршрут длительностью k+1.
|
Просмотр сообщений
