В деревне 20 домов, между некоторыми из них проложены тропинки. По тропинкам можно пройти от любого дома к любому другому и притом единственным образом. Сколько всего тропинок проложено в деревне? Ответ обосновать.

В данной задаче мы имеем 20 домов и говорим о том, что между некоторыми из них проложены тропинки, и по этим тропинкам можно пройти от любого дома к любому другому, причем единственным образом. Это описание подходит под определение дерева в теории графов.

В дереве (графе без циклов) количество рёбер (тропинок) всегда на 1 меньше количества вершин (домов). В данном случае домами являются вершины, а тропинки — рёбра.

Так как у нас 20 домов, то количество тропинок можно вычислить следующим образом:

Количество тропинок = Количество домов - 1 = 20 - 1 = 19.

Таким образом, в деревне проложено 19 тропинок.