Question

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

Answer 1

Ответ:

.

Объяснение:

0

Перенумеруем все города. Для городов i, j направим дорогу из города с меньшим номером в город с большим номером. Тогда при проезде по дорогам мы всегда приезжаем в города с большими номерами, и обратно не возвращаемся.

Из города 1 можно добраться до всех, а из n нельзя выехать. Единственный путь, проходящий все города -- это 1-2-...-n.

Теперь надо показать, что такая конструкция всего одна с точностью до перенумерации городов. Из этого будет следовать, что способов её осуществить ровно n!.

Для начала можно доказать, что имеется город, из которого нельзя выехать. В противном случае мы можем бесконечно долго путешествовать, и какие-то посещаемые города при этом повторятся. Это значит, что основное условие нарушается. Городу с таким свойством присвоим значение n. Он всего один, так как из остальных городов идут стрелки в n.

Далее применяем индукцию, отбрасывая город n и стрелки в него. Для оставшихся городов формируется (по предположению) единственная нумерация 1,2,...,n-1 такая, что из i в j идёт стрелка <=> i < j. Поскольку n больше всех остальных чисел, после возвращения n-го города на место всё сохранится.

Можно и без индукции. Для каждого города рассмотрим путь максимальной длины по стрелкам, оканчивающийся в данном городе. Длину такого пути ему и сопоставим. Значения могут приниматься от 0 до n-1. При этом они не повторяются: если для двух городов значения равны k, то из одного из них попадаем по ребру в другой, что увеличивает длину до k+1. Таким образом, все значения используются ровно по разу. Увеличивая их на 1, имеем описанную выше нумерацию. Ясно также, что ребро всегда идёт из i в j только при i < j.

Answer 2

Для решения данной задачи можно использовать понятие графов. Представим каждый город в виде вершины, а каждую дорогу — в виде ребра. Таким образом, мы получим граф, в котором каждая вершина соединена одним или несколькими ребрами с другими вершинами.

Для того чтобы президент мог объехать все дороги, необходимо, чтобы граф был связным и каждая вершина имела четную степень (количество ребер, исходящих из нее). Это обусловлено тем, что при прохождении каждой дороги, входящей в вершину, число исходящих из нее дорог должно быть четным, чтобы можно было покинуть вершину через другую дорогу.

В данном случае, так как в стране всего 5 городов, есть всего несколько вариантов графов, удовлетворяющих указанным условиям: 1. Цикл длиной 5 с каждой вершиной имеет степень 2. В этом случае есть 4 возможные ориентации дорог, итого 4 способа.

2. Цикл длиной 3 и две изолированные вершины. В этом случае есть 2 возможные ориентации дорог, итого 2 способа.

Итого, всего существует 6 способов ввести одностороннее движение на дорогах так, чтобы президент мог объехать все дороги, проехав каждую ровно один раз.