Номер 30.46, страница 249 - гдз по алгебре 8 класс учебник Мерзляк, Поляков

Глава 5. Основы теории делимости. Параграф 30. Простые и составные числа - номер 30.46, страница 249.

Условие.

30.46. Можно ли объединить 15 компьютеров в сеть так, чтобы каждый был соединен ровно с 7 другими?

Решение.

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

Согласно условию, у нас есть 15 вершин (компьютеров). Каждый компьютер должен быть соединен ровно с 7 другими, что в терминах теории графов означает, что степень каждой вершины (т.е. количество ребер, выходящих из нее) должна быть равна 7.

В теории графов есть фундаментальная теорема, известная как лемма о рукопожатиях. Она гласит, что сумма степеней всех вершин графа всегда равна удвоенному количеству ребер в этом графе. Математически это можно записать в виде формулы:

$\sum \text{deg}(v) = 2|E|$

где $\sum \text{deg}(v)$ — это сумма степеней всех вершин графа, а $|E|$ — это количество ребер.

Поскольку правая часть уравнения ($2|E|$) всегда является четным числом, то и левая часть (сумма степеней всех вершин) также обязана быть четным числом.

Давайте вычислим сумму степеней вершин для нашего случая. У нас 15 вершин, и степень каждой из них равна 7.

Сумма степеней = (количество вершин) $\times$ (степень каждой вершины) = $15 \times 7 = 105$.

Число 105 является нечетным. Это нарушает лемму о рукопожатиях, так как сумма степеней вершин в любом графе должна быть четной. Если бы такая сеть существовала, то общее число соединений (ребер) в ней было бы равно $\frac{105}{2} = 52.5$, что невозможно, так как количество соединений должно быть целым числом.

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

Следовательно, объединить 15 компьютеров в сеть с заданными условиями невозможно.

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