Помогите решить задачу по комбинаторике, пожалуйста.

Если перекрыть лишь два участка кольцевой дороги (далее - К), то все города распадутся не более чем на 2 изолированные части. Кстати, в науке это называется 2 компоненты связности графа. Поэтому рассмотрим лишь случай, когда все три перекрытые дороги суть участки К. Причем сначала предположим, что все три перекрытые дороги являются соседними участками. Тогда будет два изолированных города, бывшие соседними по ребру. Понятно, что необходимо потребовать, чтобы хотя бы из одного их этих городов вела ещё одна дорога. Таким образом, дорога должна идти не менее чем из 50 городов (идем через один по К). То есть не менее 25 новых дорог.
Например, можно соединить их диаметрально (1 с 51, 3 с 53,... 49 с 99). Тогда пусть перекрыты три дороги К. Покажем, что из 25 новых дорог есть хотя бы одна , соединяющая разные компоненты связности графа (образованного лишь К, новые не в счет). Действительно, предположим противное. Тогда города 1 и 51 принадлежат одной компоненте и поэтому ей принадлежат или города с 2 по 50, или с 52 по 100. В любом случае все в полукруге, а, стало быть и диаметральные их пары тоже по предположению, значит вообще все. Противоречие.
Таким образом данная конфигурация удовлетворяет условию: две из трех компонент связности графа, образованного К, соединены новой дорогой, поэтому в графе из всех дорог этих компонент будет не более двух.

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

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

Таким образом, каждый город должен быть соединен с двумя новыми городами. Поскольку у нас есть 100 городов, нам нужно построить 100 новых дорог. Однако каждая дорога соединяет два города, поэтому каждая дорога учитывается дважды. Поэтому нам нужно построить 100 / 2 = 50 новых дорог.

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