Задача №14520

Из десяти стран две подписали договор о дружбе ровно с шестью другими странами, а каждая из оставшихся восьми — ровно с пятью. Сколько всего было подписано договоров?

Эту задачу удобно решить с помощью теории графов. Пусть страны — это вершины графа, а договоры между ними — рёбра.

По условию:
1. У $2$ стран по $6$ договоров (степень вершин равна $6$).
2. У $8$ стран по $5$ договоров (степень вершин равна $5$).

Найдём сумму степеней всех вершин графа $S\text{:}$

Согласно лемме о рукопожатиях, сумма степеней всех вершин графа равна удвоенному количеству его рёбер. Каждый договор соединяет две страны, поэтому в общей сумме он был учтён дважды.

Следовательно, общее количество договоров равно:

Ответ: 26