WWW.DISSERS.RU

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

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


Pages:     || 2 | 3 | 4 | 5 |   ...   | 7 |
Библиотека НАМ МАГАЗИН <МАТЕМАТИЧЕСКАЯ КНИГА> В МЦНМО 5 ЛЕТ <Математическое просвещение> В магазине представлен наиболее полный ассортимент книг издательства МЦНМО. Эти книги продаются по издательским ценам. Здесь также можно найти книги по математике ведущих издательств Физматлит, Факториал, УРСС, Мир, РХД, А. М. Райгородский Лань, Просвещение, АСТ, Бином ЛЗ и др.

В отделе школьной литературы представлен широкий ассортимент книг для школьников, учителей, руководителей математических кружков.

ПРОБЛЕМА БОРСУКА В отделе вузовской и научной литературы можно найти учебники и научные монографии ведущих российских и зарубежных математиков. В магазине также имеется отдел <книга—почтой>.

Магазин работает ежедневно кроме воскресенья (летом — кроме субботы и воскресенья) с 1130 до 2000. Перерывы с 1330 до 1350 и с 1630 до 1650.

Адрес магазина: 119002, Москва, Бол. Власьевский пер., 11. Проезд: ст. м. <Смоленская> или <Кропоткинская>, далее пешком (см. схему).

ISBN 5 94057 249 9 Телефон: (495) 241–72–85 Издательство Московского центра E-mail: biblio@mccme.ru непрерывного математического образования 9 785940 572497 http://biblio.mccme.ru/ Москва • 2006 О М ЦН М В > А Г И Н К Я А К С Е Ч И Т А М Е Т А М < Н И З А Г А М М А Н а ек т ио л иб Б Библиотека <Математическое просвещение> Выпуск 33 А. М. Райгородский Н а у ч н о - р е д а к ц и о н н ы й с о в е т с е р и и:

В. В. Прасолов, А. Б. Сосинский (гл. ред.), А. В. Спивак, В. М. Тихомиров, И. В. Ященко ПРОБЛЕМА БОРСУКА Серия основана в 1999 году Издательство Московского центра непрерывного математического образования Москва • 2006 УДК 519.1+514.174 1. ВВЕДЕНИЕ ББК 22.135 Р12 В этой брошюре мы бы хотели познакомить читателя с одной из наиболее известных, красивых и интригующих задач совреАннотация менной комбинаторной геометрии. Эта задача была предложена в 1933 году замечательным польским математиком Каролем БорБрошюра написана по материалам лекции, прочитанной автором 4 декабря 2004 года на Малом мехмате МГУ для школьников суком*), и за прошедшие 70 лет она сделалась едва ли не самой 9—11 классов. В ней рассказывается об одной из знаменитых задач популярной в своей области. Собственно говоря, комбинаторная комбинаторной геометрии — гипотезе Борсука, которая утверждает, что в n-мерном пространстве всякое ограниченное множество можно геометрия как раз и сформировалась на основе таких ярких задач, разбить на n+1 часть меньшего диаметра. Вначале подробно анализикак задача о хроматическом числе или, скажем, задача Хелли.

руются случаи малых размерностей и доказывается, что при n=1, 2, И, разумеется, проблема Борсука сыграла в процессе формировагипотеза верна. Далее приводятся различные оценки сверху для числа Борсука в зависимости от размерности. Кроме того, рассматривается ния данного раздела математики одну из главных ролей. Именно связь гипотезы с другими проблемами и задачами комбинаторной геопоэтому мы не станем обсуждать здесь сам термин <комбинаторная метрии (проблема освещения, задача Грюнбаума, задача о хроматичегеометрия>, тем более что мы уже достаточно подробно комментиском числе). В заключительных главах рассматриваются контрпримеры к гипотезе Борсука и история понижения минимальной размерности, ровали его в брошюре <Хроматические числа> (см. [1]). Заметим в которой строится контрпример, а также улучшения оценки снизу.

только, что и геометрия, и комбинаторика будут сопутствовать Многие главы снабжены задачами. Некоторые из них — это упражнения, прорешав которые, читатель лучше прочувствует матери- нам на протяжении всего повествования, а стало быть, в конечном ал. На некоторые задачи опирается основной текст. Сложные задачи счёте и комментарии окажутся излишними.

отмечены звёздочками (некоторые являются открытыми проблемами).

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

числе. Обо всём этом нам предстоит постепенно узнать, но в своё Андрей Михайлович Райгородский время. Сперва нам следует понять, в чём же состоит вопрос БорсуПроблема Борсука ка — вопрос, которому суждено было оказать столь существенное (Серия: <Библиотека,,Математическое просвещение“>) влияние на развитие современной науки.

М.: МЦНМО, 2006. — 56 с.: ил.

Редакторы Д. Вельтищев, Т. Караваева, Ю. Кузнецова, М. Вельтищев Рисунки выполнил Д. Вельтищев Техн. редактор М. Вельтищев 2. ПОСТАНОВКА ПРОБЛЕМЫ БОРСУКА НА ПРЯМОЙ, НА ПЛОСКОСТИ И В ПРОСТРАНСТВЕ Лицензия ИД № 01335 от 24/III 2000 года. Подписано в печать 21/VII 2006 года.

Формат бумаги 6088 /. Офсетная бумага № 1. Офсетная печать. Физ. печ. л. 3,5.

Мы поступим следующим образом: сначала сформулируем заТираж 2000 экз. Заказ.

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

Брошюра соответствует гигиеническим требованиям к учебным изданиям для общего и начального профессионального образования (заключение государственной санитарноэпидемиологической службы Российской Федерации № 77.99.02.953.Д.003873.06.Проблема Борсука. Найти минимальное число частей меньот 2/VI 2004 года).



шего диаметра, на которые может быть разбито произвольное ограниченное множество в пространстве.

Издательство Московского центра непрерывного математического образования.

119002, Москва, Бол. Власьевский пер., 11. Тел. (495) 241-72-85, (495) 241-05-00.

По-видимому, наиболее непонятным кажется слово <диаметр>, применённое не к кругу или шару, а к произвольному множеству.

Отпечатано с готовых диапозитивов в ФГУП <Производственно-издательский комбинат ВИНИТИ>. Однако на самом деле неясностей гораздо больше, так что обо всём 140010, г. Люберцы Московской обл., Октябрьский пр-т, 403. Тел. 554-21-86.

по порядку.

*) Кароль Борсук (8 мая 1905 г. — 24 января 1982 г.) — выдающийся польский ISBN 5-94057-249-9 © Райгородский А. М., 2005.

математик. Ему принадлежат многочисленные результаты по топологии, дифференциальной геометрии и пр. Его именем даже названа улица в Варшаве.

© МЦНМО, 2006.

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

Но и на этом пути сразу же возникает недоразумение. Действи- Взамен мы предложим читателю представлять себе те множества, тельно, кто ж из нас не знает, что такое пространство Достаточно какие он сам посчитает возможным. Без сомнения, этого уже хвапоглядеть вокруг себя. Тонкость в том, что математика, будучи тит с запасом, ведь, как мы увидим позже, даже с конечными наукой, безусловно, живой, тем не менее зачастую использует тер- наборами векторов возиться весьма и весьма непросто.

мины, знакомые нам из повседневной жизни, для обозначения тех Теперь об ограниченности множеств. Пусть n3. Множество объектов, которые мы либо привыкли называть по-другому, либо A n называется ограниченным, если существует отрезок (при и вовсе не встречали. В этом состоит элемент абстракции, прису- n=1), круг (при n=2) или шар (при n=3), целиком содержащий щий математике. В нашем случае всё совсем не страшно: просто множество A.

мы называем пространством, в зависимости от контекста, не толь- Наконец, очередь дошла и до диаметра. Естественно, дабы ко трёхмерное пространство, в котором мы живём, но и плоскость, определить его, мы должны уметь измерять расстояния. Соответи прямую. Это разумно, поскольку вполне можно представить се- ствующие формулы всем хорошо известны:

бе, например, существо, которое всю жизнь ползает по плоскости |x-y|= (x1-y1)2+(x2-y2)2, и третьего измерения видеть не способно. Для него и плоскость — пространство. При этом, как мы хорошо понимаем, наше пространколь скоро x=(x1, x2), y=(y1, y2) 2, и ство трёхмерно, пространство упомянутого существа двумерно, а на прямой только одно измерение. Таким образом (по числу из|x-y|= (x1-y1)2+(x2-y2)2+(x3-y3) мерений) мы пространства и отличаем.

Будем обозначать прямую через = 1, плоскость — через 2, в аналогичных обозначениях для x, y 3. На прямой всё совсем а трёхмерное пространство — через 3. Проще всего мыслить об просто.

этих объектах так: — это множество всевозможных веществен- Зафиксируем произвольное ограниченное множество A n ных (действительных) чисел, 2 — это множество пар x=(x1, x2) при n3. Будем перебирать всевозможные пары точек x, yA чисел x1, x2, а 3 — множество троек x=(x1, x2, x3), где и измерять расстояния между ними. Получится некоторый (не x1, x2, x3. Ясно, что пары из 2 и тройки из 3 — это то, что исключено, что бесконечный) набор чисел. Нам бы х о т е л о с ь мы называем векторами или точками в соответствующих про- найти в нём максимальный элемент и назвать его диаметром странствах. В свою очередь, элементы пар и троек (числа x1, x2, x3) множества A. В самом деле, такое определение диаметра вполсуть координаты наших векторов. не коррелировало бы с общеизвестным: и для круга, и для шара Далее, а что такое п р о и з в о л ь н о е множество в простран- диаметр — это расстояние между максимально удалёнными друг стве Конечно, каждый из нас может вообразить себе уйму разных от друга точками. К сожалению, всё не так легко. Представим семножеств. Скажем, это могут быть и конечные наборы точек, бе, что A =(a, b) — это обычный интервал. Рассмотрим в нём и какие-нибудь фигуры (если речь идёт о двумерном пространстве) пары точек вида a+1/k, b-1/k. Понятно, что с увеличением k или тела (если мы говорим о трёхмерье), и многое, многое другое расстояние между точками становится всё ближе и ближе к b-a.

(см. рис. 1). Однако в A н е т точек, расстояние между которыми в точности равнялось бы b-a. Стало быть, искомый максимум не существует.

Если знать теорию пределов, то трудность ничего не стоит преодолеть, заменяя максимум на так называемый супремум (точную верхнюю грань). Мы не станем вдаваться здесь в подобные детали. С одной стороны, как правило, и без того ясно, чем заменить максимум, коль скоро его найти не удалось (скажем, для интервала диаметр — это всё равно его длина), а с другой стороны, можно опять-таки ограничиться изучением только тех множеств, для коРис. 1 торых такой проблемы нет (см. задачи).





4 Итак, диаметр множества — это, говоря не совсем строго, 3. ПРОБЛЕМА БОРСУКА НА ПРЯМОЙ расстояние между наиболее удалёнными его точками. Понятно, Сейчас мы попробуем разобраться с тем, как поэкономнее что у ограниченного множества диаметр всегда конечен. Будем разбивать на части меньшего диаметра одномерные множества.

обозначать диаметр множества A через diam A.

Иными словами, мы постараемся определить значение f(1).

Вернёмся к проблеме Борсука и попробуем проинтерпретироДля начала заметим, что неравенство f(1)2 практически очевать её с учётом накопленной информации. Пусть дано какое-то видно. В самом деле, нелепо же пытаться разбить какое-либо множество A n, где n3. Попытаемся представить A в виде множество на о д н у часть меньшего диаметра. Это то, что принято называть , т. е. противоречие внутри A =A1...Af, определения. Мы, однако, утверждаем большее, а именно: f(1)2, так что в конечном счёте f(1)=2. Если мы наше утверждение допредполагая, что diam Ai

значим через f(A ) минимум среди всех f, для которых такое Рассмотрим произвольное (ограниченное) множество A в.

представление имеет место. Понятно, что f(A ) — это и есть Мы ничего, по сути, не потеряем, если будем полагать diam A =минимальное число частей меньшего диаметра, на которые мо(см. задачу 4 из предыдущей главы). Возьмём в множестве A жет быть разбито*) множество A. Определим f(n) как максимум <крайнюю левую> и <крайнюю правую> точки. Конечно, кавычпо всем A n величин f(A ). В свою очередь, на f(n) частей ки не случайны, ведь, как мы уже знаем, такие точки вовсе меньшего диаметра разбивается уже произвольное ограниченное не обязаны существовать. Например, если речь идёт об интервамножество в n-мерном пространстве, причём существует такое мноле (a, b), то мы возвращаемся к ситуации, когда точки a+1/k жество в n, которое нельзя разбить на f(n)-1 часть. Таким и b-1/k с увеличением k становятся всё ближе и ближе к <краобразом, проблема Борсука состоит в отыскании числа f(n).

ям>, краёв этих ни при каких условиях не достигая. Интуитивно 1. Является ли ограниченным множество всех целых чисел смысл <крайних точек> понятен, а для строгости нужно опять-тана прямой ки сослаться на теорию пределов: там роль <крайне левого> будет 2. Найдите диаметры множеств, изображенных на рис. 2.

играть инфимум (точная нижняя грань), а <крайне правого> — супремум (точная верхняя грань). Итак, пусть найденные нами точки суть a и b. Ясно, что они <диаметрально противоположны>, т. е. что на них-то как раз и достигается диаметр A, равный едиb нице. Таким образом, b-a=1. С другой стороны, отрезок [a, b], безусловно, содержит внутри себя множество A или, как ещё гоa ворят, покрывает это множество. Рассмотрим разбиение Рис. a+b a+b b 3. Разбейте множества с рис. 2 на части меньшего диаметра.

[a, b]= a,,.

2 Постарайтесь сделать это максимально экономно.

4. Докажите, что величина f(n) не изменится, если вместо Разумеется, диаметр каждой из частей в данном разбиении отрезка произвольных ограниченных множеств разбивать произвольные 1 a+b A, а A2= a+b, b A, равен. Более того, если A1= a, множества фиксированного диаметра — например, диаметра 1. 2 2 5. Множество в n называется выпуклым, если вместе с любыто A =A1A2 и diam Ai1/2. В результате f(A )2, а значит, ми двумя своими точками оно целиком содержит соединяющий то же верно и для f(1).

их отрезок. Докажите, что величина f(n) не изменится, если Отметим, что мы доказали даже чуть больше, чем требовавместо произвольных ограниченных множеств разбивать произлось. Ведь мы не просто знаем, что каждое множество диаметра вольные ограниченные выпуклые множества.

на прямой разбивается на части абы какого меньшего диаметра;

мы знаем сверх того, что оно разбивается на части в д в о е мень*) Вообще говоря, для пущей корректности следовало бы потребовать, чтобы шего диаметра. В данном отношении дальнейшего усиления нам множества Ai попарно не пересекались. Иначе не совсем правильно употреблять не добиться. Иначе говоря, слово <вдвое> ничем лучшим мы не заслово <разбиение>. Однако несложно проверить, что упомянутое дополнительное требование никак не влияет на f(A ). меним: ни <втрое>, ни <в 2,1 раза>, ни <в 2,0001 раза> и т. д. нам 6 не подойдёт. Достаточно взять отрезок [0, 1] и убедиться в том, между прочим, что диаметр универсальной покрышки уже вовсе не что, как его ни разрезай на два кусочка, а всё равно один из них обязан равняться единице: главное, чтобы диаметры частей в надбудет иметь диаметр не меньше 1/2. лежащем разбиении оказались малы. Впрочем, на прямой, как мы помним, роль покрышки исполнил отрезок, и его длина была единичной. В двумерье это не так.

4. ПРОБЛЕМА БОРСУКА НА ПЛОСКОСТИ Ещё в 1929 году венгерский математик Й. Пал доказал следуТеперь нам хотелось бы понять, как устроена жизнь в про- ющую лемму:

странстве размерности два. Понятно, что с ростом числа измерений Лемма. В качестве универсальной покрышки для множеств наша основная задача может только усложниться. Так оно на са- диаметра 1 в 2 можно взять правильный шестиугольник, расстомом деле и будет. яние между параллельными сторонами которого равно единице.

Pages:     || 2 | 3 | 4 | 5 |   ...   | 7 |










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

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