3. Задача о знакомых: Докажите, что в любой компании из 6 человек всегда найдутся либо трое попарно знакомых, либо трое попарно незнакомых. (Указание: рассмотрите граф, выберите одну вершину и проанализируйте степени.)

Представим людей вершинами графа, а знакомство — рёбрами.

Выберем любого человека \(A\). Среди остальных пяти человек не менее трёх либо знакомы с \(A\), либо не знакомы с \(A\), поскольку \(5=3+2\).

Пусть сначала \(A\) знаком с тремя людьми \(B,C,D\). Если среди \(B,C,D\) есть знакомая пара, например \(B\) и \(C\), то \(A,B,C\) — трое попарно знакомых. Если же среди \(B,C,D\) нет знакомых пар, то они попарно незнакомы и образуют троих попарно незнакомых людей.

Аналогично, если \(A\) не знаком с тремя людьми \(B,C,D\), то при наличии среди них незнакомой пары вместе с \(A\) получаются трое попарно незнакомых, а если все три попарно знакомы, то они образуют троих попарно знакомых.

Ответ: в любой компании из 6 человек обязательно найдутся либо трое попарно знакомых, либо трое попарно незнакомых.