В летнем лагере в одном из отрядов выяснилось, что трое ребят знакомы ровно с пятью другими, а все остальные имеют в отряде ровно по 2 знакомых. Может ли такое быть?

Задание №5

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

В нашем случае, в отряде есть ребята, знакомые с 5 другими, и ребята, знакомые с 2 другими.

Пусть всего в отряде N человек.

Случай 1: Есть 3 человека, каждый из которых знаком с 5 другими. Их суммарная степень = 3 * 5 = 15.

Остальные (N-3) человека знакомы с 2 другими. Их суммарная степень = (N-3) * 2.

Общая сумма степеней = 15 + (N-3) * 2.

Эта сумма должна быть четной. Но 15 — это нечетное число, а (N-3) * 2 — это всегда четное число (так как умножается на 2). Сумма нечетного и четного числа всегда будет нечетной.

Случай 2: Может быть, 3 человека знакомы друг с другом, и каждый из них еще знаком с 2 другими ребятами? Тогда это значило бы, что каждый из этих троих знаком с 3 другими (2 + 1 = 3). Это противоречит условию, что они знакомы ровно с 5 другими.

Из-за того, что сумма степеней вершин получается нечетной (15 + четное число), такое условие невозможно. Всегда сумма степеней должна быть четной.

Ответ: Нет