Question

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

Answer 1

У данного человека среди остальных пяти есть либо не менее трёх знакомых, либо не менее трёх незнакомых ему. Разберём, например, первый случай. Среди этих трёх людей есть либо двое знакомых – тогда они вместе с выбранным нами исходно человеком образуют нужную тройку, либо они все трое попарно незнакомы.

Answer 2

Давайте рассмотрим все возможные комбинации знакомств между пятью человеками: A, B, C, D и E.

1) Если каждый человек знаком с каждым другим, то это означает, что все пять человек попарно знакомы друг с другом. Однако, в этом случае невозможно найти трех попарно незнакомых людей, так как каждый человек знаком со всеми остальными.

2) Если каждый человек незнаком со всеми остальными, то это означает, что никто из них не знаком друг с другом. В этом случае также невозможно найти трех попарно знакомых людей, так как никто из них не знает друг друга.

3) Рассмотрим случай, когда среди пяти человек есть группа из трех попарно знакомых людей (назовем их A, B и C), и два оставшихся человека (назовем их D и E) незнакомы друг с другом. В этом случае группа A, B и C удовлетворяет условию трех попарно знакомых людей, а D и E удовлетворяют условию трех попарно незнакомых людей.

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