В 1928 году Фрэнк Пламптон Рамсей, английский математик, философ и экономист, доказал, что такие упорядоченные конфигурации неизбежно присутствуют в любой большой структуре, будь то группа звёзд, совокупность случайно разбросанных камешков или последовательность чисел, полученных бросанием игральной кости. Если речь идёт о достаточно большом количестве звёзд, то всегда можно найти группу, которая с очень большой точностью образует какую-нибудь заданную конфигурацию: прямую линию, прямоугольник или, если уж мы заговорили о звёздах, большой ковш. Фактически теория Рамсея утверждает, что любая структура обязательно содержит упорядоченную подструктуру.
В МИРЕ НАУКИ
Scientific American · Издание на русском языке№ 9 · СЕНТЯБРЬ 1990 · С. 70–76
Теория Рамсея
Что из этого следует?
- Любая структура обязательно содержит упорядоченную подструктуру.
- Полный беспорядок невозможен.
Сколько должно быть объектов, чтобы возникла подструктура?
Ответ - числа Рамсея.
Числа Рамсея определяются как наименьшее значение n, для которого в любой группе из n точек некоторая группа из j точек образует структуру.
Задачи в теории Рамсея обычно звучат в форме вопроса «сколько элементов должно быть в некотором объекте, чтобы гарантированно выполнялось заданное условие или существовала заданная структура». Простейший пример: доказать, что в любой группе из 6 человек найдутся либо 3 человека, попарно знакомые друг с другом, либо 3 человека, попарно незнакомые друг с другом. Для доказательства возьмём любого из шестерых — назовём его А. Предположим, что он знает хотя бы троих из оставшихся. Если среди этих троих есть двое знакомых, они образуют искомую тройку (попарно знакомых) с А, если нет — то тройку попарно незнакомых между собой. Если же А знает не более двоих из оставшихся, то у него есть трое незнакомых, и для них работает аналогичное рассуждение. Также легко видеть, что в компании из пяти человек может уже не найтись троих попарно знакомых или попарно незнакомых: поставим пятерых изначально незнакомых людей по кругу и познакомим соседей.
Обычно для визуализации числе Рамсея используется граф.
В этом случае граф будет содержать n вершин, которые соединены каждый с каждым. Ребра раскрашены в два цвета. Число Рамсея определяет, сколько должны быть вершин в графе, чтобы в нем существовал полный граф с ребрами одного цвета, состоящий из j вершин.
Если есть граф с шестью вершинами (это люди), ребра которого раскрашены в красный и синий цвета (знакомство и незнакомство соответственно), то найдутся три вершины, соединённые рёбрами одного цвета. А для графа с пятью вершинами такой тройки может и не быть.
А если мы хотим найти в какой-нибудь группе больше людей, которые или каждый с каждым знакомы, или каждый с каждым не знакомы? Верно ли, что какие бы значения n и k мы не взяли, в достаточно большой компании найдутся или n попарно знакомых, или k попарно незнакомых людей? Да, верно: это утверждает теорема Рамсея, доказанная им в 1930 г. Наименьший размер компании, заведомо удовлетворяющей этому условию, обозначается R(n, k) и называется числом Рамсея. Или, учитывая синюю группу из n вершин или красную группу из k вершин, минимальное количество вершин, которое должен иметь полный граф, чтобы каждое ребро было окрашено в красный или синий цвет.
А если мы хотим найти в какой-нибудь группе больше людей, которые или каждый с каждым знакомы, или каждый с каждым не знакомы? Верно ли, что какие бы значения n и k мы не взяли, в достаточно большой компании найдутся или n попарно знакомых, или k попарно незнакомых людей? Да, верно: это утверждает теорема Рамсея, доказанная им в 1930 г. Наименьший размер компании, заведомо удовлетворяющей этому условию, обозначается R(n, k) и называется числом Рамсея. Или, учитывая синюю группу из n вершин или красную группу из k вершин, минимальное количество вершин, которое должен иметь полный граф, чтобы каждое ребро было окрашено в красный или синий цвет.
Другая интерпретация чисел Рамсея связана с арифметическими прогрессиями. Например, если каждое число от 1 до 9 покрасить в красный или синий цвет, то либо три синих числа, либо три красных образуют арифметическую прогрессию. Можно увеличивать число членов арифметической прогрессии, раскрашивать их и определять наибольшую длину арифметической прогрессии, определяемую числами одного цвета.
Еще более интересный факт связан с тем, что данная задача связана с игрой в крестики нолики, особенно с трехмерным вариантом этой игры. В частности, рассматривают куб с 64 ячейками (по четыре на каждую сторону).
Числа Рамсея представлена последовательностью A212954 (https://oeis.org/A212954) и известно их мало. Для больших чисел есть только оценки нижней и верхней грани.
Например, зададимся вопросом, какой длины должна быть последовательность натуральных чисел, раскрашенных случайным образом в два цвета, например, красным и синим, чтобы в нем появилась красная арифметическая прогрессия длиной 3 и синяя длиной 9. Можно и наоборот, поменять цвета. Такое число обозначается R(3,9). Ответ - 36. То есть, если 36 первых натуральных чисел раскрасить случайным образом в два цвета, то обязательно в таком ряду найдется арифметическая прогрессия из 9 одноцветных чисел!. Так из хаоса появляется сложный порядок.
Для определенности приведу пример, что то же вопрос, касательно одноцветных прогрессии в 10 чисел одного цвета, и синего, и красного, не имеет точного значения числа Рамсея, а только интервальную оценку. Такой порядок, 10 красных и 10 синих может появиться в натуральных рядах от (минимум) 798 чисел до (максимум) 23556. Это число Рамсея обозначается R(10,10).
Сам факт, что 797 чисел мало для возникновения порядка, а 23556 гарантирует возникновение порядка. Точное же значение числа Рамсея находится где то в этих пределах.
Вывод же - полный беспорядок невозможен. Обязательно проявится структура. И этот вывод - просто математика. Просто идея, которая вне времени, вне пространства.
Возможно, возникновения порядка в больших структурах препятствует написанию длинных приключенческих историй с продолжениями. В любой приключенческой истории конечное число героев, как минимум их двое, - отрицательный и положительный герой. Рано или поздно, сюжетные эпизоды просто обязаны повторяться и возникновение повторяющейся структуры уничтожит новизну и все загадки, ради которых выстраиваются сюжетные линии. И тем самым, интерес угаснет. Больше героев, больше линий, полифоничность текста лишь отдалит момент появления структур. Неизбежность же появления структур будет определяться числами Рамсея.
Приложение
Теория Рамсея возникла как обобщение принципа Дирихле. Для её результатов характерна неконструктивность: доказывается, что некоторая структура существует, но не предлагается никакого способа её построения кроме прямого перебора. Кроме того, для существования искомых структур требуется, чтобы объекты, их содержащие, состояли из очень большого числа элементов. Зависимость числа элементов объекта от размера структуры обычно, как минимум, экспоненциальная.Верхняя оценка числа Рамсея (m,n больше равны 1):
Комментариев нет:
Отправить комментарий