Среди шести незнакомцев всегда есть треугольник: 2^15 случаев на проверку

R(3,3) = 6, пятнадцать пар дают 32 768 раскрасок, и каждая из них прячет треугольник.

Статистика и данные · Уровень: Классический результат · Обновлено 2026-11-10

Покрасьте каждую из линий, соединяющих шесть точек, в красный или синий. Где-то в результате найдётся треугольник, все три стороны которого одного цвета, и шесть — наименьшее число точек, при котором это гарантировано. Доказательство — рассуждение о вечеринке: выберите человека, у которого пять связей, и по принципу Дирихле не меньше трёх из них одного рода; если двое из этих троих знакомы между собой, ваш треугольник готов, а если не знаком никто, эти трое незнакомы друг другу, и готов другой. Шесть человек дают 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

Пересчитать в калькуляторе

Эти ссылки открывают подходящий калькулятор с уже введёнными числами этой задачи. Строка выше — то, что должен показать экран; проверьте сами.

Это независимый сторонний информационный сайт. Он не связан с Casio, Texas Instruments или их дистрибьюторами, не спонсируется ими и не имеет их авторизации. Названия моделей и продуктов — товарные знаки соответствующих правообладателей; они приведены здесь только для идентификации устройств.

Последовательности нажатий клавиш в этих справочниках составлены на основе собственных данных о раскладке этого сайта — тех же данных, которые отображает онлайн-калькулятор, — а также общедоступных сведений о продуктах. Характеристики и региональные конфигурации проверяются на реальном устройстве и по последним материалам производителя.