28

Привет! Давай разбираться с этой задачей. Сначала прочитаем условие и что требуется доказать:

Количество участников научного семинара равно 40. Каждый из присутствующих знаком хотя бы с одним из участников! В конце семинара пройдет ужин, для которого нужно найти хотя бы одну компанию из 4 человек и посадить их круглый стол так, чтобы каждый сидел рядом со знакомым человеком. Докажи, что найти такую компанию возможно.

Доказательство:

Рассмотрим двух любых участников семинара. У каждого из них по 19 знакомых среди оставшихся (если каждый участник знаком хотя бы с одним другим, то максимум может быть 39 знакомых — если он знаком со всеми, кроме себя, но нам нужны только другие, не включая этого рассматриваемого человека). Значит, у них есть, по крайней мере, \(20-20=0\) общих знакомых.

Очевидно, что математика здесь немного подводит. Чтобы утверждать, что у двух человек нет общих знакомых, нужно, чтобы у каждого из них ни один из 19 знакомых не пересекался с 19 знакомыми другого. Но т.к. всего участников 40, и двое из них – это сами рассматриваемые люди, то максимум только 38 возможных знакомых для обоих, значит, у них обязательно есть как минимум один общий знакомый.

Значит, или в формулировке задачи ошибка, или в решении. Подозреваю, что в решении должно быть так: у каждого из них по 19 знакомых, значит у них есть, по крайней мере \(20+20-38=2\) общих знакомых.

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

Задача доказана: можно выбрать четырех человек, которые будут знакомы хотя бы с одним из своих соседей за круглым столом.

Если что-то непонятно или нужно дополнительное объяснение, смело спрашивай!