Документ взят из кэша поисковой машины. Адрес оригинального документа : http://kvant.mccme.ru/pdf/1998/04/17.pdf Дата изменения: Fri Dec 23 19:24:40 2005 Дата индексирования: Tue Oct 2 00:09:24 2012 Кодировка: Windows-1251

Покрытия полосками
ПОКРЫТИЯ ПОЛОСКАМИ

17

М.СМУРОВ, А.СПИВАК
Полоса часть плоскости, заключенная между двумя параллельными прямыми.

Н

А МОСКОВСКОЙ олимпиаде 1997 года одиннадцатиклассники решали задачу, вошедшую в 'Задачник 'Кванта': М1600. На плоскости даны: конечное число полос, сумма ширин которых равна 100, и круг радиусом 1. Докажите, что каждую из полос можно параллельно перенести так, чтобы все они вместе покрыли круг. С ней справился только один из 410 участвовавших в олимпиаде одиннадцатиклассников. Между тем при обсуждении варианта многие члены жюри, даже не желая слушать условие до конца, заявляли, что задача им известна. Они путали М1600 со знаменитой задачей, о которой будет рассказано во второй части статьи. Число 100 играло в условии роль 'большого числа'. Мы докажем, что достаточно меньшей суммарной ширины полос, равной + 2. В то же время, 100 нельзя заменить

ни на какое число, меньшее . Чтобы доказать это, впишем в круг с радиусом 1 правильный 2n-угольник. Че-

полосы (т.е. уменьшить их ширины), то никакими их сдвигами рассматриваемый 2n-угольник не покроешь. Впрочем, основное содержание статьи рассказ о некоторых трудных и интересных проблемах комбинаторной геометрии. Их формулировки привлекательны и просты. Но на многие вопросы еще нет ответа.

Что такое ширина?
Ширина по направлению Начнем с простой ситуации. Пусть даны фигура F и одна полоса (рис.2). Можно ли полосу параллельно перенести ('сдвинуть') так, чтобы накрыть F? Разумеется, некоторые фигуры (например, угол) вообще не помещаются ни в какую полосу. Поэтому дальше будем предполагать, что фигура F является ограниченной, т.е. содержится в некотором круге. Для таких

Рис. 1

рез концы каждой его стороны проведем перпендикулярные ей прямые (рис. 1). Получим n полос. Сумма их ширин равна половине периметра 2n-угольника. Она стремится к при возрастании n. Во второй части статьи мы докажем, что если сузить

Иллюстрация М.Константиновой
5 Квант ? 4