В маленькой деревне всего 15 домов. Может ли быть так, что у каждого дома 1, 3 или 7 соседей?

Решение:

Рассмотрим задачу с точки зрения графа, где дома — это вершины, а соседство — рёбра.

Пусть \( n = 15 \) — количество домов (вершин).

Степень вершины — это количество соседей у дома.

Случай 1: Каждый дом имеет 1 соседа.

Сумма степеней всех вершин равна удвоенному числу рёбер (теорема о рукопожатиях): \( \sum deg(v) = 2|E| \).

Если каждый дом имеет 1 соседа, то сумма степеней равна \( 15 \cdot 1 = 15 \).

\( 15 = 2|E| \). Число \( |E| \) должно быть целым, но \( 15 \) не делится на \( 2 \). Следовательно, такой случай невозможен.

Случай 2: Каждый дом имеет 3 соседей.

Сумма степеней равна \( 15 \cdot 3 = 45 \).

\( 45 = 2|E| \). Число \( 45 \) не делится на \( 2 \). Следовательно, такой случай невозможен.

Случай 3: Каждый дом имеет 7 соседей.

Сумма степеней равна \( 15 \cdot 7 = 105 \).

\( 105 = 2|E| \). Число \( 105 \) не делится на \( 2 \). Следовательно, такой случай невозможен.

Общее правило: Сумма степеней вершин в любом графе всегда чётна. В данном случае, если каждый из \( 15 \) домов имеет \( k \) соседей, то сумма степеней равна \( 15k \).

• Если \( k = 1 \), то \( 15 \cdot 1 = 15 \) (нечётное).
• Если \( k = 3 \), то \( 15 \cdot 3 = 45 \) (нечётное).
• Если \( k = 7 \), то \( 15 \cdot 7 = 105 \) (нечётное).

Поскольку во всех предложенных случаях сумма степеней получается нечётной, такой сценарий невозможен.

Ответ: нет.