Задача Рамсея
Задача Рамсея[1][2][3], задача о знакомствах среди шести человек[4] — это математическая теорема в теории Рамсея, частный случай теоремы Рамсея.
Утверждение
Пусть на вечеринке 6 человек. Если два человека встречались друг с другом до этого хотя бы раз, то они называются знакомыми, если нет — незнакомыми. Согласно задаче Рамсея:
В любой компании из шести человек либо три человека попарно знакомы, либо три человека попарно незнакомы.
Преобразование условия в граф
Доказательство можно провести с помощью графа, записав условие теоремы именно в этом виде.
Граф будет иметь 6 вершин, каждая пара вершин соединена ребром. Такой граф называется полным графом (у него нельзя начертить новые рёбра, так как все возможные соединения уже выполнены). Полный граф с [math]\displaystyle{ n }[/math] вершинами обозначается [math]\displaystyle{ K_n }[/math].
В данном примере можно построить граф [math]\displaystyle{ K_6 }[/math]. У такого графа 15 ребер. 6 вершин обозначают 6 человек, упомянутых в условии задачи.
Далее для доказательства необходимо раскрасить рёбра. Ребро будет окрашено красным цветом, если два человека незнакомы, либо синим цветом, если они знакомы. С учётом этих преобразований можно переформулировать утверждение теоремы:
- Независимо от покраски ребёр в графе [math]\displaystyle{ K_6 }[/math]будет либо красный треугольник (треугольник, в котором все ребра красные), либо синий треугольник (в котором все рёбра синие). Красный треугольник будет означать, что 3 человека попарно незнакомы, а синий будет означать, что 3 человека попарно знакомы. Если это утверждение действительно верно, то будет верно и исходное утверждение.
Окончание доказательства
Далее для доказательства выбирается произвольная вершина P. Из вершины выходит пять рёбер. По принципу Дирихле по крайней мере три ребра одного цвета (если ребёр какого-то из цветов меньше 3, ребёр другого цвета больше 3).
A, B, C — вершины, другие концы ребёр, упомянутых выше. Если хотя бы одно из рёбер AC, BC, AB — синее, то можно получить одноцветный треугольник (с помощью двух ребёр из P и упомянутой только что вершины). Если же ни одно из этих ребёр не синее, то все они красные, и из них можно получить красный треугольник ABC, ч. т. д.
Записи Рамсея
В 1930 году в статье «On a Problem in Formal Logic» Рамсей доказал более общую теорему (известную как теорема Рамсея), эта теорема является её частным случаем. На теореме Рамсея основывается теория Рамсея, один из разделов комбинаторики.
Прочие случаи
Если в компании не 6 человек, а только 5, следствие, упомянутое в задаче Рамсея, может не выполняться.
Чтобы показать возможность такого случая, необходимо построить контрпример. Контрпример — пятиугольник, окружающий пятиконечную звезду. Пятиугольник необходимо окрасить в красный цвет, а звезду — в синий. Таким образом, минимальное количество вершин, для которого выполняется свойство, указанное в задаче — 6.
В теории Рамсея данный факт записывается так: [math]\displaystyle{ R(3,3: 2) = 6. }[/math]
Литература
Visvanatha Krishnamurthy. Culture, excitement, and relevance of mathematics. — Wiley Eastern, 1990-01-01. — 348 с. — ISBN 9788122402728.
Примечания
- ↑ Евгений Вечтомов. Философия математики 2-е изд. Учебное пособие для бакалавриата и магистратуры. — Litres, 2018-12-20. — 318 с. — ISBN 9785041182014.
- ↑ Новиков Федор Александрович. Дискретная математика: Учебник для вузов. 2-е изд. Стандарт третьего поколения. — Издательский дом "Питер", 2012-09-10. — 400 с. — ISBN 9785496000154.
- ↑ Ирина Леонидовна Бабинская. Задачи математических олимпиад. — Наука, 1975. — 120 с.
- ↑ Жуковский М. Е., А.А. Глибичук, А.М. Райгородский, Шкредов И. Д., А.Б. Дайняк, Д.Г. Ильинский, Д.В. Мусатов, А.В. Савватеев http://ru.discrete-mathematics.org/fall2017/magistracy_online_program.pdf Архивная копия от 5 февраля 2018 на Wayback Machine
Ссылки
- Alexander Bogomolny Знакомства с точки зрения математики на cut-the-knot (требуется Java)