Геометрические оценки
и задачи из комбинаторной
геометрии

DjVu

      ПРЕДИСЛОВИЕ
      Настоящая книга представляет собой очередной (но ни в какой мере не зависящий от предыдущих) том из ряда сборников задач, выросших из деятельности школьного математического кружка при Московском государственном университете и из (первоначально тесно связанных со школьным кружком при МГУ) математических олимпиад московских школьников. Такое происхождение книги отражено уже в списке ее авторов, первый и старший из которых в возрасте 23 лет погиб в партизанском отряде более чем 30 лет тому назад. С именем студента Додика Шклярского связаны многие традиции той работы с интересующимися математикой школьниками, которую и по сей день ведут студенты механикоматематического факультета МГУ; в частности, от него идет упор в этой работе на решение задач повышенной трудности1). Поэтому мы сочли уместным и в этой книге, как и в некоторых ей предшествующих, поставить на первое место в списке авторов имя человека, который не мог, конечно, принимать реального участия в работе по ее составлению, но который оказал значительное влияние на составителей. Однако наряду с традициями, идущими еще ог довоенных времен, в книге отражаются и некоторые более свежие влияния — и о них хочется сказать здесь несколько.более подробно.
      Эту книгу можно рассматривать как завершающий этап работы по переработке вышедшего более 20 лет тому назад сборника задач по элементарной геометрии2); при этом в процессе подготовки нового варианта названной книги она настолько разрослась, что ее оказалось уместным выпустить в свет в виде трех отдельных томов (двумя остальными являются книги [4] и [13]). При этом авторам пришлось учитывать то, что за истекшие 20 лет сама элементарная геометрия коренным образом изменила свое лицо; это повлекло за собой необходимость изменения и характера посвященного ей задачника. В самом деле, если еще сравнительно недавно основное содержание элементарной геометрии составляли задачи на доказательство и на построение, связанные со свойствами треугольников, окружностей и фигур, получаемых комбинированием многоугольников и окружностей (именно такие задачи, к слову сказать, составляли большинство в указанном в последней сноске сборнике), то сегодня это направление вызывает сравнительно малый интерес. Последнее частично объясняется тем, что «традиционная элементарная геометрия» была в значительной степени порождена теми разделами математики, расцвет которых относился к XIX, но отнюдь не к XX веку (и которые сами уже в значительной степени утратили свой былой блеск в глазах ученых и любителей математики) — синтетической геометрией') и проективной геометрией2). Однако «природа не терпит пустоты» — и место «классической» элементарной геометрии на наших глазах начинают занимать некоторые новые направления, связанные с актуальной сегодня проблематикой3).
      Говоря о тех сдвигах в общенаучных интересах, которые вызвали определенное «смещение акцентов» в математике, задевшее и элементарную геометрию, надо в первую очередь сказать об одном специфическом типе задач, которые в настоящее время привлекают большое внимание математиков и «потребителей» математики. Мы имеем в виду так называемые «задачи на оптимизацию», ставящие своей целью нахождение «оптимального» (самого лучшего) или по крайней мере «достаточно хорошего» режима работы отдельного механизма или большой системы (механической, биологической, экономической или какой-либо еще). Характерный для нашего времени интерес к задачам такого рода вызвал к жизни целый ряд новых направлений математики — своего рода новых «математических наук», развивающихся с большой интенсивностью. Этот поворот к новой тематике отразился и на геометрии, определив, в частности, подъем внимания к одной возникшей еще в XIX веке ветви математики, — к так называемой дискретной геометрии (о ней см., например, [24] и [25]), неожиданным образом «попавшей в струю» современных исканий.
      Основные задачи дискретной геометрии касаются «плотнейших укладок» равных фигур и «редчайших покрытий» равными фигурами — здесь требуется расположить, скажем, в некоторой ограниченной области ф плоскости или пространства наибольшее возможное число непересекающихся «копий» заданной фигуры F или покрыть Ф наименьшим числом равных F фигур1). Такая постановка задач идет от теории чисел — и первые серьезные результаты в области дискретной геометрии получили создатели геометрических методов теории чисел: немецкий математик Г. Минковский, русские Г. Ф. Вороной, А. Н. Коркин, Е. И. Золотарев, норвежец А. Туэ. Впоследствии, однако, этим направлением заинтересовались и геометры. Особенно возросло внимание к дискретной геометрии, когда выяснилось, что многие ее результаты приложимы в некоторых из связанных с «оптимизационными задачами» новых направлениях математики (например, в имеющей большое прикладное значение «теории кодирования», изучающей оптимальные режимы работы тех или иных линий связи).
      Другое направление геометрических исследований, родственное дискретной геометрии и первоначально находившееся в тесной связи с последней, представляет собой так называемая комбинаторная геометрия. Под этим названием понимают раздел геометрии, в котором рассматриваются задачи о нахождении в том или ином отношении «оптимальных» конфигураций, образованных конечным, числом точек или геометрических фигур. При этом типичные для комбинаторной геометрии задачи связаны с оценкой тех или иных целых чисел — обычно числа точек или фигур, которые .могут входить в удовлетворяющую условиям задачи конфигурацию. Именно таким характером рассматриваемых здесь задач и объясняется прилагательное «комбинаторная» — ведь комбинаторикой называется раздел алгебры, в котором подсчитывается число тех или иных комбинаций конечного числа' элементов, удовлетворяющих заданным в формулировке задачи условиям.
      Задачи комбинаторной геометрии отличаются очень большим разнообразием; при этом формулировки их, как правило, опираются лишь на самые простые геометрические понятия и факты и доступны любому школьнику. Решения же задач комбинаторной геометрии зачастую оказываются весьма сложными; целый ряд основных для этого раздела задач не решен и по сей день. Однако эта тематика подсказывает и ряд задач, которые можно предложить начинающему математику, например интересующемуся математикой школьнику старших классов, — именно такие задачи и составляют основное содержание настоящего сборника.
      Рукопись книги была прочитана Н. Б. Васильевым и Л. И. Головиной, замечания которых позволили внести в текст целый ряд усовершенствований. Очень полезно было обсуждение отдельных задач с молодыми математиками, из числа которых особо хочется отметить Ф. Л. Варпаховского, Г. А. Гальперина, В. Л. Гугенмахера, А. М. Леонтовича и И. И. Яглома. Б. Грюнбаум (Сиэттль, США) и Г. А. Тоноян (Ереван) обратили мое внимание на не замеченную мною ранее литературу, имеющую отношение к теме книги; первый из них поделился также своими соображениями, касающимися одной из приведенных в книге задач. На разных стадиях подготовки книги к печати мне оказывали содействие многие мои друзья; здесь в первую очередь хотелось бы назвать Л. И. Головину, без помощи которой эта книга, вероятно, никогда не увидела бы света. Мне приятно выразить здесь искреннюю признательность всем, кто так или иначе принял участие в создании этой книги.
      И. М. Яглом
     
      УКАЗАНИЯ К ПОЛЬЗОВАНИЮ КНИГОЙ
      Настоящая книга представляет собой сборник задач, условия которых сопровождаются довольно подробными комментариями. Эти комментарии содержат определения некоторых незнакомых широкому читателю понятий, связанных с рассматриваемыми задачами; иногда — краткую историю вопроса и указание на возможные «продолжения» тематики задач и на связанные с ней нерешенные вопросы; зачастую — ссылки на дополнительную, иногда довольно специальную литературу. Книга может быть использована в работе школьного или студенческого кружка (или просеминара) и для самообразования. При использовании книги в работе кружка естественным является рассказ руководителя об общей тематике задач и, возможно, разбор решений некоторых наиболее характерных или наиболее трудных задач; однако желательно, чтобы большую часть задач участники кружка решили сами. Руководителю следует особо обратить внимание учащихся на (указанные в тексте книги или найденные самостоятельно) нерешенные пока задачи, ибо с тематикой книги связано много доступных для начинающих проблем, которые могут послужить трамплином для последующей исследовательской работы. Порядок разбора на кружке полученных его участниками результатов может быть, например, близок к описанному на стр. 21 — 22 книги Д. Пойа «Математическое открытие» (М., «Наука», 1970).
      Для того чтобы облегчить руководителю мотивированный выбор тематики кружка, скажем несколько подробнее о содержании настоящей книги. Собранные в ней задачи разбиты на шесть отдельных циклов, причем деление это в значительной степени условно — так, например, ясно, что задачи 82, 83 цикла 5 и некоторые следующие за ними свободно могли бы быть отнесены к циклу 1, а задачи 61 — 63, 64 6) и некоторые другие из цикла 4 — к циклу 3. Эта условность членения материала книги между отдельными циклами задач частично задевает даже книги [4] и [13], предшествующие настоящей, в которых также затронуты некоторые темы, которые были бы вполне уместны и в настоящей книге, — обстоятельство, о котором стоит, быть может, предупредить преподавателя, собирающегося использовать эту книгу в работе математического кружка. Непосредственно комбинаторной геометрии (о ней говорится в Предисловии к книге) посвящены лишь два последних цикла задач, на которые хочется особо обратить внимание читателей. Однако и многие другие задачи — в первую очередь это относится, пожалуй, к циклам 2 и 3 — также навеяны комбинаторной геометрией.
      Несколько иной характер имеют циклы 1 и 4 — они порождены тем разделом геометрии, из которого выделилась комбинаторная геометрия, а именно теорией выпуклых фигур (см. определения на стр. 55 — 56). В геометрии созданная в XIX веке теория выпуклых фигур занимает сегодня очень большое место. Связано это с тем, что общее понятие «геометрической фигуры» как произвольного множества точек плоскости или пространства является на самом деле настолько сложным, что его и к геометрии-то относить рискованно; сегодня это понятие скорее считают относящимся к топологии1) или к математическому анализу (к теории множеств). Никакие геометрические подходы к понимаемой таким образом «теории фигур» просто невозможны, — и для того чтобы очертить круг «доступных геометрии» объектов, приходится накладывать на рассматриваемые «фигуры» те или иные дополнительные ограничения, самым простым и естественным из которых является требование выпуклости. В настоящее время теория выпуклых фигур выросла в большую, активно развивающуюся науку со своими методами и свойственной только ей тематикой2); значение этой теории сильно возросло и в силу того, что на ее методах в значительной степени основаны дискретная геометрия н комбинаторная геометрия (см. Предисловие). Отражением возросшего значения теории выпуклых фигур является то, что в большинстве стран мира понятие выпуклой фигуры входит сегодня в школьный курс математики.
      Самыми простыми (плоскими) выпуклыми фигурами являются выпуклые многоугольники; при. этом очень важной является возможность заменить произвольную плоскую выпуклую фигуру F «сколь угодно близким к ней» выпуклым многоугольником М, например, вписанным в F. На обсуждение смысла взятого в кавычки выражения в известной мере нацелен цикл задач 1, в котором, впрочем, это обсуждение не доводится до конца; строго доказывается и подробно обсуждается сформулированное утверждение, скажем, в книге [30] или в статье [28]. Выделенное курсивом сзойство выпуклых многоугольников позволяет считать их, в каком-то смысле, «самыми главными» (плоскими) выпуклыми фигурами — очень многие свойства выпуклых многоугольников удается затем автоматически перенести на все выпуклые фигуры, основываясь на этой возможности «приблизить» каждую выпуклую фигуру выпуклыми многоугольниками. .Это обстоятельство делает соблазнительной попытку изложения некоторой части общей теории выпуклых фигур на (доступном и привычном школьникам!) уровне выпуклых многоугольников. Настоящий сборник задач ни в какой мере не претендует, конечно, на решение столь общей методической задачи; однако нам хочется порекомендовать читателям продумать вопрос о возможности переноса тех или иных результатов собранных в цикле 4 задач на (произвольные!) плоские выпуклые фигуры.
      Звездочками в настоящей книге отмечены те задачи, которые нам кажутся более трудными, а двумя звездочками — самые трудные задачи. Все содержание книги разбито на три части. Первую из них составляют условия задач. Предполагается, что читатель начнет с попытки самостоятельного решения задачи. Если это ему не удастся, то он может заглянуть в конец книги, где собраны ответы или указания к решению, с тем, чтобы далее продолжать думать над решением задачи. Вторую часть книги составляют решения задач, их следует читать лишь после того, как задачу удалось решить самому (ибо сравнение найденного решения с приведенными в книге может оказаться поучительным) или если задача очень уж долго не поддается решению. Впрочем, в случае задач, номера которых помечены звездочкой, или — тем более! — двумя звездочками, этот порядок работы может быть и изменен: здесь не зазорно начать попытку решения задачи сразу с ознакомления с приведенным в конце книги «указанием», или даже просто ознакомиться с приведенным во второй части книги «решением», рассматривая соответствующий текст как включенную в настоящий задачник «теорию».
      К книге приложен довольно обстоятельный список литературы (не претендующий, впрочем, на полноту и не исчерпывающий все использованные составителем источники), настолько подробный, что его объем надо, видимо, специально аргументировать. Первая часть списка адресована читателю, заинтересовавшемуся не какой-либо конкретной задачей из числа собранных в настоящем сборнике, а всем тем направлением, которое этот сборник представляет. В этой части библиографии перечислен ряд книг и статей (в подавляющем большинстве своем вполне доступных начинающему математику), уделяющих много места тематике, близкой к той, которой посвящена настоящая книга. Для удобства читателей эта часть списка литературы имеет дополнительную рубрикацию и названные в ней книги и статьи иногда сопровождаются краткими аннотациями, характеризующими их содержание. Однако основную часть списка литературы составляет его вторая часть, содержащая перечень работ, непосредственно связанных с собранными здесь задачами; эти работы разбиты на шесть групп, отвечающих шести циклам задач. Второй раздел библиографического списка обращен в первую очередь не к учащемуся, а к преподавателю, пожелавшему использовать эту книгу в своей работе. Еще одна категория лиц, на которых рассчитан обстоятельный список литературы, — это те читатели, которые пожелали бы испробовать свои силы в попытке самостоятельной исследовательской работы в..области комбинаторной геометрии. Хочется обратить внимание на то, что
      «классическая» элементарная геометрия достигла своего настоящего развития в первую очередь благодаря усилиям лиц, не причислявших себя к нрофессионалам-мате-матикам, — более всего усилиям многочисленных школьных учителей в разных странах мира. Нам кажется, что и комбинаторная геометрия, которая смело может претендовать на положение «элементарной геометрии наших дней», в состоянии заложить фундамент для самостоятельного научного творчества многих любителей математики, начиная с учащихся средней школы — и при составлении настоящей книги мы хотели дать начинающим математикам материал для их исследовательской работы.