Теорія Ремзі — розділ математики, який вивчає умови, за яких у довільно сформованих математичних об'єктах зобов'язаний з'явитися певний порядок. Названа на честь Френка Ремзі.
Завдання теорії Ремзі зазвичай звучать у формі питання «скільки елементів має бути в деякому об'єкті, щоб гарантовано виконувалося задана умова чи існувала задана структура?». Найпростіший приклад:
- Довести, що в будь-якій групі з 6 осіб, знайдуться троє людей, знайомих одне з одним, або троє людей, попарно незнайомих одне з одним.
Класичні результати
Припустимо, наприклад, що ми знаємо, що кроликів розсаджено в
кліток. Наскільки великим має бути
щоб гарантовано в одній з кліток було принаймні 2 кроликів? Згідно з принципом Діріхле, якщо
, то знайдеться клітка, в якій буде мінімум 2 кроликів. Теорія Ремзі узагальнює цей принцип.
Огляд результатів до 1990 р. дано в роботі.
Теорема Ремзі
Сам Ремзі довів таку теорему:
Нехай дано числа |
Її було узагальнено на випадок гіперграфу.
Мінімальне число , за якого для заданого набору аргументів
існує зазначене в теоремі розфарбування, називається числом Ремзі. Питання про значення чисел Ремзі за невеликим винятком залишається відкритим.
Схожа за формулюванням, але відрізняється доведенням теорема ван дер Вардена:
Для кожного набору чисел |
Найменше таке число називається числом ван дер Вардена.
Замість множини натуральних чисел можна розглянути ґратку , а арифметичних прогресій — фігури в ній, гомотетичні даній, і твердження теореми залишиться правильним (узагальнена теорема ван дер Вардена).
Теорема Хейлса — Джеветта
Для будь-яких чисел |
З цієї теореми випливає, що під час гри в багатовимірні хрестики-нулики при будь-якій довжині рядка та будь-якому числі гравців можна знайти таке число вимірів, що нічия буде неможлива.
(Гіпотеза Ердеша — Секереша про опуклі багатокутники)
Для будь-якого натурального |
Згідно з гіпотезою Ердеша та Секереша про опуклі багатокутники число точок в загальному положенні, у яких обов'язково існує опуклий -кутник задається формулою:
для всіх
Вони ж довели, що у множині з меншим числом точок опуклий -кутник може не існувати.
Теорема Крута про одноколірний єгипетський дріб
Для будь-якої розмальовки цілих чисел більших від При цьому максимальний елемент, а отже й розмір множини |
Цю [ru] довів 2003 року [en].
Особливості теорії
Для результатів у рамках теорії Ремзі характерні дві властивості. По-перше, вони неконструктивні. Доводиться, що деяка структура існує, але не пропонується жодного способу її побудови, окрім прямого перебору. По-друге, щоби шукані структури існували, потрібно, щоб об'єкти, які їх містять, складалися з дуже великого числа елементів. Залежність числа елементів об'єкта від розміру структури зазвичай, принаймні, експоненціальна.
Див. також
Примітки
- Graham, R.; Rothschild, B.; (1990), Ramsey Theory (вид. 2nd), New York: John Wiley and Sons, ISBN .
- Ramsey, F. P. (1930), On a problem of formal logic, Proc. London Math. Soc. Series 2, 30: 264—286, doi:10.1112/plms/s2-30.1.264
- van der Waerden, B. L. (1927). Beweis einer Baudetschen Vermutung. Nieuw. Arch. Wisk. 15: 212—216.
- Hales A., Jewett R. Regularity and positional games // Trans. Amer. Math. Soc. 106 (1963), p. 222—229.
- Erdős, P.; Szekeres, G. (1935), , Compositio Math, 2: 463—470, архів оригіналу за 19 лютого 2019, процитовано 18 лютого 2019
Література
- Мартин Гарднер. Глава 17. Теория Рамсея // От мозаик Пенроуза к надёжным шифрам = Penrose Tiles to Trapdoor Ciphers / пер. с англ. Ю. А. Данилова. — М. : Мир, 1993. — С. 288—308. — 416 с. — 10 000 екз. — .
Посилання
- Теорія Ремзі (рос.) [ 19 лютого 2019 у Wayback Machine.]
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет