Задача
COM-B2-M06-P014 Десять человек
#14
★★★★☆ Уровень 4 из 5
Докажите, что среди любых \(10\) человек найдутся либо \(3\) попарно знакомых, либо \(4\) попарно незнакомых.
Используйте оценку \(R(3,4)\le R(2,4)+R(3,3)\).
По рекурсии Рамсея имеем
\[R(3,4)\le R(2,4)+R(3,3).\]
Из \(R(2,4)=4\) и \(R(3,3)=6\) получаем \(R(3,4)\le10\). Значит, в любой красно-синей раскраске рёбер \(K_{10}\) есть либо красный \(K_3\), либо синий \(K_4\).
Переведём это на язык людей: красное ребро — знакомство, синее — незнакомство. Получаем либо \(3\) попарно знакомых, либо \(4\) попарно незнакомых.
Не острейшая, но очень важная оценка.