ЯсноПонятно24

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

Предположим, что каждый участник знаком с не менее чем 38 другими участниками. Тогда количество пар участников, которые знакомы друг с другом, не менее чем 38 * 76 / 2 = 1448.

Рассмотрим граф, вершинами которого будут участники семинара, а рёбра будут соответствовать знакомствам между участниками. Так как количество пар участников, которые знакомы друг с другом, не менее чем 1448, то суммарная степень всех вершин графа не менее чем 1448.

Так как у каждой вершины степень не менее чем 38, то суммарная степень всех вершин не меньше чем 38 * 76 = 2888. Но это противоречит тому, что суммарная степень всех вершин не меньше чем 1448. Значит, наше предположение неверно.

Следовательно, существует компания из 4 человек, которую можно посадить за круглый стол так, чтобы каждый сидел рядом со знакомым человеком.