Номер 356, страница 72, часть 2 - гдз по математике 5 класс учебник Петерсон, Дорофеев

356 Можно ли 77 телефонов соединить между собой проводами так, чтобы каждый был соединён ровно с пятнадцатью?

Для решения этой задачи представим телефоны в виде вершин графа, а провода, их соединяющие, — в виде его рёбер. По условию, у нас есть 77 телефонов, значит, в графе 77 вершин. Каждый телефон соединён с пятнадцатью другими, что означает, что степень каждой вершины графа равна 15.

Воспользуемся основным свойством теории графов, известным как лемма о рукопожатиях. Она утверждает, что сумма степеней всех вершин любого графа равна удвоенному числу его рёбер. Если обозначить количество вершин как $V$, степень каждой вершины как $k$, а количество рёбер как $E$, то можно записать формулу:

Сумма степеней всех вершин = $V \times k = 2E$.

Подставим в эту формулу значения из нашей задачи:

• Количество вершин (телефонов) $V = 77$.
• Степень каждой вершины (количество соединений) $k = 15$.

Вычислим суммарную степень всех вершин:

$77 \times 15 = 1155$

Таким образом, мы получаем равенство:

$1155 = 2E$

Это равенство показывает, что удвоенное число рёбер (проводов) должно быть равно 1155. Однако число 1155 является нечётным. Величина же $2E$ по определению всегда является чётным числом, поскольку количество рёбер $E$ в графе должно быть целым (не может быть половины провода).

Мы пришли к противоречию: нечётное число (1155) не может быть равно чётному числу ($2E$). Следовательно, граф с такими характеристиками, а значит и такая схема соединения телефонов, невозможен.

Другое следствие из леммы о рукопожатиях гласит, что в любом графе количество вершин с нечётной степенью должно быть чётным. В нашей задаче 77 вершин, и все они имеют нечётную степень (15). Так как число 77 нечётно, это также доказывает, что такое соединение невозможно.

Ответ: нет, нельзя.