WWW.DISSERS.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА

   Добро пожаловать!


Pages:     | 1 || 3 | 4 |   ...   | 7 |

Во-первых, нетрудно убедиться в том, что f(2)3. Проще всего Эта лемма, если пытаться доказывать её строго, не вполне рассмотреть для этого вершины произвольного правильного тре- тривиальна. Однако в максимально доступной форме её доказательугольника. Диаметр такого множества — это расстояние между ство изложено в замечательной старой книжке В. Г. Болтянского любыми двумя из его элементов, так что, как наше множество и И. Ц. Гохберга <Теоремы и задачи комбинаторной геометрии> на две части ни разбивай, а в одну из них заведомо попадут (см. [2]). Разумеется, мы не станем повторять эти рассуждения, по крайней мере две вершины, которые диаметрально противопо- а попросту отошлём читателя к упомянутому источнику.

ложны. Ясно, что и весь треугольник тем более нельзя разбить Универсальная покрышка Пала изображена на рис. 4. Сразу на две <меньших> части. Дополнительный важный пример, по- же очевидно, что её диаметр отнюдь единице не равен. Тем не меказывающий, что f(2)3, представляет собой круг. На рис. 3 нее, легко сосчитать диаметры указанных на том же рисунке трёх изображено <оптимальное> разбиение круга на части меньшего частей и проверить, что они равны 3/2=0,866...<1. Таким обрадиаметра. Оно напоминает значок <Мерседеса>, и если считать, как зом, всё в порядке, и мы доказали, что f(2)3.

обычно, что круг имеет единичный диаметр, то окажется, что диа- Здесь следует сделать несколько замечаний. Во-первых, мы метры (одинаковых) частей в разбиении равны 3/2=0,866...<1. опять-таки (см. конец предыдущей главы) доказали даже больше, Этот факт нам ещё понадобится. чем от нас требовал Борсук. В самом деле, мы знаем, с одной Значительно тоньше выглядит ситуация с обратной оценкой. стороны, что всякое двумерное множество диаметра 1 допускает Дело в том, что f(2)3, а стало быть, и вовсе имеет место равен- разбиение на три части, у которых диаметры не превосходят 3/2.

ство f(2)=3, дающее полное решение проблемы Борсука на плоско- С другой стороны, существует множество — круг, — для котости. Как это доказать Нужно воспользоваться идеей, аналогичной рого последнее утверждение усилить нельзя в том смысле, что, той, к помощи которой мы прибегли в случае прямой. А именно, как круг на три <дольки> ни разрезай, а всё равно хотя бы следует придумать какую-нибудь двумерную фигуру, покрываю- одна из долек будет иметь диаметр не меньше 3/2 (значок щую в некотором смысле любое другое плоское множество (диаме- <Мерседеса> оптимален). Напомним, что аналогом <критической> тра 1) и допускающую в то же время несложное разбиение на три величины 3/2 на прямой было число 1/2. Далее, стоит подчеркчасти с диаметрами, меньшими единицы. Понятно, что, коль ско- нуть, что наука о построении универсальных покрышек (даже ро такую фигуру мы разбили, покрытое ею множество разбито на плоскости) весьма обширна и мнои подавно. Введём точное определение. гогранна. В разделе задач мы кое-что Определение. Множество U n при n3 в подобном роде предложим читателю для называется универсальной покрышкой для мно- самостоятельного изучения. Однако тут жеств диаметра 1, если для каждого множест- мы в соответствующие дебри забираться ва A с diam A =1 найдётся такое движение, не станем. Наконец, заметим, что именно что A (U). Борсук был первым, кто провел все тольПо-другому говоря, U — это универсальная ко что описанные нами выкладки.

покрышка, если та или иная её <жёсткая> копия, Любопытно рассмотреть отдельно один полученная в результате движения, целиком со- важный частный случай задачи, а именно держит произвольно заданное множество. Ясно, тот случай, когда нас интересуют тольРис. Рис. что к чему-то такому мы и стремились. Заметим, ко конечные множества. Иными слова8 ми, мы хотим показать, что каждое конечное множество точек содержит также некоторый отрезок xjxp, то он xj xi xk на плоскости может быть разбито на 3 части меньшего диаметра. должен пересекаться как с отрезком x1xi, так Разумеется, этот факт является прямым следствием уже доказан- и с отрезком x1xk, ибо у всяких двух непере ного неравенства f(2)3. Однако его можно установить и за счёт секающихся единичных отрезков найдётся пара совершенно других средств: если до сих пор мы мыслили исключи- вершин, отстоящих друг от друга на расстояние, тельно в геометрических терминах (универсальные покрышки), то большее единицы. Поэтому точка xp должна со тут нам удастся в существенной мере отойти от геометрии и пе- впадать с точкой x1. Таким образом, из точки xj x реключиться на комбинаторику. С одной стороны, нам станет выходит лишь один отрезок. Если мы исключим яснее, тем самым, смысл выражения <комбинаторная геометрия>, из A точку xj, то в оставшемся множестве бу Рис. а с другой стороны, мы самостоятельно (без каких-либо ссылок) дет m-1 точка, и по предположению индукции придём к весьма нетривиальному результату. Итак, справедлива в нём найдётся не более m-1 пары диаметрально противоположследующая теорема, которую в 1946 году доказал выдающийся ных точек. Присоединив к этой m-1 паре точки x1 и xj, мы венгерский математик П. Эрдеш*): получим как раз утверждение леммы.

Теорема. Всякое конечное множество точек на плоскости мо- Сейчас мы готовы завершить доказательство теоремы, и здесь жет быть разбито на три части меньшего диаметра. мы снова прибегнем к помощи индукции. В самом деле, пусть A — Заметим сперва, что с конечными множествами куда приятнее произвольное множество, состоящее из m двумерных точек и имеработать, чем с произвольными: и что они из себя представляют, ющее диаметр 1. Если m3, то проблем с разбиением A на три и как измерить их диаметры, понять ничего не стоит. Перейдём части меньшего диаметра нет, и основание индукции нам обеспетеперь к доказательству. чено. Предположим, что m>3 и для всех A, содержащих ровно Доказательство. Зафиксируем произвольное конечное множе- m-1 точку, теорема доказана. Поймём, почему и для m-элементство точек x1,..., xm 2 и будем считать, что ных A искомое разбиение найдётся. Как и при доказательстве леммы, каждой паре диаметрально противоположных точек в A diam {x1,..., xm}=1.

мы сопоставим соединяющий эти точки отрезок длины 1. Если Докажем лемму. допустить, что из всякой точки в A выходит не менее трёх отЛемма. Число пар точек, реализующих диаметр множества резков, то всего различных отрезков у нас окажется как минимум A ={x1,..., xm}, не превосходит m. 3m/2, что невозможно ввиду леммы. Значит, есть точка xA, Доказательство. Будем действовать с помощью математиче- из которой выходит не более двух отрезков. Если мы удалим точской индукции. В самом деле, если m3, то наше утверждение ку x из A, то в полученном множестве A {x} останется m- очевидно, и мы имеем основание индукции. Предположим те- точка. По предположению индукции последнее множество допусперь, что m>3 и для всех множеств A, состоящих из m-1 кает разбиение на три части меньшего диаметра. Возьмём ту из точки, утверждение леммы доказано. Убедимся в том, что и для этих частей, в которую не попадает вторым своим концом ни один m-элементных множеств A всё в порядке. Каждым двум точкам из отрезков, выходящих из точки x. Ясно, что если мы добавим xi, xkA, удалённым друг от друга на расстояние 1, поставим x к этой части, то возникнет разбиение множества A, в котором в соответствие соединяющий их отрезок. Если из каждой точ- диаметры частей опять-таки меньше единицы. Теорема доказана.

ки выходит не более чем два отрезка, то общее число отрезков 6. Докажите, что круг радиуса 1/ 3 является универсальной не превосходит m и лемма доказана. Пусть, напротив, есть точ- покрышкой для множеств диаметра 1 в 2.

ка — скажем, x1, — из которой выходит по меньшей мере три 7. Убедитесь в том, что покрышка из задачи 6 не позволяет отрезка (см. рис. 5). Назовём их x1xi, x1xj и x1xk. Два <край- решить проблему Борсука на плоскости.

них> из этих отрезков — скажем, x1xi и x1xk — образуют угол 8. Рассмотрим круг B1 радиуса 1/ 3 и зафиксируем на ограни не больше 60 градусов, так как |xi-xk||xi-x1|=|xk-x1|=1. Это- чивающей его окружности произвольную точку. Пусть B2 — это му углу принадлежит отрезок x1xj. Если наша система отрезков круг радиуса 1 с центром в нашей точке. Докажите, что B1B (см. рис. 6) — это универсальная покрышка. Постройте её раз*) Пол Эрдеш (1913—1996) — выдающийся венгерский математик. Он является биение на 3 части с диаметрами меньше единицы. Постарайтесь одним из основателей современной математической школы в Венгрии. Им написано добиться того, чтобы диаметры частей были как можно меньше.

более полутора тысяч статей и книг, а также предложены десятки задач, многие из которых стали уже классическими. Чему они будут равны 10 9. Не ссылаясь на лемму Пала, докажите, что всякий многоугольник на плоскости может быть разбит на три части меньшего диаметра.

10. Придумайте универсальную покрышку для множеств диаметра 1 на плоскости, которая имела бы как можно меньшую площадь.

5. ПРОБЛЕМА БОРСУКА В Сейчас речь пойдёт, собственно, о <пространстве> — в том обыден1 ном смысле, в каком мы привыкли это слово понимать. Число измерений увеличивается ещё на единицу, геометрия становится богаче, и, разумеется, возникают новые тонкости, которых ни в случае прямой, ни в случае плоскости не было.

Рис. Тот факт, что f(3)4, вытекает из рассмотрения множества вершин правильного тетраэдра. Ясно, что здесь всё устроено так же просто, как то было и для пары тоРис. 7, а) чек на прямой, и для тройки вершин правильного треугольника на плоскости. Однако в случае плоскости мы приводили дополнительно важный пример круга, который позволял установить оценку f(2)3. Разумно, стало быть, обсудить аналогичный пример и в пространстве. Понятно, что имеется в виду шар.

Сперва убедимся в том, что шар (обозначим его B) разбивается на четыре части меньшего диаметра. Пусть диаметр самого шара, как обычно, равен 1. Впишем в B правильный тетраэдр A1A2A3A4.

Считая, что O — это центр шара, рассмотрим трёхгранные углы U1, U2, U3, U4, выходящие из O и порождённые тетраэдрами OA1A2A3, OA1A2A4, OA1A3A4, OA2A3A4.

Положим B1=BU1, B2=BU2, B3=BU3, B4=BU4.

Очевидно, B=B1B2B3B4 (см. рис. 7). Нетрудно проверить (сделайте это самостоятельно), что 3+ diam Bi= =0,888...<1, i=1,..., 4.

Теперь следует заметить, что сам Борсук ещё в 1932 году до- Рис. 7, б) казал, используя весьма нетривиальные соображения, что на три части меньшего диаметра шар разбить нельзя. Более того, разбиение, которое мы только что описали, оптимально, т. е. добиться 12 разбиения шара на четыре части, каждая из которых имела бы диаметр, меньший, чем 0,888..., уже не удастся. Соображения, A5 Aприменённые Борсуком, в максимально доступной форме изложены в книжке [2]. Отметим, что разбиение B=B1B2B3B4 очень BBBBBBBBBBBBBBBBBBBB BBB BB BB BB BB BB BB B22 BBB B BB BB BB BB BB BB BB BB BB BBBBBBBBBBBBBBBBBпохоже на соответствующее разбиение круга: ведь и там <значок BМерседеса> получался из правильного вписанного треугольника, BBBBBBBBBBBBBBBBBBB BB BB BB BB BB BB B BBB BBB B BB BB BB BB BB BB BB BB BB BB BBBBBBBBBBBBBBBA2 Aявляющегося плоским аналогом правильного тетраэдра.

A3 AЧто же, далее, можно сказать о верхних оценках для f(3) Иными словами, можем ли мы, например, утверждать, что A1 AA4 Af(3)=4 Если проводить аналогию с одномерным и плоским случаями, то в последнее равенство хочется верить, ведь и раньше мы имели f(n)=n+1. Ответ на поставленный вопрос положителен. Первым, кто доказал неравенство f(3)4, был английский математик Х. Эгглстон. К сожалению, метод Эгглстона не был A6 Aэлементарным, и, в частности, на построение каких-либо универсальных покрышек он не опирался. Как следствие, и результат Рис. 8 Рис. получился не совсем удовлетворительным. Конечно, проблема Борсука была решена, ведь для каждого A 3, имеющего диаAметр 1, нашлось разбиение на такие четыре части A1,..., A4, что diam Ai<1 для любого i. Тем не менее при n2 удавалось <перевыполнить план>: на прямой оказывалось, что в аналогичном разбиении diam Ai<1/2, а на плоскости подобная оценка имела BBBBBBBBBBBBBBBBBBB BB BB BB BB BB BB B22 BB BB BBB B BB BB BB BB BB BB BB BB BB BB BBBBBBBBBBBBBBBвид diam Ai< 3/2=0,866.... Обе оценки были значительно точнее неравенства diam Ai<1, причём потом ещё выяснялось, что B числа 1/2 и 3/2 в известном смысле неулучшаемы.

BBBBBBBBBBBBBBBBBBB BB BB BB BB BB BB BB BB BBB B BB BB BB BB BB BB BB BB BB BB BBBBBBBBBBBBBBBРезультат Эгглстона был опубликован в 1955 году, а два года C2 Dспустя два замечательных геометра — А. Хеппеш и Б. Грюнбаум — Aнезависимо друг от друга предложили вполне элементарный подAход к решению трёхмерной задачи. Естественно, и Хеппеш, CCCCCCCCCCCCCCCCCCC CC CC C CCC CC CC CC CC C CC CC CC CC CC CC и Грюнбаум исходили из построения некоторой универсальной CCC CC CC CC CC CCCCCCCCCCCCCCCDDDDDDDDDDDDDDDDDDD DD покрышки. По-видимому, идея <витала в воздухе>, так как Хеп- DDD DD DD DD D DD DD DDD D D D D D D D D D D D DDDDDDDDDDDDDD1 AD1 AD1 A4 DD1 AD1 AD1 A4 DD1 A4 DD1 AD1 AD1 AD1 AD1 AD1 A4 DD1 AD1 AD11 AD1 A D11 A44 DD A D11 A44 DD A D11 A44 DD A D11 A44 DD AD11 A44 DD A D11 A44 DD A D11 A44 DD A A D11 AD A A D11 AD A D11 AD1 AD A D A A A A D11 AD A A D11 A44 DD A D AA D AD AD AA D AD AD AAAAAAAAAAAAAAAAAпеш и Грюнбаум, не сговариваясь, рассмотрели одну и ту же C3 DC3 DC3 DC3 DC3 DC3 DC3 DC3 DC3 DC3 DC3 DC3 DC3 DC3 DC3 DC33 DC3 D C33 DC C33 DC C33 DC C33 DC C33 DC C33 DC C33 DC C CC A1 CCCC C CC CC CC CC CC CC CC CC CC CCCCCCCCCCCCCCCCCпокрышку. Устроена эта покрышка так. Сначала берётся правильный октаэдр A1A2A3A4A5A6, у которого расстояние между любыми двумя параллельными гранями равно 1 (см. рис. 8). Затем плосDDDDDDDDDDDDDDDDDDD DD DD DD DD DD DD DD D DDD D DD DD DD DD костью, параллельной четырёхугольнику A1A2A3A4 и проходящей DDD DD DD DD DD DD DDDDDDDDDDDDDDDCна расстоянии 1/2 от него (в направлении вершины A5), от октаэдра отсекается пирамида B1B2B3B4A5 (см. рис. 9). Точно так же от него отсекаются ещё две пирамиды — C1C2C3C4A1 и D1D2D3D4A(см. рис. 10). Можно доказать, что <жёсткие копии> многогранника U, получающегося в итоге, действительно покрывают любое Aнаперёд заданное множество диаметра 1 в пространстве. Мы этого делать не станем, сославшись на книжку [2].

Рис. Заметим, что, во-первых, diam U>1. Во-вторых, теперь нас должно интересовать наиболее экономное разбиение U на четыре 14 части диаметра меньше единицы. Хеппеш действовал немного грубее Грюнбаума. В результате у него диаметры частей оказались равны 9+4 =0,99775..., а у Грюнбаума — 6129030-937419 =0,9887....

1518 Последнее число не может не впечатлять: ведь ясно, какую огромную и скрупулёзную вычислительную работу пришлось проделать Грюнбауму, дабы отыскать его. Расчёты Грюнбаума также подробно изложены в книге [2], и мы на них не останавливаемся. Тем не менее, мы всё же приводим здесь рисунки (см. рис. 11), на которых изображено разбиение Грюнбаума.

Что же мы, таким образом, имеем С одной стороны, благодаря Грюнбауму, мы знаем, что всякое трёхмерное множество диаметра 1 может быть разбито на четыре части диаметра н е б о л ь ш е 0,9887.... С другой стороны, у нас есть шар, в любом разбиении которого на четыре части непременно найдётся часть диаметра н е м е н ь ш е 0,888.... Числа 0,9887 и 0,888, конечно, довольно далеки (в масштабах единицы) друг от друга, и, стало быть, в всё уже не так безоблачно, как то было на плоскости и на прямой.

Естественно, возникает новая нетривиальная геометрическая задача отыскания правильного числа [0,888..., 0,9887...], отвечающего за <оптимальность> решения исходной проблемы Борсука.

Понятно, что для улучшения верхней оценки на (коль скоро это вообще возможно) необходимо придумать как можно более экономное разбиение произвольного множества на четыре части. Для улучшения же нижней оценки (опять-таки при условии, что оно принципиально возможно) следует придумать множество, не допускающее никакого разбиения на четыре части, каждая из которых имела бы заданный наперёд диаметр, не больший 0,888.... В Рис. 11, а) году американский математик Д. Гэйл высказал гипотезу, что = =0,888..., т. е. что множеств <хуже> шара в определённом смысле в пространстве не бывает. Эта гипотеза до сих пор не доказана и не опровергнута (см. задачи). Однако кое-какие интересные результаты были достигнуты в борьбе с неравенством 0,9887.

Pages:     | 1 || 3 | 4 |   ...   | 7 |






















© 2011 www.dissers.ru - «Бесплатная электронная библиотека»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.