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

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

Информатика (138 баллов) | 50 просмотров
Дан 1 ответ
0 голосов

Это полный граф с n=5 вершинами, число ребер в нем равно
n*(n-1)/2 = 5*4/2 = 10
формула получается как сумма арифметической прогресии, первую норку можно соединить с 4ю другими
4
вторую уже с 3мя (т.к. с первой она уже соединена):
4+3
третью норку соединяем с 4ой и пятой (с 1 и 2 уже есть тоннели)
4+3+2
и четвертую с пятой
4+3+2+1

по индукции доказывается для n

ответ 10.

(3.8k баллов)