Задача
COM-B2-M06-P016 Двадцать человек
#16
★★★★☆ Уровень 4 из 5
Докажите, что среди любых \(20\) человек найдутся либо \(4\) попарно знакомых, либо \(4\) попарно незнакомых.
Используйте предыдущую оценку \(R(4,4)\le20\).
Покрасим ребро между двумя людьми в красный цвет, если они знакомы, и в синий, если не знакомы. По оценке \(R(4,4)\le20\) в \(K_{20}\) есть либо красный \(K_4\), либо синий \(K_4\).
Красный \(K_4\) означает \(4\) попарно знакомых людей, синий \(K_4\) — \(4\) попарно незнакомых.
Хорошее упражнение на перенос графового результата обратно в язык условия.