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

Утверждение

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

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

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

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

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

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

Независимо от покраски ребёр в графе ${\textstyle 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.

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

Литература

Visvanatha Krishnamurthy. . — Wiley Eastern, 1990-01-01. — 348 с. — ISBN 9788122402728 .

Примечания

1. Евгений Вечтомов. . — Litres, 2018-12-20. — 318 с. — ISBN 9785041182014 .
2. Новиков Федор Александрович. . — Издательский дом "Питер", 2012-09-10. — 400 с. — ISBN 9785496000154 .
3. Ирина Леонидовна Бабинская. . — Наука, 1975. — 120 с.
4. Жуковский М. Е., А.А. Глибичук, А.М. Райгородский, Шкредов И. Д., А.Б. Дайняк, Д.Г. Ильинский, Д.В. Мусатов, А.В. Савватеев от 5 февраля 2018 на Wayback Machine

Ссылки

• Alexander Bogomolny на (требуется Java)