Теория Рамсея Научно - исследовательская работа Приходько Елены

Цель: изучение теории Рамсея и применение знаний для решения задач. Задачи: изучить и исследовать теорию Рамсея; построить модель теории Рамсея; применить теорию Рамсея при решении задач.

Талантливый математик Фрэнк Пламптон Рамсей доказал, что полная неупорядоченность невозможна. Каждое достаточно большое множество чисел, точек или объектов обязательно содержит высоко упорядоченную структуру

Модели теории Рамсея

R(3, 3) = 6.

Число Рамсея R(k, m) это наименьшее число n такое, что в любом полном графе с n вершинами, ребра которого раскрашены в красный и синий цвета, найдется либо подграф с k вершинами, все ребра которого окрашены в красный цвет, либо подграф с m вершинами, все ребра которого окрашены в синий цвет. R(k, m) = n

Теория Рамсея в арифметической прогрессии Начнём со случая, в котором 4 и 6 имеют одинаковый цвет, скажем синий Чтобы избежать синей арифметической прогрессии 4, 5, 6, мы покрасим 5 в красный цвет Чтобы избежать синих арифметических прогрессий 2, 4, 6 и 4, 6, 8, мы покрасим 2 и 8 в красный цвет Но тогда у нас получится красная арифметическая прогрессия 2, 5, 8.

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

Задача. В математическом кружке участвуют 100 школьников. Известно, что среди любых четырёх участников кружка найдется по меньшей мере один, знакомый с остальными тремя. Докажите, что найдется участник, знакомый со всеми 99 остальными участниками. Каково минимальное число школьников, знакомых со всеми остальными 99 участниками?

РЕШЕНИЕ: Изобразим школьников в виде точек А, В, С, Д, Е. Соединим точки синим отрезком если школьники знакомы, а красным – незнакомы.

5 < R(3,3) = 6

8 < R(3,4) = 9

13 < R(3,5) = 14

17 < R(4,4) = 18

17 < R(3,6) = 18

22 < R(3,7) = 23

27 < R(3,8) 29

35 < R(3,9) = 36

СПАСИБО ЗА ВНИМАНИЕ!