Задача Рамсея

Задача Рамсея, задача о знакомствах среди шести человек — это математическая теорема в теории Рамсея, частный случай теоремы Рамсея.

Утверждение

Пусть на вечеринке 6 человек. Если два человека встречались друг с другом до этого хотя бы раз, то они называются знакомыми, если нет — незнакомыми. Согласно задаче Рамсея:

В любой компании из шести человек либо три человека попарно знакомы, либо три человека попарно незнакомы.

Преобразование условия в граф

Доказательство можно провести с помощью графа, записав условие теоремы именно в этом виде.

Граф будет иметь 6 вершин, каждая пара вершин соединена ребром. Такой граф называется полным графом (у него нельзя начертить новые рёбра, так как все возможные соединения уже выполнены). Полный граф с n { extstyle n} вершинами обозначается K n { extstyle K_{n}} .

В данном примере можно построить граф K 6 { extstyle K_{6}} . У такого графа 15 ребер. 6 вершин обозначают 6 человек, упомянутых в условии задачи.

Далее для доказательства необходимо раскрасить рёбра. Ребро будет окрашено красным цветом, если два человека незнакомы, либо синим цветом, если они знакомы. С учётом этих преобразований можно переформулировать утверждение теоремы:

Независимо от покраски ребёр в графе K 6 { extstyle K_{6}} будет либо красный треугольник (треугольник, в котором все ребра красные), либо синий треугольник (в котором все рёбра синие). Красный треугольник будет означать, что 3 человека попарно незнакомы, а синий будет означать, что 3 человека попарно знакомы. Если это утверждение действительно верно, то будет верно и исходное утверждение.

Окончание доказательства

Далее для доказательства выбирается произвольная вершина P. Из вершины выходит пять рёбер. По принципу Дирихле по крайней мере три ребра одного цвета (если ребёр какого-то из цветов меньше 3, ребёр другого цвета больше 3).

A, B, C — вершины, другие концы ребёр, упомянутых выше. Если хотя бы одно из рёбер AC, BC, AB — синее, то можно получить одноцветный треугольник (с помощью двух ребёр из P и упомянутой только что вершины). Если же ни одно из этих ребёр не синее, то все они красные, и из них можно получить красный треугольник ABC, ч. т. д.

Записи Рамсея

В 1930 году в статье «On a Problem in Formal Logic» Рамсей доказал более общую теорему (известную как теорема Рамсея), эта теорема является её частным случаем. На теореме Рамсея основывается теория Рамсея, один из разделов комбинаторики.

Прочие случаи

Если в компании не 6 человек, а только 5, следствие, упомянутое в задаче Рамсея, может не выполняться.

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

В теории Рамсея данный факт записывается так: R ( 3 , 3 : 2 ) = 6. {displaystyle R(3,3:2)=6.}