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

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

• из любой деревни можно добраться до любой другой (сеть связна);

• при этом нигде нет «обходных путей» (нет циклов), потому что если бы был цикл, то между некоторыми двумя деревнями существовало бы как минимум два разных маршрута.

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

Известное свойство дерева: если в дереве N вершин, то рёбер (дорог) ровно N − 1.

Почему так:

• Начнём с одной деревни: дорог 0.

• Чтобы добавить ещё одну деревню так, чтобы она была связана с уже имеющимися и при этом не возникло второго маршрута (цикла), её можно присоединить ровно одной новой дорогой.

• Каждый раз при добавлении деревни прибавляется 1 дорога.

• Значит, при переходе от 1 деревни к 214 деревням добавится $214 - 1$ дорог.

Считаем:

Ответ: 213 дорог.