Из десяти стран семь подписали договор о дружбе ровно с пятью другими странами, а каждая из оставшихся трёх — ровно с семью. Сколько всего было подписано договоров?
Для решения задачи воспользуемся теорией графов. Представим каждую страну в виде вершины графа, а каждый договор между двумя странами — в виде ребра, соединяющего соответствующие вершины.
Согласно лемме о рукопожатиях, сумма степеней всех вершин графа равна удвоенному количеству его рёбер. Степень вершины в данном случае — это количество договоров, подписанных конкретной страной.
1. Найдём сумму степеней всех 10 вершин:
7⋅5+3⋅7=35+21=562. Так как каждый договор соединяет две страны, каждое ребро графа учитывается в этой сумме дважды. Чтобы найти общее количество договоров (рёбер), разделим полученную сумму на 2:
256=28Таким образом, всего было подписано 28 договоров.
Ответ: 28
Проверить решение?
Покажи своё решение — проверю и покажу, где ошибка
Потренируйся на похожих — ИИ проверит твои решения
1
Задачи повышенной сложности
ФИПИ