Question

В некотором государстве 10 городов и 21 автодорога, каждая из которых связывает какие-то два города. Между городами устанавливается железнодорожное сообщение, исходя из принципа экономии: железная дорога между двумя городами прокладывается тогда и только тогда, когда автомобильная дорога между этими городами отсутствует. Сколько железных дорог будет построено?

Answer 1

Из каждого города должно выходить 9 дорог. Всего из 10 городов должно выходить 9·10 = 90 дорог. Но здесь каждая дорога посчитана дважды. Значит всего должно быть 90:2 = 45 дорог.

Так как автомобильных дорог 21, то железных дорог будет построено 45-21 = 24.

Answer 2

Давайте рассмотрим ситуацию с городами и автодорогами. У нас есть 10 городов и 21 автодорога, каждая из которых связывает какие-то два города.

Из условия задачи следует, что если между городами есть автомобильная дорога, то между этими же городами не будет железнодорожного сообщения.

Обратим внимание на число городов и число автодорог. Поскольку в некотором государстве 10 городов и 21 автодорога, то максимальное количество железных дорог, которые могут быть построены, равно количеству возможных сочетаний из 10 городов по 2:

C(10, 2) = 10! / (2! * (10 - 2)!) = 10! / (2! * 8!) = 10 * 9 / 2 = 45.

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