ЕГЭ. Задача 21. Задача о столбах и проводах

От /

Девять столбов соединены между собой проводами так, что от каждого столба
отходит ровно 8 проводов. Сколько всего проводов протянуто между этими 9 столбами?

Задача о столбах и проводах

📘 Теория задачи

Эта задача решается с помощью теории графов. Каждый столб представляет собой вершину графа, а каждый провод — ребро графа.

Ключевая идея: если мы сложим количество проводов, отходящих от каждого столба, то каждый провод посчитаем дважды (он соединяет два столба).

Сумма степеней вершин = 2 × количество рёбер

В теории графов это утверждение известно как лемма о рукопожатиях.

Степень вершины — это количество рёбер, исходящих из неё. В нашей задаче степень каждой вершины равна 8.

🔍 Пошаговое решение

Шаг 1: У нас 9 столбов (вершин), от каждого отходит 8 проводов (степень вершины = 8).
Шаг 2: Вычисляем сумму степеней всех вершин:
9 × 8 = 72
Шаг 3: Применяем лемму о рукопожатиях: сумма степеней = 2E, где E — количество рёбер (проводов).
72 = 2E → E = 36
Шаг 4: Также можно заметить, что это полный граф K₉, так как каждый столб соединён со всеми остальными.

Для полного графа с n вершинами существует формула:

E = n × (n-1) ÷ 2 = 9 × 8 ÷ 2 = 36

🎮 Интерактивная демонстрация

Поэкспериментируйте с разным количеством столбов, чтобы понять принцип:

📊 Текущие значения

Количество столбов (n)
3
Средняя степень вершины
2.0
Сумма степеней Σ deg(v)
6
Количество проводов (E)
3
Проверка формулы: 2E = Σ deg(v)
6 = 6 ✓

Попробуйте построить полный граф для 9 столбов — вы получите ровно 36 проводов!

✅ Итоговый ответ

36 проводов

Каждый из 9 столбов соединён с 8 другими, но при таком подсчёте каждый провод считается дважды, поэтому делим на 2:
9 × 8 ÷ 2 = 36

Прокрутить вверх