Заполни пропуски в доказательстве задачи. сы Количество участников научного семинара равно 86. Каждый из присутствующих знаком по крайней мере с 43 участниками. В конце семинара…
Заполни пропуски в доказательстве задачи. сы Количество участников научного семинара равно 86. Каждый из присутствующих знаком по крайней мере с 43 участниками. В конце семинара пройдёт игра, для которой нужно найти хотя бы одну команду из 4 человек и посадить за круглый стол так, чтобы каждый сидел рядом со знакомым человеком. Докажи, что найти такую команду возможно. Доказательство У каждого из них по 43 знакомых среди оставшихся Значит, у них есть по крайней мере Рассмотрим двух знакомыхучастников семинара (если таких участников нет, то задача доказана). участников. 43 + 43 84 общих знакомых, ия Значит, можем объединить их в команду и рассадить за круглый стол так, чтобы каждый сидел рядом со знакомым человеком.
Для решения этой задачи мы будем использовать принципы теории графов и комбинаторики.
Доказательство
Условия задачи: У нас есть 86 участников семинара, каждый из которых знаком как минимум с 43 другими участниками. Это означает, что каждый участник может быть представлен как вершина в графе, где знакомство между участниками является ребром.
Обозначения: Пусть граф \( G \) содержит 86 вершин (участников). Поскольку каждый из них знаком с минимум 43 другими, то степень каждой вершины (число рёбер, исходящих из вершины) не менее 43.
Соседние участники: Рассмотрим произвольного участника \( A \). У него есть 43 знакомых участника; обозначим их как \( B_1, B_2, \ldots, B_{43} \).
Формирование команд: Выберем любой участник \( B_1 \) из знакомых \( A \) и рассмотрим его знакомых. Участник \( B_1 \) также знаком как минимум с 43 другими участниками. Поскольку \( A \) и \( B_1 \) знакомы, между ними есть рёбра в нашем графе.
Количество общих знакомых: Теперь рассмотрим общее количество знакомых у участников \( A \) и \( B_1 \):
- Поскольку \( A \) знаком с \( B_1 \) и на других 42 участниками \( B_1 \) полуучает минимум 43 интересующих их, у нас может быть максимум 84 разных участников (так как их общее количество 86 и \( A \) и \( B_1 \) могут иметь общих знакомых).
- Как минимум один участник, знакомый и с \( A \), и с \( B_1 \), должен существовать. Это связано с тем, что если бы у них не было общих знакомых, тогда у них могли бы быть разные 43 знакомых, что нарушило бы принцип о том, что среди всех 86 участников.
Выбор команды из 4 человек: Таким образом, у нас есть не менее 3 участников (например, \( A, B_1, C \)), которые знакомы между собой. Теперь можно выбрать еще одного участника, \( D \), который знает хотя бы одну из этих троих, и мы получаем команду из 4 человек: \( A, B_1, C, D \).
Заключение
Мы доказали, что всегда можно составить команду из 4 человек, сидящих за круглым столом так, что каждый из них знаком с соседями. Это означает, что задача выполняется. Таким образом, мы можем констатировать, что найти такую команду действительно возможно.
