Математические беседы

DjVu

      ПРЕДИСЛОВИЕ
      Эта книга написана по материалам одной из секций школьного математического кружка при Московском государственном университете им. М. В. Ломоносова, работавшей в 1945/46 и 1946/47 учебных годах. Один из авторов был руководителем этой секции, другой — ее участником. Секция называлась секцией общего типа. На ее занятиях рассматривались вопросы из различных областей математики. Основной целью было не столько сообщить участникам новые сведения, сколько научить их активному, творческому отношению к математике. Наиболее удачные темы складывались в процессе самой работы секции. В предлагаемую книгу вошли — в значительно переработанном и расширенном виде — три такие темы: задачи о многоцветной раскраске карт, задачи из теории чисел, решаемые с помощью арифметики вычетов, и задачи из теории вероятностей, связанные с так называемыми случайными блужданиями.
      Каждой из этих тем была посвящена целая серия последовательных занятий секции. Она начиналась обычно с задач, которые не требовали никаких новых понятий по своей формулировке, но решение которых должно было сразу ввести участников секции в новый круг вопросов. И в дальнейшем беседы руководителя тесно переплетались с задачами, которые давались в ходе самой беседы, иногда решались на месте, а чаще оставлялись для домашнего решения до стедующего ванятия. Значительная часть всего материала темы предлагалась в виде циклов связанных между собой задач *). На каждом занятии секции определенное время отводилось
      *) Помимо того, на каждом занятии давалось достаточное число задач (типа первых трех выпусков «Библиотеки математического кружка»), не связанных непосредственно с текущей темой.
      разбору решений, которые служили затем материалом для обобщений и выводов, делавшихся руководителем. В своих беседах руководитель излагал также более трудные вопросы, менее поддающиеся расчленению на отдельные задачи.
      Форма беседы, прерывающейся постановкой задач, решение которых существенно для дальнейшего изложения, принята и в этой книге.
      Для чтения первых двух разделов достаточно знания математики в объеме 7 классов средней школы; третий раздел требует несколько большей математической культуры. Книга рассчитана в основном на школьников старших классов, но может быть использована также в студенческих кружках на младших курсах.
      Мы пользуемся случаем выразить нашу благодарность А. Н. Колмогорову, советы которого способствовали значительному улучшению книги. Мы приносим также благодарность Э. Э. Балашу, задачи которого легли в основу §§ 2 и 3 главы IV второго раздела. Наконец, мы признательны М. А. Най-марку и И. М. Яглому, прочитавшим рукопись и сделавшим ряд замечаний. В заключение нам хотелось бы отметить тщательную работу нашего редактора А. 3. Рывкина.
      Е. Дынкин В. Успенский
      Март 1952 г.
     
      УКАЗАНИЯ К ПОЛЬЗОВАНИЮ КНИГОЙ
      Все три раздела независимы друг от друга, поэтому читать их можно в любом порядке; однако при этом следует помнить, что первый раздел является наиболее легким, а третий — наиболее трудным. Добавление к первому разделу содержит решение одной задачи, примыкающей по своему характеру к тематике этого раздела; впрочем, добавление может читаться независимо от первого раздела, так как для его понимания не нужно ничего, кроме определения правильной раскраски.
      Каждый раздел посвящен одной теме; отдельные его части тесно связаны между собой. Поэтому каждый раздел надо читать последовательно, от начала до конца. Исключение составляют только главы II и IV второго раздела, отмеченные звездочками. Они несколько отступают от основного плана раздела и могут быть опущены при первом чтении без ущерба для понимания дальнейшего (глава II является по существу дополнением к главе I, а глава IV — дополнением к главе III).
      Книга рассчитана на активную работу читателя. В каждый раздел входят в качестве его органической части задачи. Большая часть задач группируется в циклы. Каждый цикл составляет единое целое. Чаще всего отдельные задачи, опираясь одна на другую, ведут читателя к окончательному результату, который содержится в заключительной задаче цикла (см., например, задачи 21 — 27, 38 — 41 первого раздела, задачи 84 — 88, 127 — 131 второго раздела и др.). Иногда объединяющей целью является не получение какого-нибудь определенного результата, а овладение новым методом (например, в задачах 11 — 14 первого раздела). Наконец, в небольшом числе случаев задачи носят характер тренировочных упражнений, которые должны помочь читателю овладеть новыми понятиями (задачи 57 — 64 второго раздела, задачи 186 — 188 третьего раздела и др.).
      Приступая к решению задач, полезно просмотреть формулировки всех задач данного цикла. Рекомендуем читателю не заглядывать в решения, помещенные в конце книги, до тех пор пока он не решит все задачи цикла: решения, которые мы приводим, направят его на определенный путь, между тем, размышляя самостоятельно, он может притти к новым, оригинальным решениям. Практика школьного кружка показывает, что при этом иногда получаются более простые и изящные решения, нежели те, которые ожидались авторами задач. Различные циклы задач значительно отличаются друг от друга по своей трудности. Однако опыт университетского школьного кружка позволяет назвать неделю в качестве примерного среднего срока работы над одним-двумя циклами задач.
      Вероятно, читателю не всегда удастся самостоятельно решить все задачи цикла. Если первые задачи решены, но в дальнейшем читатель наталкивается на трудности, которые ему никак не удается преодолеть, то полезно прочесть решения первых, уже решенных задач. Иногда это окажется достаточным, чтобы натолкнуть на решение задачи, ранее не поддававшейся усилиям. Если же трудности окажутся непреодолимыми, то следует ознакомиться с решением трудной задачи и после этого продолжать решение дальнейших задач.
      Несмотря на фундаментальную роль задач, книга отнюдь не является задачником. Равноправную с задачами роль играет помещенный в ней теоретический материал. Взаимоотношение этого материала с задачами различно в различных главах книги. Иногда основное содержание составляют условия задач, и роль остального текста сводится лишь к тому, чтобы ввести необходимые понятия и подвести итоги (см., например, § 1 первого раздела, главу V второго раздела и др.). В других случаях (глава II второго раздела и почти весь третий раздел) ведущая роль принадлежит теоретическому материалу, задачам же отводится подчиненное место. Во всяком случае текст * и задачи тесно связаны между собой и необходимо читать их подряд в том порядке, в каком они приведены в книге.
      В заключение посоветуем читателю не жалеть времени на решение задач. Каждый цикл задач, каждая задача, решенные самостоятельно, будут обогащать арсенал средств, которыми располагает читатель. Одна самостоятельно найденная идея стоит десятка идей, усвоенных с чужих слов. Даже в том случае, когда настойчивые попытки решить задачу не приведут к успеху, потраченное время не пропадет даром: основательно поработав над задачей, вы будете читать ее решение совершенно другими глазами, будете искать причины своей неудачи и сумеете выделить среди рассуждений вспомогательного характера ту основную идею, которая обеспечивает успех.
     
      РАЗДЕЛ ПЕРВЫЙ
      ЗАДАЧИ О МНОГОЦВЕТНОЙ РАСКРАСКЕ
      Различные страны на географической карте окрашиваются для удобства в разные цвета. При этом обычно не требуется, чтобы каждая страна имела свой особый цвет. Достаточно, чтобы в различные цвета были окрашены соседние страны, т. е. страны, имеющие общую границу, например страны Sj и S2 на рис. 1 *)
      *) Страны Sj и Ss не являются соседними, хотя и соприкасаются в точке А (общей границы у них нет).
      Такую раскраску карты мы будем называть правильной. Естественно поставить вопрос, какое число красок нужно иметь для того, чтобы правильно раскрасить данную карту. Ясно, что нас устроит число красок, равное числу стран карты; в этом случае мы просто каждую страну выкрасим в свой цвет. Однако мы не удовлетворимся таким решением: нас будет интересовать минимальное число красок, достаточное для правильной раскраски данной карты. Легко построить карту, для которой таким минимальным числом красок является 2 (рис. 2).
      Карта на рис. 2 является картой острова, расположенного в море, которое показано штриховкой. Море мы не закрасили ни одной из красок а и Ь. Однако обычно море на картах также закрашивается, причем требуется, чтобы прибрежные страны, т. е. страны, граничащие с морем, были окрашены в отличный от моря цвет. Море, таким образом, ничем не отличается для нас от простой страны. То, что оно не ограничено, для нас не существенно. Поэтому в дальнейшем мы не будем выделять море особо, а включим его в число стран. Карты, которые мы будем рассматривать, не будут, таким образом, картами островов; мы будем считать их распространенными на всю плоскость. При такой точке зрения карта на рис. 2 уже не может быть правильно раскрашена двумя красками.
      Вернемся теперь к вопросу о минимальном числе красок, достаточном для правильной раскраски карты. На рис. 3 изображены карты, для которых такими числами являются соответственно 2, 3, 4. На этом наши примеры обрываются. До сих пор не построена карта, для которой минимальное число красок было бы 5 или больше, иными словами, которую нельзя было бы правильно раскрасить четырьмя красками. Есть предположение, что всякую карту можно правильно раскрасить четырьмя красками (в этом состоит известная «проблема четырех красок»). Однако это никем еще не доказано. С другой стороны, доказано, что всякую карту можно правильно раскрасить пятью красками (мы покажем это в § 4). Таким образом, мы можем высказать только следующие два утверждения, досадный пробел между которыми ничем не заполнен:
      Не всякую карту можно правильно раскрасить тремя красками (см. рис. 3, в).
      Всякую карту можно правильно раскрасить пятью красками.
      В следующих параграфах мы займемся вопросом о том, для каких карт достаточно двух красок (§ 1) и трех красок (§2). В § 3 мы постараемся вывести некоторые критерии для четырехцветной раскраски, в § 4 — докажем теорему о пяти красках.