Задача
COM-B2-M06-P015 Оценка для \(R(4,4)\)
#15
★★★★☆ Уровень 4 из 5
Используя \(R(3,4)\le10\), докажите, что \(R(4,4)\le20\).
Примените рекурсию к \(R(4,4)\).
По рекурсии Рамсея
\[R(4,4)\le R(3,4)+R(4,3).\]
По симметрии \(R(4,3)=R(3,4)\). Так как \(R(3,4)\le10\), получаем
\[R(4,4)\le10+10=20.\]
Задача показывает, как из малых оценок строятся более крупные.