О задаче Радо

Квант 1975, №8 с. 40-45 Тег OZQ8

О задаче Радо

В «Кванте» №5 за 1975 год в разделе «Задачник „Кванта“» была опубликована задача М321 (автор А. В. Браилов). Напомним её условие.

Имеется прямоугольный стол площади 1. Докажите, что для любого $\eps\gt0$ можно указать систему прямоугольных салфеток, покрывающих этот стол (края салфеток параллельны краям стола), такую, что любая её подсистема, состоящая из неперекрывающихся салфеток, имеет площадь меньшую $\eps$ .

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

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

Мы начнём с ещё более примитивного, чем у водомерок, внешнего мира: с одномерного аналога задачи М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)$ .

Рис. 1

Рис. 2

Пусть дана какая-то система отрезков $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.

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

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

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

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

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

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

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

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

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

Рис. 3

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

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

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

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

Докажите теорему 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, г).

Рис. 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.

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

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

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

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