Задача Эрдёша—Секереша о выпуклых многоугольниках

6

КВАНТ 2009/№2

Задача Эрдеша – Секереша о выпуклых многоугольниках

В.КОШЕЛЕВ, А.РАЙГОРОДСКИЙ

Напутствие

Задача, о которой мы хотим поговорить в этой статье, по праву считается одной из жемчужин комбинаторной геометрии. Исключительная простота ее постановки делает рассказ о ней доступным школьнику, а нетривиальность ее решения и многочисленные ее связи с другими областями математики сразу же выводят заинтересованного слушателя на передний край современной комбинаторики. Задача эта возникла в 1934 году, и, хотя умение быстро считать не является, вопреки расхожему мнению, отличительной особенностью математика, каждый из нас моментально сообразит, что в этом году исполняется ровно 75 лет со дня ее рождения. Не правда ли, круглая дата? Что ж, давайте ее отметим.

Первые шаги

Постановка задачи

Рассмотрим какое-нибудь конечное множество точек X на плоскости и зададимся, например, таким вопросом: верно ли, что в множестве X всегда найдутся три точки, являющиеся вершинами треугольника? На первый взгляд, вопрос кажется просто нелепым. Ясно же, что если в X одна или две точки, то и говорить не о чем; если же X ³ 3 (мощность X не меньше тройки), то вроде как любые три элемента в множестве служат вершинами треугольника. Так-то оно так, да не совсем: а что если какие-то три точки из множества X лежат на одной прямой? Тогда вряд ли уместно говорить о треугольнике с вершинами в них. И уж вовсе никуда не годится ситуация, в которой все точки нашего множества оказываются «нанизанными» на одну прямую. Короче, ответ на вопрос неожиданно отрицательный. Однако если мы с самого начала допустим, что в множестве X никакие три точки не лежат на одной прямой, то сработает естественная логика и при условии X ³ 3 мы сможем гарантировать наличие треугольников в X. Хорошо, с треугольниками разобрались. А как тогда обстоят дела с $выпуклыми^{1}$ четырехугольниками, вы-

1 Множество называется выпуклым, если вместе с любыми двумя своими точками оно содержит и весь отрезок, их соединяющий.

пуклыми пятиугольниками и т.д.? Хочется, по идее, получить ответ в той же форме, что и в случае треугольников, а именно: для каждого n О ¥, n ³ 3, желательно отыскать такую «пограничную» величину $g ( n ) О^{¥}$, чтобы в каждом множестве X, не содержащем троек точек на одной прямой и имеющем не менее g ( n ) элементов, нашлись n вершин выпуклого n- угольника и чтобы для g ( n ) - 1 описанное свойство не выполнялось. Вот g ( 3 ) = 3, а чему равны g ( 4 ), g ( 5 ) и пр.? Вообще, существуют ли (вернее, конечны ли) эти величины? Ведь вполне может статься, что, скажем, для любого m найдется множество X размера m, в котором нет вершин выпуклых десятиугольников. Кто знает? Проблема Эрдеша – Секереша, к изучению которой мы теперь переходим, как раз и состоит в отыскании величин g ( n ). Ниже мы расскажем много интересного о ней, а сейчас сделаем небольшое замечание. Для постановки задачи оказалось очень важно предположить, что множества X не содержат троек точек на одной прямой. В действительности, такое свойство очень часто работает в геометрии, и потому для него придуман специальный термин: говорят, что множество X c этим свойством находится в общем положении. Происхождение термина связано с тем, что в некотором естественном смысле «почти все» множества на плоскости находятся в общем положении, – отсюда и общность. Впрочем, мы не станем здесь давать более подробные комментарии, иначе мы уйдем слишком далеко в сторону от нашего основного маршрута. Главное, что отныне, рассматривая множества точек на плоскости, мы будем подразумевать, что они находятся в общем положении: иные множества нас просто не волнуют.

Разберемся с четырехугольниками

Очевидно, что g ( 4 ) > 3 (на трех точках четырехугольнику взяться неоткуда). Может быть, g ( 4 ) = 4? Разумеется, нет. Достаточно посмотреть на рисунок 1, чтобы понять это: изображенные на картинке точки находятся в общем положении, и, тем не менее, среди них нет вершин выпуклых четырехугольников. Итак, g ( 4 ) ³ 5. Покажем, что g ( 4 ) = 5, т.е. убедимся, что в любом

9

ЗАДАЧА

ЭРДЕША

–

СЕКЕРЕША

своих задач он назначал некие суммы денег, ранжируя, тем самым, задачи по «трудности». Кажется, самой большой из когда-либо предложенных им сумм была сумма в 3000 долларов. А о гипотезе 1 он незадолго до своей смерти в 1996 году писал, что, несомненно, заплатил бы за ее доказательство 500 долларов. Забавно и то, что за опровержение гипотезы он денег не предлагал: видимо, свято верил в ее справедливость и не хотел стимулировать движение математической мысли в неверном, с его точки зрения, направлении. С гипотезы 1, попыток доказать ее и возникающей вокруг этого многогранной проблематики начинается по-настоящему серьезная работа над задачей. И в дальнейшем мы поговорим об этом. Прежде всего: а разве мы где-то, вообще, показали, что g ( n ) < ¥ для каждого n?

Так почему же g ( n ) всегда существует?

Несколько слов о теореме Рамсея

В математике все взаимосвязано, и иной раз для решения задачи из одной области приходится применять соображения из областей, которые, на первый взгляд, могут показаться весьма далекими от нее. Так и здесь: мы увидим вскоре, что задача Эрдеша – Секереша имеет непосредственный выход на классическую теорему Рамсея в комбинаторике. Давайте вспомним, что это такое, постепенно переходя от простых частных случаев к несколько более сложным общим ситуациям. Итак, многие читатели, вероятно, слышали такое классическое школьное утверждение: среди любых шести человек есть либо трое попарно знакомых, либо трое попарно незнакомых людей. Это утверждение очень легко доказать, и соответствующее рассуждение каждый без труда проделает сам. Заметим, кстати, что аналогичное утверждение для пяти человек, вообще говоря, не является верным. Описанную ситуацию удобно (и принято) формулировать в терминах графов. Действительно, речь фактическти идет о том, чтобы рассмотреть полный граф на шести вершинах-«людях», раскрасить все его $C_{6}^{2} = 15$ ребер в красный и синий цвета (ребро красное – люди знакомы, ребро синее – люди не знают друг друга) и убедиться в том, что либо в графе есть треугольник, у которого все ребра красные, либо в графе есть треугольник, у которого все ребра синие. При этом, опять же, для полного графа на пяти вершинах такой номер не проходит. А вот и чуть более общее утверждение на языке графов. Для любых натуральных чисел s, t существует наименьшее натуральное число $m_{0}$, обладающее следующим свойством. Каково бы ни было m ³ $m_{0}$ и какова бы ни была раскраска ребер полного графа на m вершинах в красный и синий цвета, либо в графе есть полный подграф на s вершинах, у которого все ребра красные, либо в графе есть полный подграф на t вершинах, у которого все ребра синие. Например, при s = t = 3 имеем $m_{0} = 6$. Теперь заметим, что ребра графа суть, конечно, двухэлементные подмножества множества его вершин.

О

ВЫПУКЛЫХ

МНОГОУГОЛЬНИКАХ

А что если мы отныне станем красить не ребра, но трех-, четырех-,…, k-элементные подмножества данного множества? Чем это хуже? Ничем! И вот, наконец, теорема Рамсея во всей своей полноте. Теорема Рамсея. Для любых натуральных чисел $k, l_{1},^{K}, l_{r}$ существует наименьшее натуральное число $m_{0}$, обладающее следующим свойством. Каково бы ни было m ³ $m_{0}$, если каждое k-элементное подмножество множества {1, …, m} покрашено в один из r цветов с «именами» 1, …, r, то найдется i О { 1, K r } и такое $l_{i}$ -элементное подмножество T М { 1, K, m }, что все его k -элементные подмножества имеют цвет с именем i. Результат про графы вытекает из этой теоремы при $k = 2, r = 2, l_{1} = s, l_{2} = t.$ Есть тут и своя маленькая логическая тонкость, которую пытливый читатель должен, по идее, заметить сразу: а что если $k > l_{i}$ при каком-нибудь i? Скажем, пусть по-прежнему k = 2, r = 2, но $l_{1} = 1, l_{2} = 100.$ В этом случае срабатывает принцип «все крокодилы в реке Тумча красные». Смысл в том, что про отсутствующие элементы можно сказать все что угодно и, стало быть, здесь $m_{0} = 1.$ Аналогичные рассуждения применимы и в других подобных случаях. Доказательство теоремы Рамсея получается с помощью многократной индукции и, будучи элементарным, требует все же чересчур много места для своего изложения в нашей заметке. По счастью, это настолько классический факт, что отыскать его полное доказательство не составляет большого труда. Читатель может обратиться как к оригинальным работам [5] и [2], так и к различным популярным источникам типа [6], [7] и [8]. Заметим, что для величины $m_{0}$, фигурирующей в теореме, используется более или менее стандартное обозначение $R_{k} ( l_{1},^{K}, l_{r} )$. В частности, мы уже говорили, что $R_{2} ( 3, 3 ) = 6$ и $R_{2} ( 1, 100 ) = 1$. Кстати, таких точных равенств известно очень мало. Их перечень проще всего найти в Википедии (см. [9]), откуда есть ссылка на обзор [10]. В следующем параграфе мы применим теорему Рамсея для доказательства того, что g ( n ) < ¥.

Два фокуса

Сейчас мы докажем, что g ( n ) £ $R_{4} ( n, 5 )$. Действительно, пусть X – множество точек, состоящее из не менее чем $R_{4} ( n, 5 )$ элементов. Покрасим все четверки точек в нем в красный и синий цвета: если данные четыре точки являются вершинами выпуклого четырехугольника, объявляем четверку красной; иначе говорим, что она синяя. По теореме Рамсея возможны два варианта. В одном из них в X найдутся пять точек, среди которых все четверки синие, т.е. нет ни одной четверки, которая бы порождала выпуклый четырехугольник. Но это нонсенс, так как противоречит утверждению Кляйн о том, что g ( 4 ) = 5. Значит, остается лишь альтернатива, при которой в X есть n точек без синих четверок. Иными словами, все четырехугольники, порождаемые этими точками, выпуклые. Такое возможно только в случае, если сами эти n точек суть