Question

В подземной волшебной стране количество городов равно 66, причём каждый соединён с каждым подземным ходом. Со временем качество подземных ходов ухудшается и им требуется ремонт. Какое наибольшее число подземных ходов можно закрыть на ремонт так, чтобы по оставшимся ходам можно было из каждого города проехать в каждый?

Answer 1

Дано:
Количество городов: 66.
В начальном состоянии все города соединены между собой подземными ходами.

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

Известно, что для полного графа на 66 вершинах количество рёбер равно C(66, 2) = (66 * 65) / 2 = 2145.

Таким образом, наибольшее число подземных ходов, которые можно закрыть на ремонт, так чтобы оставшиеся ходы позволяли из каждого города проехать в каждый, равно 2145 - 66 = 2079.

Ответ: Можно закрыть на ремонт 2079 подземных ходов.