В команде 35 человек. Может ли быть так, что 13 из них имеют по 13 знакомых (в этой команде), 8 — по 3 знакомых, а 14 — по 10 знакомых?

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

Что нам дано?

• Всего в команде 35 человек.
• 13 человек имеют по 13 знакомых.
• 8 человек имеют по 3 знакомых.
• 14 человек имеют по 10 знакомых.

Что нужно проверить?

Может ли такое распределение знакомств существовать?

Как это проверить?

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

Когда мы считаем количество знакомых у каждого человека, мы фактически считаем, сколько линий выходит из этой точки (это называется «степень вершины»).

Главное правило: Сумма всех «степеней вершин» (то есть сумма всех знакомых у каждого человека) всегда должна быть в два раза больше, чем общее количество «линий» (знакомств). Это потому, что каждое знакомство соединяет двух людей, и мы считаем его дважды: один раз для каждого из них.

Давай посчитаем общую сумму знакомых:

1. 13 человек по 13 знакомых: 13 * 13 = 169
2. 8 человек по 3 знакомых: 8 * 3 = 24
3. 14 человек по 10 знакомых: 14 * 10 = 140

Общая сумма знакомых = 169 + 24 + 140 = 333

Что мы видим?

Сумма знакомых (333) получилась нечетной. Но мы знаем, что общая сумма знакомых всегда должна быть четным числом (ведь это удвоенное количество знакомств).

Вывод:

Так как сумма степеней вершин (333) получилась нечетной, такое распределение знакомств в команде из 35 человек невозможно.

Ответ: Нет, такое распределение знакомств невозможно, потому что сумма всех знакомых получается нечетной (333), а она должна быть четной.