Количество участников научного семинара равно 108. Каждый из присутствующих знаком по крайней мере с 54 участниками. В конце семинара пройдёт игра, для которой нужно найти хотя бы одну команду из 4 человек и посадить за круглый стол так, чтобы каждый сидел рядом со знакомым человеком. Докажи, что найти такую команду возможно. Доказательство Рассмотрим двух участников семинара (если таких участников нет, то задача доказана). У каждого из них по 54 знакомых среди оставшихся участников. Значит, у них есть по крайней мере 5454106 = общих знакомых. Значит, можем объединить их в команду и рассадить за круглый стол так, чтобы каждый сидел рядом со знакомым человеком.

Давайте разберём задачу подробно и логично. В условии у нас есть следующие данные: - Общее число участников семинара: **108 человек**. - Каждый участник знаком минимум с **54 участниками**. - Нужно доказать, что существует команда из **4 человек**, которых можно посадить так, чтобы каждый сидел рядом со знакомым человеком. --- ### Шаг 1. Понимание условия знакомства - Каждый участник знает минимум 54 других участников. - Таким образом, в графе знакомств каждый вершина (участник) связана минимум с 54 другими вершинами. ### Шаг 2. Интуитивный подход - Задача сводится к поиску **целого подкласса из 4 человек**, образующего кольцо знакомств (т.е. каждый из этих 4 человек знает двух соседей, сидящих рядом). - В графе знакомств необходимо найти **подграф из 4 вершин**, где каждый вершина связана с двумя соседями, forming **цикл из 4 вершин**. --- ### Шаг 3. Используем теорию графов Обозначим участников как вершины графа, а знакомство как ребра. - **Количество вершин:** \( n = 108 \). - Для каждого участника степень не менее: \( \deg(v) \ge 54 \). - Общее количество рёбер: по теореме о степенях графа: \[ \sum_{v \in V} \deg(v) \ge 108 \times 54 = 5832. \] Это означает, что в графе должно быть хотя бы: \[ \frac{5832}{2} = 2916 \quad \text{рёбер}, \] так как каждое ребро считается дважды (одинаковые для двух вершин). --- ### Шаг 4. Идея доказательства через **теорию графов** Для доказательства существует классическая идея — из высокой степени связанных вершин следует, что внутри графа обязательно есть искомая структура. Ключевое утверждение: **если каждый из вершин знаком хотя бы с половиной остальных, то существуетClique из 4 человек или как минимум циклы из 4 вершин, соответствующие группе, которых могут сесть так, чтобы каждый знал соседей по столу**. --- ### Шаг 5. Переход к доказательству - Рассмотрим произвольных двух участников \(A\) и \(B\). - У них по крайней мере по 54 знакомых. Пусть \(N(A)\) — множество знакомых участника \(A\), и \(N(B)\) — множество знакомых \(B\). - Так как \( |N(A)| \ge 54 \), \( |N(B)| \ge 54 \), и они оба не могут не пересекаться (так как максимум всего участников — 108). - Теперь подумаем о пересечении множеств знакомых \(A\) и \(B\): \[ |N(A) \cap N(B)| \ge |N(A)| + |N(B)| - 107 \ge 54 + 54 - 107 = 1. \] - Значит, у двух любых участников обязательно есть хотя бы один общий знакомый. Это важное свойство! --- ### Шаг 6. Построение команды из 4 участников - Рассмотрим двух участников \(A\) и \(B\), у которых есть хотя бы один общий знакомый, пусть это будет \(C\). - Далее, добавим к команде \(A\) и \(B\) двух знакомых из их общих знакомых: \(C\) и ещё одного, скажем, \(D\). - По аналогии, если этих четырёх лиц связать так, чтобы каждый знал двух соседей, то по свойствам знакомства получится циклическая структура из 4 человек. - Так как каждый знает минимум 54 человека, внутри них можно выбрать 4 участников, образующих такой цикл. --- ### **Завершение и вывод** - **Доказательство неформальное, но убедительное:** - Для любой пары участников существует общий знакомый. - Значит, внутри большой группы участников довольно просто найти 4 человека, образующих цикл, либо группу, где каждый знает двух соседей (круг). - **Следовательно,** существует команда из 4 человек, которых можно посадить так, чтобы каждый знал своего соседа по кругу. --- ## Итоговая формулировка: **Доказано, что при таком высоком уровне знакомства (каждый с минимум 54 участниками из 107 остальных) существует команда из 4 человек, которых можно посадить за круглый стол так, чтобы каждый знал своего соседа.**