新規更新March 11, 2019 at 03:38AM
【外部リンク】
Задача Рамсея
ParticipantOfTheEncyclopedia:
[[Файл:Friends_strangers_graph.gif|справа|обрамить| Все 78Возможные [[Граф (математика)|графы]], показывающие друзей и незнакомцев в компании из 6 человек. ]]
'''Задача Рамсея'''<ref></ref><ref></ref><ref></ref> — это [[Теорема|математическая теорема]] в [[Теория Рамсея|теории Рамсея]].
== Утверждение ==
Пусть на вечеринке 6 человек. Если два человека встречались друг с другом до этого хотя бы раз, то они называются ''знакомыми,'' если нет — ''незнакомыми.'' Согласно задаче Рамсея:
: В любой компании из шести человек либо три человека попарно знакомы, либо три человека попарно незнакомы.
== Преобразование условия в граф ==
[[Математическое доказательство|Доказательство]] можно провести с помощью графа, записав условие теоремы именно в этом виде.
[[Граф (математика)|Граф]] будет иметь 6 [[Вершина (теория графов)|вершин]], каждая пара вершин соединена [[Ребро (теория графов)|ребром]]. Такой граф называется [[Полный граф|полным графом]] (у него нельзя начертить новые рёбра, так как все возможные соединения уже выполнены). Полный граф с <math display="inline">n</math>вершинами обозначается <math display="inline">K_n</math>.
В данном примере можно построить граф <math display="inline">K_6</math>. У такого графа 15 ребер. 6 вершин обозначают 6 человек, упомянутых в условии задачи.
Далее для доказательства необходимо раскрасить рёбра. Ребро будет окрашено красным цветом, если два человека незнакомы, либо синим цветом, если они знакомы. С учётом этих преобразований можно переформулировать утверждение теоремы:
: Независимо от покраски ребёр в графе <math display="inline">K_6</math>будет либо красный треугольник (треугольник, в котором все ребра красные), либо синий треугольник (в котором все рёбра синие). Красный треугольник будет означать, что 3 человека попарно незнакомы, а синий будет означать, что 3 человека попарно знакомы. Если это утверждение действительно верно, то будет верно и исходные утверждение.
== Окончание доказательства ==
Далее для доказательства выбирается произвольная вершина ''P.'' Из вершины выходит пять рёбер. По [[Принцип Дирихле (комбинаторика)|принципу Дирихле]] по крайней мере три ребра одного цвета (если ребёр какого-то из цветов меньше 3, ребёр другого цвета больше 3).
''A'', ''B'', ''C'' — вершины, другие концы ребёр, упомянутых выше. Если хотя бы одно из рёбер ''AC, BC, CA —'' синее, то можно получить одноцветный треугольник (с помощью двух ребёр из P и упомянутой только что вершины). Если же ни одно из этих ребёр не синее, то все они красные, и из них можно получить красный треугольник ''ABC.''
== Записи Рамсея ==
Теорему делает привлекательной сравнительная простота формулировки. В 1930 году в статье «On a Problem in Formal Logic» [[Рамсей, Фрэнк Пламптон|Рамсей]] доказал более общую теорему (известную как [[Теорема Рамсея|теорема Рамсея]]), эта теорема является её частным случаем. На теореме Рамсея основывается [[Теория Рамсея|теория Рамсея]], один из разделов [[Комбинаторика|комбинаторики]].
== Прочие случаи ==
[[Файл:RamseyTheory_K5_no_mono_K3.svg|обрамить| Контрпример для графа с пятью вершинами ]]
Если в компании не 6 человек, а только 5, следствие, упомянутое в задаче Рамсея, может не выполняться.
Чтобы показать возможность такого случая, необходимо построить [[контрпример]]. Контрпример — [[пятиугольник]], окружающий [[Пятиконечная звезда|пятиконечную звезду]]. Пятиугольник необходимо окрасить в красный цвет, а звезду — в синий. Таким образом, минимальное количество вершин, для которого выполняется свойство, указанное в задаче — 6.
В теории Рамсея данный факт записывается так: <math>R(3,3: 2) = 6.</math>
:<math xmlns="https://ift.tt/M2cV0i"> </math><span></span>
== Примечания ==
* В. Кришнамурти. Культура, волнение и актуальность математики, Wiley Eastern, 1990.
<references />
== Ссылки ==
* [https://ift.tt/2cB27r0 Знакомства с точки зрения математики] на [https://ift.tt/2cB27r0 cut-the-knot] (требуется Java)
[[Категория:Теоремы дискретной математики]]
[[Категория:Теория Рамсея]]
[[Категория:Страницы с непроверенными переводами]]
https://ift.tt/2XOskIR
