Яглом И. М.

О задаче РадоЯглом И. М. О задаче Радо // Квант. — 1975. — № 8. — С. 40⁠—⁠45.‍‍

По-видимому, гипотетический (и имеющий отношение только к математике, а не к биологии) пример живых существ, для которых внешний мир — двумерная плоскость, а не трёхмерное пространство, принадлежит знаменитому немецкому естествоиспытателю и математику Г. Гельмгольцу: это водомерки — «водяные пауки», скользящие движения которых по поверхности воды можно увидеть в любом застоявшемся водоёме. «Водомерки» Гельмгольца так же не в состоянии вообразить привычный нам «трёхмерный» мир, как человек не может представить себе «четырёхмерное пространство»‍.

Мы начнём с ещё более примитивного, чем у водомерок, внешнего мира: с одномерного аналога задачи М321. Даже в таком «облегчённом» варианте она отнюдь не становится бессодержательной.

Покрытия отрезка

Сейчас у нас и «столы», и «салфетки» — не прямоугольники, а отрезки прямой. Нас интересует такое

Утверждение. Пусть заданы отрезок $o$‍‍ длины 1 («стол») и число $\eps\gt0$‍.‍ Тогда можно указать систему отрезков («салфеток»), покрывающих «стол» $o$‍,‍ такую, что любая подсистема непересекающихся отрезков (неперекрывающихся «салфеток») имеет общую длину, меньшую $\eps$‍‍‍.

Верно это Утверждение или нет?

Испытаем сначала самые простые системы «салфеток». На рисунке 1, а «стол» покрыт тремя «салфетками» длины $\dfrac13$‍.‍ Из них можно выбрать подсистему из двух неперекрывающихся «салфеток» с общей длиной $\dfrac23$‍.‍ (Можно, конечно, выбрать подсистему из одной «салфетки», но длина такой подсистемы меньше.) Итак, если $\eps\gt\dfrac23$‍,‍ то наше утверждение верно: мы указали систему отрезков такую, что любая её подсистема, состоящая из непересекающихся отрезков, имеет общую длиHy, не большую $\dfrac23$‍,‍ т. е. меньшую $\eps$‍.‍

Упражнение 1. Докажите, что для $\eps\gt\dfrac12$‍‍ Утверждение тоже верно. (Постройте соответствующее покрытие отрезка- «стола» $o$‍‍ меньшими отрезками-«салфетками».)

Ясно, что каждый пример системы отрезков $K$‍‍ гарантирует справедливость нашего утверждения лишь при $\eps\gt d_k$‍,‍ где $d_k$‍‍ — некоторое положительное число, зависящее от этой системы $K$‍.‍ Так, для примера на рисунке 1, а $d_k=\dfrac23$‍;‍ на рисунке 1, б $d_k=\dfrac35$‍.‍ А вообще $d_k$‍‍ — это наибольшая длина подсистемы $K'\subset K$‍,‍ состоящей из непересекающихся отрезков. Ясно, что чем меньше $\eps$‍,‍ тем труднее строить пример. Может случиться так, что при $\eps$‍,‍ бо́льших какого-то $\eps$‍,‍ наше Утверждение верно, а при меньших $\eps$‍‍ — уже нет. Докажем, что для одномерного варианта нашей задачи дело обстоит именно так.

При $\eps=\dfrac13$‍‍ Утверждение неверно.

Другими словами, никакая система «салфеток» не может послужить требуемым примером для $\eps=\dfrac13$‍,‍ т. е. любая система «салфеток» содержит подсистему неперекрывающихся «салфеток», покрывающих часть «стола» $o$‍‍ длины $\dfrac13$‍‍ $\Big($‍‍или больше $\dfrac13\Big)$‍.‍

Пусть дана какая-то система отрезков $K$‍,‍ покрывающих отрезок $o$‍‍ длины 1. Выберем из $K$‍‍ наибольший отрезок, обозначим его $i_1$‍.‍ Выбросим теперь из системы $K$‍‍ все отрезки покрытия, пересекающиеся с отобранным отрезком $i_1$‍‍ (они покрывают отрезок длины не больше $3|i_1|$‍,‍ где $|i|$‍‍ — длина отрезка $i$‍).‍ Из ocтавшихся отрезков покрытия снова выберем наибольший (обозначим его $i_2$‍)‍ и выбросим все те отрезки, которые пересекаются с $i_2$‍‍ (они покрывают отрезок длины не больше $3|i_2|$‍),‍ и т. д., пока не исчерпаем всех отрезков покрытия. Выбранная подсистема непересекающихся отрезков $i_1$‍,‍ $i_2$‍,‍ $\ldots$‍‍ такова, что $$ 3|i_1|+3|i_2|+\ldots\ge1, $$ поскольку отрезки длины $3|i_1|$‍,‍ $3|i_2|$‍,‍ $\ldots$‍‍ в совокупности покрывают всю данную систему $K$‍‍ и, стало быть, весь отрезок $o$‍‍ длины 1. Поэтому сумма длин $|i_1|+|i_2|+\ldots$‍‍ не меньше $\dfrac13$‍.‍

На рисунке 2 показан процесс выбора такой подсистемы $\{i_1,i_2,i_3\}$‍‍ для системы из семи отрезков.

Упражнение 2.

1. Докажите, что из любой системы «салфеток», покрывающих «стол», можно выбрать подсистему «салфеток», которая тоже покрывает «стол», и такую, что никакая точка «стола» не покрыта более чем двумя «салфетками».
2. Докажите, что и при $\eps=\dfrac12$‍‍ Утверждение неверно.

Упражнение 3. Докажите, что если «стол» — по-прежнему отрезок длины 1, а «салфетки» могут быть и «дырявыми», т. е. каждая «салфетка» может состоять из одного или нескольких отрезков, то Утверждение, сформулированное в начале этого пункта, верно при всех $\eps\gt0$‍.‍

Решив упражнения 1 и 2, вы докажете следующий факт:

Теорема 1. Пусть «стол» и «салфетки» — отрезки, длина «стола» равна $1$‍.‍

1. Из любой системы «салфеток», покрывающих «стол», можно выделить подсистему неперекрывающихся «салфеток» общей длины нё меньше $\dfrac12$‍.‍
2. Если $\eps\gt\dfrac12$‍,‍ то всегда можно указать систему «салфеток» такую, что любая её подсистема неперекрывающихся «салфеток» имеет длину меньше $\eps$‍.‍

Другими словами, Утверждение верно при $\eps\gt\dfrac12$‍‍ и неверно при $\eps\le\dfrac12$‍.‍

Упражнение 4. Докажите аналогичную теорему для «стола» — окружности длины 1, и «салфеток» — дуг этой окружности.

Квадратные салфетки

В 1928 году известный венгерский математик Тибор Радо (Т. Radó) сообщил в письме редактору ведущего польского математического журнала Fundamenta Mathematicae, главе польской математической школы Вацлаву Серпинскому, что не может решить, по-видимому, несложную геометрическую задачу, связанную с теорией функций нескольких переменных. Изложив известные нам соображения и результаты о покрытиях отрезка отрезками, Т. Радо ставит вопрос о получении аналогичных оценок для «двумерной» задачи, в которой «салфетки» — квадраты (разных размеров), а «стол» — скажем, квадрат (или прямоугольник) площади 1, причём края салфеток параллельны краям стола (рис. 3).

Итак, разница между задачей Радо и задачей М321 (Браилова) только в форме «салфеток»: в М321 они могут быть любыми прямоугольниками, а у Радо — только квадратами. Но это «маленькое» различие, как нередко бывает, полностью меняет дело.

Метод, которым мы из системы отрезков, покрывающих отрезок длины 1, выделили подсистему длины не меньше $\dfrac13$‍,‍ работает и в двумерном случае. С его помощью Т. Радо доказал такой факт.

Теорема 2. Из любого покрытия плоского «стола» площади 1 квадратными «салфетками» можно выбрать покрытие неперекрывающимися «салфетками», сумма площадей которых не меньше $\dfrac19$‍.‍

Упражнение 5.

1. Докажите теорему 2.
2. Придумайте пример, показывающий, что в формулировке теоремы 2 нелъзя число $\dfrac19$‍‍ заменить на число $\dfrac14$‍.‍

Таким образом, в задаче Радо (в отличие от задачи Браилова) тоже существует какое-то критическое значение $\eps_0$‍‍ такое, что

при $\eps\gt\eps_0$‍,‍ верно

Утверждение 1. Можно указать пример системы «салфеток» такой, что любая подсистема неперекрывающихся «салфеток» имеет общую площадь меньше $\eps$‍,‍

а для $\eps\lt\eps_0$‍‍ верно

Утверждение 2. Из любой системы «салфеток» можно выбрать подсистему из неперекрывающихся «салфеток» с общей площадью не меньше $\eps$‍.‍

Разумеется, площадь «стола» мы всё время считаем равной 1.

Т. Радо сумел доказать, что для критического значения $\eps_0$‍‍ верны оценки $$ \dfrac19\le\eps_0\le\dfrac14,\tag1 $$ но был уверен, что на самом-то деле $\eps_0=\dfrac14$‍.‍

Доказать это равенство он и предлагал в письме Вацлаву Серпинскому.

Однако сделать это не удалось ни Серпинскому, ни другим математикам, хотя за задачу Радо принимались многие. И лишь 55 лет спустя, в 1973 году, стало ясно, почему. Оказывается, гипотеза Т. Радо просто неверна! В «Бюллетене польской Академии наук» появилась сенсационная заметка венгерского математика М. Айтаи (M. Ajtai), в которой довольно просто показывалось, что квадратами всего двух различных размеров можно так покрыть прямоугольник площади 1, что из них нельзя выбрать непересекающуюся подсистему площади $\dfrac14$‍‍ или больше. Сейчас известно, что $$ \dfrac1{8{,}6}\lt\eps_0\lt\dfrac14;\tag2 $$ левое неравенство явилось результатом последовательных уточнений неравенства (1) Т. Радо, последнее из которых принадлежит ленинградскому геометру В. A. Залгаллеру‍ (по-видимому, оно также не является окончательным, будучи гораздо ближе к «грубому» результату теоремы 2, чем к гипотетической оценке Т. Радо).

Наиболее красиво и просто решается частный случай задачи Радо, — когда все «салфетки» — квадраты одного размера. В этом случае критическое значение $\eps_0$‍‍ оказывается действительно равным $\dfrac14$‍.‍ Этот результат доказал ещё в 1940 году молодой ленинградский математик А. С. Соколин (и позже, независимо от него, многие другие, причём несколькими различными путями).

Теорема Блихфельда и результат Соколина

Докажем сначала такую приятную теорему, одному из вариантов которой была посвящена вторая страница обложки «Кванта», 1973, №10‍.

Теорема Блихфельда. Если площадь фигуры, расположенной на листе клетчатой бумаги, больше $n-1$‍‍ (где $n$‍‍ — целое; сторона клетки принимается за $1$‍),‍ то эту фигуру можно параллельным переносом сдвинуть в такое положение, что она покроет по крайней мере $n$‍‍ узлов сетки. (Узлами называют точки, где пересекаются линии, разбивающие плоскость на квадратные клетки.)

Доказательство. Разрежем лист клетчатой бумаги на отдельные клетки и соберём вместе, в стопку, все те клетки, на которых помещается хотя бы часть фигуры (от рисунка 4, а перейдём к рисунку 4, б). Поскольку сумма площадей кусков нашей фигуры больше $n-1$‍,‍ то некоторые точки в стопке будут покрыты по крайней мере $n$‍‍ кусками фигуры. Проткнём иглой одну из этих точек; на каждом куске останется след от прокола. Если мы теперь расположим клетки, собранные в стопку, на плоскости в прежнем порядке (разумеется, мы считаем, что клетки совмещались параллельным переносом), то проколы будут располагаться «правильным образом» — в вершинах новой сетки квадратов со стороной 1 (рис. 4, в). Остаётся параллельно перенести фигуру так, чтобы эти проколы совместились с узлами (рис. 4, г).

Упражнение 6. Докажите, что если площадь фигуры меньше $n+1$‍,‍ то eё можно перенести так, чтобы она задевала не больше $n$‍‍ узлов сетки ($n$‍‍ — целое число).

С помощью теоремы Блихфельда получается нужный нам результат.

Теорема 3. Если система конгруэнтных квадратов с взаимно параллельными сторонами покрывает фигуру площади $S$‍,‍ то из неё можно выбрать подсистему непересекающихся (не имеющих общих внутренних точек) между собой квадратов, сумма площадей которых не меньше $\dfrac S4$‍.‍

Какую именно фигуру покрывают квадраты, здесь, как, впрочем, и в задаче Радо, не имеет значения. Важна только её площадь.

Доказательство. Мы нарочно сформулировали теорему несколько иначе, чем предыдущие (площадь «стола» теперь $S$‍,‍ а не 1), чтобы иметь возможность выбрать другую единицу длины. Будем считать, что длина стороны каждой «салфетки» равна $\dfrac12$‍.‍ По теореме Блихфельда можно расположить нашу фигуру (площади $S$‍)‍ на клетчатой бумаге (со стороной клетки 1) так, чтобы она покрывала $n\ge S$‍‍ узлов сетки. Оставим по одной «салфетке», покрывающей каждый из этих $n$‍‍ узлов. Ясно, что выбранные «салфетки», не могут налегать друг на друга, а их общая площадь равна $$ \dfrac14n\ge\dfrac S4. $$ Теорема Соколина доказана.

Варианты задачи Радо

Больше всего усилий на задачу Т. Радо затратил другой известный венгерский математик — Р. Радо. В 1950, 1951, 1968 гг. он опубликовал в английских журналах три обширные статьи: «Несколько теорем о покрытиях», I⁠—⁠III, целиком навеянные задачей Т. Радо (так что у нас было основание назвать статью «О задаче Радо», не указывая инициала). Перечислим только некоторые результаты и нерешённые вопросы, связанные с этой задачей.

Для задачи о треугольном «столе» $\mathrm{T}$‍‍ и подобных ему (с соответственно параллельными сторонами) треугольных «салфетках» удалось получить некоторые оценки для $\eps_0$‍;‍ в частности, для покрытия $\mathrm{T}$‍‍ конгруэнтными (и параллельно расположенными) треугольниками (аналог результата Соколина) можно указать критическое значение $\eps_0$‍‍ точно: $\eps_0=\dfrac16$‍.‍ (Разумеется, в этой задаче всегда можно говорить о «столе», имеющем форму правильного треугольника.)

Получены также некоторые оценки для круглых «салфеток» (одинаковых и разных размеров), и для других типов подобных друг другу «салфеток».

Упражнение 7. Докажите, что если все «салфетки» подобны данной фигуре $\Phi$‍‍ (которую они покрывают), то существует $\eps_0\gt0$‍‍ такое, что из любого покрытия «стола» площади 1 можно выделить подсистему неперекрывающихся «салфеток» с общей площадью не меньше $\eps_0$‍‍ ($\eps_0$‍,‍ конечно, зависит от формы $\Phi$‍).‍

Таким образом, здесь критическое значение $\eps_0$‍‍ всегда положительно, — в отличие от задачи Браилова, в которой $\eps_0=0$‍‍ (там «салфетки» — прямоугольники, не обязательно подобные друг другу!).

Рассматривались и другие обобщения задачи Радо, например: какую наибольшую суммарную площадь может иметь общая площадь двух подсистем, в каждой из которых «салфетки» не налегают друг на друга; каковы оценки для пространственных аналогов задачи Радо — но во всех этих направлениях получены лишь частичные результаты и довольно грубые оценки.

Упражнение 8.

1. Докажите для пространственного аналога задачи Радо (о покрытии куба кубами) неравенства $$ \dfrac1{27}\lt\eps_0\le\dfrac18.\tag3 $$
2. Сформулируйте и докажите для этого случая аналог теоремы 3.

Ряд задач, близких к задаче Радо (в том числе и предложенных выше в качестве упражнений), вместе с их решениями, вы можете найти в последних выпусках серии «Библиотека математического кружка» и «Библиотечка физико-математической школы»:

Д. О. Шклярский и др., «Геометрические оценки и задачи из комбинаторной геометрии», М., Наука, 1974, цикл задач 3;

Н. Б. Васильев и др., «Математические соревнования; геометрия», М., Наука, 1974, задачи 7.6⁠—⁠7.9.