Мақола ва тезислар номи

ИЗУЧЕНИЕ ТЕОРЕМЫ РАМСЕЯ 
Сапаева С.М. 
Учитель школы №3 г. Ургенча Хорезмской области 
Аннотация:
В этой статье говорится о теореме Рамсея. Хотя в школьный курс 
математики она не введена, но, при решении задач Рамсея не раз обращаемся к теории 
графов. А теория графов изучается в курсе математики спецклассов. Рассмотим, как 
можно проще понять суть теоремы и как применять данную теорему для решения задач. 
Ключевые слова:
теорема Рамсея , теория графов, ребро многоугольника, компания 
из нескольких человек.
Задача. 
Пусть на вечеринке 6 человек. Если два человека встречались друг с другом до этого 
хотя бы раз, то они называются знакомыми, если нет —незнакомыми. Согласно задаче 
Рамсея: 
В любой компании из шести человек либ о три человека попарно знакомы, либо три 
человека попарно незнакомы. 
Доказательство можно провести с помощью графа, записав условие теоремы именно в 
этом виде. 
192 S.S.Buxoriy. Ikki yuz yetmish yetti pir. Buxoro. 2006 y.-B194 
193 https://forum.ziyouz.com/index.php?topic=2526.540;wap 
194 Dala yozuvlari. Buxoro viloyati.Kogon tumani. Xo’ja Yakshaba qishloqg’i.2020-yil, mart-aprel. 

---

663 
Граф будет иметь 6 вершин, каждая пара вершин соединена ребром. Такой граф 
называется полным графом (у него нельзя начертить новые рёбра, так как все возможные 
соединения уже выполнены). {\textstyle K_{n}}
. 
В данном примере можно построить граф 
{\textstyle K_{6}} . У такого графа 15 
ребер. 6 вершин обозначают 6 человек, упомянутых в условии задачи. 
Далее для доказательства необходимо раскрасить рёбра. Ребро будет окрашено 
красным цветом, если два человека незнакомы, либо синим цветом, если они знакомы. С 
учётом этих преобразований можно переформулировать утверждение теоремы: 
Независимо от покраски ребёр в графе {\textstyle K_{6}} 
будет либо красный 
треугольник (треугольник, в котором все ребра красные), либо синий треугольник (в котором 
все рёбра синие). Красный треугольник будет означать, что 3 человека попарно незнакомы, а 
синий будет означать, что 3 человека попарно знакомы. Если это утверждение действительно 
верно, то будет верно и исходное утверждение. 
Для решения этой задачи , мы условие задачи Рамсея преобразовали на граф.
ЗАДАЧА. 
Постройте пример компании из пяти человек, в которой нет трех человек, которые 
попарно знакомы или попарно не знакомы (то есть в любой тройке есть два знакомых и два 
незнакомых человека). 
Решение : 
Для решения этой задачи построим чертеж , здесь точки обозначают людей, красные 
ребра — знакомство, а синий — незнакомство.
Нетрудно убедиться, что в любой тройке будут обязательно две соседние вершины 
(красное ребро) и две несоседние вершины (синее ребро). 
Задачи вроде знакомые и решаются в виде графов . Но относится к теореме Рамсея . 
Очень похожие задачи решаются в программе математики 7 класса ( в спецклассах по 
математике ) .
Теория Рамсея — это раздел комбинаторики. 
Математика предлагает простое объяснение. В 1928 году Фрэнк Пламптон Рамсей, 
английский математик, философ и экономист, доказал, что такие упорядоченные 
конфигурации неизбежно присутствуют в любой большой структуре, это могут быть группа 
звёзд, совокупность случайно разбросанных камешков или последовательность чисел, 
полученных бросанием игральной кости. Когда речь идёт о большом количестве предметов , 
то всегда можно найти группу, которая с очень большой точностью образует какую-нибудь 
заданную конфигурацию: прямую линию, прямоугольник и т.д. Теория Рамсея утверждает, 
что любая структура обязательно содержит упорядоченную подструктуру. Как впервые 
провозгласил около четверти века назад умерший недавно американский математик Теодор 
С. Моцкин, из теории Рамсея следует, что полный беспорядок невозможен. 
В отличие от многих разделов современной математики теорию Рамсея можно 
изложить на интуитивном уровне. В самом деле, привлекательность этой теории отчасти 
обусловлена той простотой, с которой можно сформулировать её задачи. Например, если из 
присутствующих на вечеринке случайным образом выбрать шесть человек (скажем, 

---

664 
Альбины , Карины , Мадины, Марат , Руслан и Наргис ), то верно ли, что либо трое из них 
друг с другом знакомы, либо трое из них незнакомы друг с другом? 
Числа Рамсея чрезвычайно трудно вычислять. Усилиями поколений математиков и 
компьютеров удалось найти лишь семь чисел Рамсея, которые приведены на рис. 2. Чтобы 
наглядно продемонстрировать трудность вычисления чисел Рамсея 
5 < R(3,3) = 6
8 < R(3,4) = 9 
13 < R(3,5) = 14
17 < R(3,6) = 18 
22 < R(3,7) = 23
27 < R(3,8) ≤ 29 
35 < R(3,9) = 36 

---

665 
Числа Рамсея определяются как наименьшее значение n, для которого в любой группе 
из n точек либо некоторая группа из j точек образует полную сеть красных рёбер, либо 
некоторая группа из k точек образует полную сеть синих рёбер. Рисунки показывают, как 
велико должно быть конкретное число Рамсея. На первой диаграмме изображены пять точек, 
соединённые красными и синими рёбрами таким способом, что никакие три точки не 
образуют ни красной, ни синей полной сети. Следовательно, из первой диаграммы можно 
вывести, что число Рамсея для трёх красных и трёх синих больше пяти. Аналогично можно 
утверждать, что из второй диаграммы следует, что число Рамсея для трёх красных и четырёх 
синих больше восьми. Другими более сложными методами можно показать, что число 
Рамсея для трёх красных и трёх синих равно шести, а число Рамсея для трёх красных и 
четырёх синих равно девяти . 
Задача . 
Пусть есть компания из шести человек. Докажите, что в этой компании обязательно 
найдутся три человека, которые будут попарно знакомы друг с другом, либо которые будут 
попарно незнакомы друг с другом. 
Решение : 
Обозначим людей в этой компании через 1,2,3,4,5,6 и рассмотрим 1 человека. Помимо 
него есть ещё 5 человек, значит, что 1 будет либо знаком по крайней мере с тремя, либо 
незнаком по крайней мере с тремя. Для определенности будем считать, что он знаком с 2, 3, 
4. Тогда если 2 и 3 будут знакомы, то мы нашли тройку попарно знакомых людей (1−2−3), 
поэтому будем считать, что они не знакомы. Аналогично можно сказать про пары (3−4) и 
(4−2) — они должны быть не знакомыми. Отсюда получаем, что у нас нашлась тройка 
(2−3−4), в которой все попарно незнакомы. Доказано. 
Теорема Рамсея в прогрессии.
Арифметическая прогрессия — это последовательность чисел, в которой разность 
между соседними членами остается постоянной. Например, 8, 10, 12, 14 — это 
арифметическая прогрессия, в которой разность между соседними членами равна двум. Из 
теории Рамсея следует такое утверждение об арифметических прогрессиях: если каждое 
число от 1 до 9 покрасить в красный или синий цвет, то либо три синих числа, либо три 
красных образуют арифметическую прогрессию. 
Чтобы доказать это утверждение, мы могли бы проверить все 512 способов раскраски 
девяти чисел. Но мы можем доказать его, рассмотрев только два случая. Начнем со случая, в 
котором 4 и 6 имеют одинаковый цвет, скажем синий. 
Чтобы избежать синей арифметической прогрессии 4, 5, 6. мы покрасим 5 в красный 
цвет. 
Чтобы избежать синих арифметических прогрессий 2,4,6 и 4,6,8, мы покрасим 2 и 8 в 
красный цвет. 
Но тогда у нас получится красная арифметическая прогрессия 2,5, 8. Итак, если 4 и 6 
имеют одинаковый цвет, то всегда получится либо красная, либо синяя арифметическая 

---

666 
прогрессия. Теперь рассмотрим случай, когда 4 и 6 имеют различный цвет. Число 5 можно 
покрасить как угодно, не создав при этом арифметической прогрессии, так что мы 
произвольно покрасим 5 в красный цвет. 
Продолжим раскрашивание следующим образом: 
Такое раскрашивание дает последовательность 
Но в ней все равно осталась красная арифметическая прогрессия 1,5,9. Таким образом, 
независимо от того, в одинаковый или в разные цвета окрашены 4 и 6, всегда имеется либо 
синяя, либо красная арифметическая прогрессия. 
Теорема Рамсея хотя не изучается в школьном курсе математики , но для 
интересующихся школьников будет весьма увлекательной. Если рассмотреть игру крестики 
и нолики , ещё интересней.