Покрасьте каждую из линий, соединяющих шесть точек, в красный или синий. Где-то в результате найдётся треугольник, все три стороны которого одного цвета, и шесть — наименьшее число точек, при котором это гарантировано. Доказательство — рассуждение о вечеринке: выберите человека, у которого пять связей, и по принципу Дирихле не меньше трёх из них одного рода; если двое из этих троих знакомы между собой, ваш треугольник готов, а если не знаком никто, эти трое незнакомы друг другу, и готов другой. Шесть человек дают 6 × 5/2 = 15 пар (вторая ссылка), так что машина может справиться полным перебором в 2^15 = 32 768 случаях (первая ссылка) — достаточно мало, чтобы ни у кого не было оправдания этого не делать, а точность границы проверяют на пятицикле: красный пятиугольник с синей звездой внутри, который на пяти точках избегает обоих треугольников.
Следующее диагональное число, R(4,4) = 18, стоит 2^153 раскрасок: у восемнадцати точек 18 × 17/2 = 153 пары между собой (третья ссылка), а 2^153 — это 1.1417981541648⋅10+46 (четвёртая), не то число, о котором спорят пересчётом. Гринвуд и Глисон в 1955 году получили 18 смесью оценок и проверенных вручную случаев; R(5,5), тот же вопрос на следующем шаге, с тех пор открыт — известно лишь, что он лежит в узкой полосе, которая за семьдесят лет немного сдвинулась. Собственная теорема Рамсея 1930 года была о логической машинерии под всем этим, и доказали её потому, что она понадобилась для вопроса философии математики: уверенность, что всякая достаточно большая структура содержит крупный упорядоченный кусок самой себя.
Ответ
32768
Как его читать
2^15 в поле вычислений: каждая двухцветная раскраска пятнадцати пар из шести человек. Вторая ссылка — сами пятнадцать пар.
Источник
Frank P. Ramsey, 'On a Problem of Formal Logic', 1930; R(3,3) = 6 is the party theorem, R(4,4) = 18 was proved by Greenwood and Gleason in 1955, and R(5,5) is still unknown
Пересчитать в калькуляторе
Эти ссылки открывают подходящий калькулятор с уже введёнными числами этой задачи. Строка выше — то, что должен показать экран; проверьте сами.