Теорема о друзьях и незнакомцах

78 из 156 возможных графов друзей-незнакомцев с 6 узлами. Остальные 78 можно получить, поменяв местами красный и синий цвета каждого графика. Для каждого графика красные/синие узлы показывают примерную тройку общих друзей/незнакомцев.

Теорема о друзьях и незнакомцах — математическая теорема из области математики, называемой теорией Рамсея .

Заявление

Предположим, в группе шесть человек. Рассмотрим любые два из них. Возможно, они встречаются впервые — и в этом случае мы будем называть их общими незнакомцами; или они могли встречаться раньше — и в этом случае мы будем называть их общими знакомыми. Теорема гласит:

В любой группе из шести человек как минимум трое из них являются (попарно) общими незнакомцами или общими знакомыми.

Преобразование в настройку теории графов

Доказательство теоремы не требует ничего , кроме трехшаговой логики. Задачу удобно сформулировать на языке теории графов.

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

Теперь возьмите $K_{6}$ . Всего у него 15 ребер. Пусть 6 вершин обозначают 6 человек в нашей группе. Пусть ребра окрашены в красный или синий цвет в зависимости от того, являются ли два человека, представленные вершинами, соединенными ребром, общими незнакомцами или общими знакомыми соответственно. Теперь теорема утверждает:

Независимо от того, как вы раскрасите 15 ребер

K_{6}

с красным и синим вы не сможете избежать либо красного треугольника, то есть треугольника, все три стороны которого красные, представляющего три пары общих незнакомцев, либо синего треугольника, представляющего три пары общих знакомых. Другими словами, какие бы цвета вы ни использовали, всегда будет хотя бы один одноцветный треугольник (то есть треугольник, все ребра которого имеют один и тот же цвет).

Доказательство

Выберите любую одну вершину; назови П. это выходит пять ребер Из P . Каждый из них окрашен в красный или синий цвет. Принцип «ячейки» гласит, что как минимум три из них должны быть одного цвета; ибо если имеется менее трех цветов одного цвета, скажем, красного, то есть по крайней мере три синих.

Пусть A , B , C — другие концы этих трех ребер, все одного цвета, скажем, синего. Если какое-либо из AB , BC , CA синее, то это ребро вместе с двумя ребрами от P до конечных точек ребра образует синий треугольник. Если ни одно из AB , BC , CA не синее, то все три ребра красные и мы имеем красный треугольник, а именно ABC .

Статья Рэмси

Чрезвычайная простота этого аргумента, который приводит к очень интересному выводу, делает эту теорему привлекательной. В 1930 году в статье, озаглавленной «О проблеме формальной логики», Фрэнк П. Рэмси доказал очень общую теорему (теперь известную как теорема Рамсея ), простым случаем которой является эта теорема. Эта теорема Рамсея лежит в основе области, известной как теория Рамсея в комбинаторике .

Границы теоремы

Вывод теоремы не верен, если заменить партию из шести человек партией менее шести человек. Чтобы показать это, мы дадим раскраску К ₅ красным и синим цветом, которая не содержит треугольника со всеми ребрами одного цвета. Рисуем К ₅ в виде пятиугольника , окружающего звезду ( пентаграмму ). Раскрашиваем края пятиугольника в красный цвет, а края звезды в синий.Таким образом, 6 — наименьшее число, для которого можно утверждать заключение теоремы. В теории Рамсея мы записываем этот факт как:

R(3,3:2)=6.

Ссылки

В. Кришнамурти. Культура, волнение и актуальность математики, Wiley Eastern, 1990. ISBN 81-224-0272-0 .

Внешние ссылки

Знакомства на вечеринке в кратчайшие сроки (требуется Java)