Скачать

Теория Рамсея

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

Рональд Л. Грэм, Джоуэл X. Спенсер

Как повествует написанный три с половиной тысячи лет назад клинописный текст, однажды древнешумерский учёный взглянул на звёздное небо и увидел льва, буйвола и скорпиона. Современный астроном скорее всего склонен описывать созвездие как временную группу звёзд, которую мы, земляне, наблюдаем с одной точки на краю обычной галактики. И всё же большинство любителей поглазеть на звёзды согласятся, что ночное небо выглядит сплошь усыпанным созвездиями, имеющими форму прямых линий, четырёхугольников и пятиугольников. Может ли так быть, что подобные геометрические фигуры порождаются какими-то неизвестными нам силами, действующими во Вселенной?

Математика предлагает куда более простое объяснение. В 1928году Фрэнк Пламптон Рамсей, английский математик, философ и экономист, доказал, что такие упорядоченные конфигурации неизбежно присутствуют в любой большой структуре, будь то группа звёзд, совокупность случайно разбросанных камешков или последовательность чисел, полученных бросанием игральной кости. Если речь идёт о достаточно большом количестве звёзд, то всегда можно найти группу, которая с очень большой точностью образует какую-нибудь заданную конфигурацию: прямую линию, прямоугольник или, если уж мы заговорили о звёздах, большой ковш. Фактически теория Рамсея утверждает, что любая структура обязательно содержит упорядоченную подструктуру. Как впервые провозгласил около четверти века назад умерший недавно американский математик Теодор С.Моцкин, из теории Рамсея следует, что полный беспорядок невозможен.

Специалисты по теории Рамсея стараются вычислить, сколь велико должно быть множество звёзд, чисел или каких-либо объектов, чтобы можно было гарантировать существование определённой желаемой подструктуры. На решение таких задач часто требуются десятилетия, и поддаются они только при самом изобретательном и тонком рассуждении. Пытаясь найти решения поставленной задачи, специалисты по теории Рамсея помогают тем самым инженерам в построении более совершенных сетей коммуникации и систем передачи и поиска информации. Они также открыли некоторые математические методы, которые пригодятся учёным следующего столетия. Возможно, самое важное заключается в том, что теория Рамсея исследует основополагающую структуру математики, т.е. структуру, пронизывающую всю Вселенную.

В отличие от многих разделов современной математики теорию Рамсея можно изложить на интуитивном уровне. В самом деле, привлекательность этой теории отчасти обусловлена той простотой, с которой можно сформулировать её задачи. Например, если из присутствующих на вечеринке случайным образом выбрать шесть человек (скажем, Альфреда, Бетти, Кэлвина, Дебору, Эдварда и Фрэнсис), то верно ли, что либо трое из них друг с другом знакомы, либо трое из них незнакомы друг с другом?

Мы можем решить эту «головоломку о вечеринке» многими способами. Мы могли бы перебрать все мыслимые комбинации и проверить, содержит ли каждая рассматриваемая группа трёх знакомых или трёх незнакомых людей. Но поскольку нам пришлось бы проверить 32768 (или 2¹⁵) комбинаций, то такой «метод грубой силы» не является ни практичным, ни поучительным.

К счастью, мы можем отыскать ответ, рассмотрев два простых случая. В первом из них предположим, что Альфред знает трёх (или больше) из числа остальных гостей, скажем, Бетти, Кэлвина и Дебору. Если Бетти и Кэлвин, или Бетти и Дебора, или Кэлвин и Дебора знакомы друг с другом, то Альфред и пара знакомых образуют группу из трёх знакомых людей; в противном случае Бетти, Кэлвин и Дебора друг с другом незнакомы. Во втором случае предположим, что Альфред знает самое большее двух (или меньше) из гостей, скажем, Бетти и Кэлвина. Если Дебора и Эдвард, или Дебора и Фрэнсис, или Эдвард и Фрэнсис незнакомы друг с другом, то Альфред и пара незнакомых между собой гостей образуют группу из трёх человек, незнакомых друг с другом. В противном случае Дебора, Эдвард и Фрэнсис друг с другом знакомы. Всего в шести предложениях мы доказали, почему любая группа из шести человек должна включать или трёх знакомых, или трёх незнакомых людей. Короче говоря, решение «головоломки о вечеринке» есть частный случай теории Рамсея.