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

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

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

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

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

5 R(3, 3) = 6.

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

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

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

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

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

11 5 < R(3,3) = 6

12 8 < R(3,4) = 9

13 13 < R(3,5) = 14

14 17 < R(4,4) = 18

15 17 < R(3,6) = 18

16 22 < R(3,7) = 23

17 27 < R(3,8) 29

18 35 < R(3,9) = 36

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