Question

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

Answer 1

1)600:2=300
2)300:3=150

Answer 2

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

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

Рассмотрим город A и город B. Чтобы существовали два различных маршрута из A в B через промежуточный город C, мы можем представить это следующим образом:

1. A -> C -> B
2. A -> B

Теперь рассмотрим другую пару городов A и D:

1. A -> C -> D
2. A -> D

Мы можем заметить, что промежуточный город C обслуживает все пары городов. Таким образом, нам нужно соединить каждую пару городов исходной страны новой дорогой и добавить один промежуточный город, чтобы удовлетворить условия задачи.

Количество новых дорог, которые нам нужно построить, будет равно количеству комбинаций из 600 городов по 2, плюс дополнительная дорога от промежуточного города ко всем остальным городам:

Количество дорог = C(600, 2) + 600 = 600! / (2! * (600 - 2)!) + 600 = 179,700 + 600 = 180,300

Таким образом, наименьшее количество дорог, которое может быть построено, равно 180,300.