Задача
COM-B2-M06-P008 Точное значение \(R(3,3)\)
#8
★★★☆☆ Уровень 3 из 5
Используя верхнюю оценку для \(K_6\) и раскраску \(K_5\), докажите, что \(R(3,3)=6\).
Нужно доказать две части: \(6\) достаточно, а \(5\) недостаточно.
Из задачи о \(K_6\) следует, что при \(6\) вершинах одноцветный треугольник неизбежен, значит, \(R(3,3)\le6\).
С другой стороны, рёбра \(K_5\) можно раскрасить так: стороны пятиугольника красные, диагонали синие. Тогда каждый цвет образует цикл длины \(5\), и одноцветного треугольника нет. Значит, \(R(3,3)>5\).
Итак, \(R(3,3)=6\).
Здесь появляется культура верхней и нижней оценки.