Юбилей теоремы Райского

Квант 2019, №7 с. 11-12 Тег PUP5

А.РОМАНОВ

ЛЕТ НАЗАД В ЖУРНАЛ «МАТЕМА- тические заметки» была подана статья школьника Дмитрия Райского [1] с существенным продвижением в проблеме, поставленной Хадвигером [2]. Дмитрий доказал такую теорему: При раскраске плоскости в три цвета (разбиении на три непересекающиеся множества) всегда можно выбрать цвет, в котором реализуются все расстояния, т.е. для любого положительного d найдутся две точки на расстоянии d, окрашенные в выбранный цвет. Теорема Райского является заметным усилением доказанной в 1961 году братьями Мозерами теоремы о том, что при раскраске плоскости в три цвета найдутся две точки одного цвета на расстоянии 1. При подготовке статьи [1] к печати теорема была обобщена на N-мерное пространство и существенно отредактирована. В результате работа школьника оказалась трудночитаемой и недоступной для юных математиков. Здесь я постарался воспроизвести первоначальный вариант решения. Я благодарен Н.Н.Константинову, который в 1971 году рассказал мне доказательство теоремы Райского. Константинов помогал Дмитрию в подготовке статьи и без его участия публикация вряд ли была бы возможна.

Определенное таким образом произведение содержит не более чем $n_{◊} k$ различных векторов, так как суммы векторов для разных пар могут и $совпадать.^{Лемма} 1.$ Если мы рассмотрим повороты k-пучка на произвольный угол, то лишь для конечного числа углов поворота произведение фиксированного n-пучка и повернутого k-пучка будет содержать менее чем $n_{◊} k$ различных векторов. Действительно, выбрать два различных вектора a, b из n-пучка и два различных вектора c, d из k-пучка можно лишь конечным числом способов. Для каждой такой четверки векторов рассмотрим повороты k-пучка на угол D и сравним суммы векторов $a_{+} c_{D}$ и $b_{+} d_{D}$ . Так как окружности пересекаются не более чем в двух точках, не более двух углов D могут дать равенство этих сумм, что и доказывает лемму $1.^{Лемма} 2.$ Если произведение n-пучка и k-пучка содержит n ◊ k различных векторов, то n ◊ k концов этих векторов образуют n фигур, полученных параллельным переносом k-точечника, и k фигур, полу-

Вспомогательные леммы

Пусть на плоскости задана фигура из n различных точек – n-точечник. Выберем одну из этих точек и назовем n-пучком набор векторов, выходящих из этой точки ко всем точкам n-точечника (один из векторов n-пучка – нуль-вектор). Определим произведение n-пучка и k-пучка как пучок векторов a + c, где вектор a берется из n-пучка, а c – из k-пучка.

DOI: https://doi.org/10.4213/kvant20190702

Рис. 1

ченных параллельным переносом n-точечника (рис.1).

Доказательство теоремы

Предположим, что утверждение неверно и существует раскраска плоскости в три цвета, для которой нельзя выбрать цвет, в котором реализуются все расстояния. Тогда для этой раскраски у каждого цвета есть

ЮБИЛЕЙ

ТЕОРЕМЫ

расстояние, которого не может быть между двумя точками это цвета. Рассмотрим 7-точечник, предложенный братьями Мозерами, который Райский назвал «зондом» (рис.2). Все нарисованные отрезки имеют длину 1. Простым перебором можно убедиться, что если из

РАЙСКОГО

любом зонде для цвета 1 из 7 точек не более двух цвета 1, в любом зонде для цвета 2 из 7 точек не более двух цвета 2, а в любом зонде для цвета 3 из 7 точек не более двух цвета 3. Тем самым, не более $2_{◊} 7^{2}$ точек может быть окрашено в каждый цвет, всего не более $6_{◊} 7^{2}$ точек из $7^{3}$ может быть окрашено. Доказательство завершено.

Многомерный случай

Рис. 2

этих семи точек выбрать любые три, то найдутся две выбранные точки, соединенные отрезком. Из этого сразу следует теорема Мозеров. У нас для каждого цвета будет свой 7-точечник-зонд, в котором вместо 1 будет отсутствующее в этом цвете расстояние. Выберем произвольную точку плоскости и все векторы пучков будем считать выходящими из этой точки. Пронумеруем цвета произвольно и рассмотрим зонд для цвета 1. В каждом из трех 7-точечников-зондов выберем одну из 7 точек, например $A_{4}$ . Тогда для каждого зонда определен свой 7-пучок. По лемме 1 повернем 7-точечник-зонд для цвета 2 на такой угол, чтобы произведение 7-пучков 1 и 2 содержало $7^{2}$ различных векторов (было 49-пучком), а 7-точечник-зонд для цвета 3 повернем на такой угол, чтобы произведение 49-пучка и этого 7-пучка содержало $7^{3}$ различных векторов. По лемме 2, концы этих $7^{3}$ векторов – $7^{3}$ различных точек на плоскости – образуют 49 зондов для цвета 3, они же образуют 49 зондов для цвета 2 и 49 зондов для цвета 1. Для завершения доказательства достаточно заметить, что в

В статье Райского приведено доказательство теоремы для n-мерного пространства: Пусть множества $A_{1}, A_{2},^{…}, A_{n} +_{1}$ образуют покрытие n-мерного евклидова пространства $R^{n} (n >$ 1); тогда среди них найдется такое множество $A_{i}$ , что для всякого d > 0 найдется пара точек из этого множества, расстояние между которыми равно d. Для доказательства теоремы в таком виде не требуется новых идей, кроме конструирования зонда в $R^{n}$ и доказательства леммы 1. Чтобы не жертвовать доступностью изложения, рассмотрим случай трехмерного пространства, для больших измерений трудности носят чисто технический характер. (Заметим, что в статье Райского доказательство существенно отредактировано, здесь я постарался воспроизвести первоначальный вариант.) Построим зонд для $R^{3}$ . Веретеном Райский назвал 5-точечник из четырех вершин правильного тетраэдра со стороной d и еще одной точки b, симметричной одной из его вершин – вершине a – относительно грани (рис.3). Зондом он назвал 9-точечник, полученный из двух веретен, совмещенных вершинами a и повернутых так, чтобы расстояние между точками b этих веретен тоже было равно d (рис.4). Рис. 3

КВАНТ 2019/№7

Лемма 2 меняется незначительно. Произведение n-пучка и k-пучка содержит n k векторов с учетом кратности, и n k концов этих векторов образуют n фигур, полученных параллельным переносом k-точечника, и k фигур, полученных параллельным переносом n-точечника. Каждая точка произведения пучков встречается в этих фигурах столько раз, какова кратность точки. При таком подходе многомерный случай отличается от двумерного только конструкцией зонда.

Оценка сверху

Рис. 4

Очевидно, что такой поворот веретен существует. Доказательство леммы 1 нуждается в незначительной модернизации. Для заданного n-точечника выберем плоскость в $R^{3}$ так, чтобы проекция n-точечника на эту плоскость содержала n различных точек. Выберем исходное положение (поворот) k-точечника относительно этой плоскости, чтобы его проекция содержала k различных точек. На плоскости получились n- пучок и k-пучок, для которых справедлива лемма 1. Рассмотрим поворот исходного k- пучка вокруг прямой, перпендикулярной выбранной плоскости. Проекция на плоскость содержит $n_{◊} k$ различных векторов, что и доказывает лемму 1 для $R^{3}$ . Остальная часть доказательства проводится без изменений.

До публикации статьи Райского была известна раскраска плоскости в 7 цветов, в которой любые две точки на расстоянии 1 раскрашены в разные цвета. Эта раскраска основана на разбиении плоскости на равные правильные шестиугольники. С.Б.Стечкин заметил (и с разрешения Райского вставил в статью), что плоскость можно разбить на 6 таких множеств, чтобы на каждом из них реализовались не все расстояния. Элемент конструкции состоит из 4 правильных шестиугольников и 8 правильных треугольников. Путем параллельных переносов этим элементом мостится вся плоскость, как показано на ри-

Оптимизация доказательства теоремы Райского

Предложенное доказательство не использует идей, отсутствующих в первоначальном варианте Райского. Оказывается, можно отказаться от рассмотрения поворотов, делающих точки не совпадающими (лемма 1). Вместо этого можно каждому вектору произведения n-пучка и k-пучка приписать кратность – количество вариантов выбора вектора из n-пучка и вектора из k-пучка, для которых суммы векторов совпадают.

Рис. 5

сунке 5. Все треугольники являются открытыми, а нижние и правые вершины шестиугольников не принадлежат этим фигурам. Если принять сторону треугольника за 1, то расстояние $d_{1} = 2$ не реализуется на множествах $A_{1},^{…}, A_{4}$ одинаково

(Продолжение см. на с. 23)