Математические беседы (Дынкин, Успенский) 1952 года - Скачать советский учебник

РАЗДЕЛ ВТОРОЙ

ЗАДАЧИ ИЗ ТЕОРИИ ЧИСЕЛ Глава I. Арифметика вычетов 49

§ 1. Арифметика вычетов по модулю т, или т-арифметика 49

§ 2. Арифметика вычетов по модулю р, или р-арифметика 55

§ 3. Извлечение квадратного корня. Квадратные уравнения 59

§ 4. Извлечение кубического корня. Простые делители чисел вида а2 + 3 61

§ 5. Многочлены и уравнения высших степеней 62

Глава II. m-адические и р-адические числа 64

§ 1. Применение 10-арифметики к делению многозначных чисел 64

§ 2. Бесконечно-значные числа 67

§ 3. и-адические и р-адические числа 71

Глава III. Приложения я-арифметики и р-арифметики к теории чисел 80

§ 1. Ряд Фибоначчи 80

§ 2. Треугольник Паскаля 89

§ 3. Дробно-линейные функции 93

Глава IV. Дополнительные сведения о ряде Фибоначчи и треугольнике Паскаля 102

§ 1. Приложение р-адических чисел к ряду Фибоначчи 102

§ 2. Связь между треугольником Паскаля и рядом Фибоначчи 103

§ 3. Члены ряда Фибоначчи, кратные заданному числу 106

Глава V. Уравнение х — 5у2=1 109

Заключение 112

РАЗДЕЛ ТРЕТИЙ

СЛУЧАЙНЫЕ БЛУЖДАНИЯ (ЦЕПИ МАРКОВА)

§ 1. Основные свойства вероятности 121

§ 2. Задачи о блуждании по бесконечной прямой. Треугольник вероятностей 133

§ 3. Закон больших чисел 143

§ 4. Блуждания с конечным числом состояний 154

§ 5. Блуждания с бесконечным числом состояний 167

Заключение 179

РЕШЕНИЯ ЗАДАЧ Раздел первый. Задачи о многоцветной раскраске 181

Раздел второй. Задачи из теории чисел 210

Раздел третий. Случайные блуждания (цепи Маркова) 270

ПРЕДИСЛОВИЕ

Эта книга написана по материалам одной из секций школьного математического кружка при Московском государственном университете им. М. В. Ломоносова, работавшей в 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 — докажем теорему о пяти красках.

{/spoilers}

    1. Докажите, что пересечение двух или нескольких выпуклых фигур есть выпуклая фигура.

2. Докажите, что всякий выпуклый многоугольник является пересечением конечного числа полуплоскостей (черт. 3).

Фигура называется ограниченной, если она целиком помешается внутри некоторой окружности. Например, всякий параллелограмм, треугольник, круг, а также все фигуры, изображенные на черт. 1, являются ограниченными фигурами.

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

Черт. 4.

На черт. 4 изображено несколько неограниченных фигур; из них выпуклыми являются фигуры а (полуплоскость), б (полоса), в (угол) и г.

Выпуклым фигурам можно дать и другие определения отличные от приведенного выше (см. ниже стр. 17 — 18 и 25),

однако определение, приведенное в начале этого параграфа, является самым удобным, и мы, в основном, будем пользоваться этим определением.

По отношению ко всякой плоской фигуре все точки плоскости делятся на три категории: внутренние, внешние и граничные.

Точка фигуры называется внутренней, если существует круг (хотя бы очень малого радиуса) с центром в этой точке, целиком принадлежащий фигуре. Внутренними точками фигуры будут, например, точки А и А' на черт. 5.

Точка называется внешней по отношению к фигуре, если существует круг с центром в этой точке, не содержащий точек фигуры. Примером внешней точки по отношению к фигуре является точка В на черг. 5.

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

Точка С на черт. 5 может служить примером граничной точки фигуры. Граничные точки фигуры образуют некоторую линию — кривую или ломаную. Эта линия называется границей фигуры. Если плоская линия является границей некоторой выпуклой фигуры, то она называется выпуклой кривой, или — в том случае, когда эта линия ломаная, — выпуклым многоугольником 1).

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