Задача
COM-B1-M09-P024 Шесть человек
Докажите, что среди любых \(6\) человек найдутся либо \(3\) попарно знакомых, либо \(3\) попарно незнакомых.
Выберите одного человека и разделите остальных на знакомых с ним и незнакомых с ним.
Выберем человека \(A\). Среди остальных \(5\) человек по принципу Дирихле есть либо \(3\), знакомые с \(A\), либо \(3\), не знакомые с \(A\). Пусть сначала \(A\) знаком с \(B,C,D\). Если среди \(B,C,D\) есть знакомая пара, например \(B\) и \(C\), то \(A,B,C\) - три попарно знакомых. Если же среди \(B,C,D\) нет знакомых пар, то \(B,C,D\) - три попарно незнакомых. Второй случай, когда есть \(3\) человека, не знакомые с \(A\), аналогичен: если среди них есть незнакомая пара, она вместе с \(A\) дает тройку незнакомых; если нет, то эти трое попарно знакомы.
Сильная задача для книги 1: первый шаг к теории Рамсея.