Text
                    МАТЕМАТИКИ
 Комбинаторика  и  перечисление
 D^AGOSTINI


Мир математики
Мир математики Хуанхо Руэ Искусство подсчета Комбинаторика и перечисление Москва — 2014 D3AGOSTINI
УДК 51(0.062) ББК22.1 М63 М63 Мир математики: в 45 т. Т. 34: Хуанхо Руэ. Искусство подсчета. Комбинаторика и пе речисление. / Пер. с исп. — М.: Де Агостини, 2014. — 144 с. Книга, которую вы держите в руках, посвящена парадоксальной науке — комби¬ наторике. С одной стороны, она явно свидетельствует: для того чтобы прийти к неожи¬ данным заключениям, достаточно лишь умения считать и рисовать. С другой стороны, комбинаторика не ограничивается простым счетом: она затрагивает сложнейшие области математики. На первый взгляд комбинаторные задачи кажутся элементарными — их пой¬ мут даже дети, — однако на деле часто оказывается, что их невозможно решить. Но как бы то ни было, комбинаторика помогает нам лучше понять реальность. Это, безусловно, подтвердит гениальный математик Пал Эрдёш, который разделил историю комбинаторики на «до» и «после». Именно он станет нашим проводником в этот удивительный мир. © Juanjo Rue, 2011 (текст) © RBA Coleccionables S.A., 2011 © ООО «Де Агостини», 2014 Все права защищены. Полное или частичное воспроизведение без разрешения издателя запрещено. ISBN 978-5-9774-0682-6 ISBN 978-5-9774-0729-8 (т. 34) УДК 51(0.062) ББК22.1
Содержание Предисловие 7 Глава 1. Посчитаем! 9 Искусство подсчета 9 Считаем на пальцах 12 Теория вероятностей и комбинаторика — науки, идущие рука об руку 23 Глава 2. Графы и карты 33 Графы и карты 35 Несколько примеров посложнее 44 Метод двойного подсчета 49 Деревья — главные герои теории графов 55 Глава 3. Вечный странник 61 «Мой разум открыт для вас!» 61 Детство 64 Юность и изгнание 67 США, Израиль... жизнь странника 71 Личность гения: гипотеза и доказательство 74 Глава 4. Считаем (уже не на пальцах) 83 Что мы видим и чего не видим 84 Как разделить завтрак 84 На встрече одноклассников 89 Задача со счастливым концом 96 И снова о теории вероятностей. Вероятностный метод 100 Глава 5. Комбинаторика чисел 107 Основы арифметики 108 Функции представления 115 Вес имеет значение 120 ...Несмотря на это, существуют арифметические прогрессии 125 Заключение 130 5
СОДЕРЖАНИЕ Приложение. Доказательство леммы Шпернера 133 Библиография 137 Алфавитный указатель 139 6
Посвящается моим родителям и бабушке Антонии Предисловие Однажды в солнечный день я гулял с подругой по Люксембургскому саду. Все во¬ круг бурлило: мастера игры в петанк вели свое сражение, дети замышляли обычные шалости, а влюбленные парочки не замечали никого вокруг. Меня переполнял вос¬ торг, ведь мы шагали по Латинскому кварталу, а в этом районе Парижа все просто дышит историей. Само место приглашает к размышлениям и диалогу. Вот и мы, под¬ давшись этому очарованию, начали свой разговор. Вначале мы не поняли друг дру¬ га: я говорил о математике, точнее, говорил на математическом языке, но с трудом доносил до своей подруги идеи, скрывавшиеся за нагромождением малопонятных терминов. Однако я быстро осознал свою ошибку и попытался ее исправить. Математика — техническая (и весьма техническая!) наука, но оперирует она идеями. Идеи следует излагать простым языком, пусть даже для этого потребуется приложить немало сил. Достичь этой цели не всегда удается и самим математикам, и в результате возникает неверный, далекий от реальности образ. По моему мнению, опытный и не очень опытный исследователь должен идти на компромисс с обще¬ ством и осознавать моральную обязанность донести до него суть своих трудов: важ¬ ные идеи и прекрасные результаты. Такую скромную цель я и преследовал, работая над этой книгой. Она посвящена комбинаторике — науке, в которой одного умения считать и ри¬ совать достаточно, чтобы получить непростые, удивительные и неожиданные ре¬ зультаты. Комбинаторные задачи звучат просто (их поймут даже дети), но решить их подчас невозможно. При этом задачи и понятия комбинаторики помогают нам лучше понять реальность. Мы начнем знакомство с этой наукой с простого счета на пальцах. Это помо¬ жет нам понять, почему иногда выгодно делать ставку в азартной игре, даже если на первый взгляд мы не имеем преимущества. Далее вы узнаете, что комбинаторика не ограничивается простым счетом — она также описывает дискретные модели, ко¬ торые помогают упростить реальность. Вы поймете, что при проектировании сети 7
ПРЕДИСЛОВИЕ автомобильных дорог расположение мостов зависит не от прихоти главного инжене¬ ра, а от того, как именно нужно соединить населенные пункты. Все термины, о которых мы расскажем в этой книге, весьма необычным образом использовал один человек, который разделил историю комбинаторики на «до» и «после», — гениальный математик Пал Эрдёш. Он станет нашим проводником в мире современной комбинаторики, где счет уже не ведется на пальцах, где рассма¬ триваются хаотические объекты, скрывающие в себе упорядоченные структуры, где смешиваются случайность и детерминизм, где играют в кости с графами и находят старых друзей на встречах выпускников. Да, Бог играет в кости не только со Все¬ ленной. В заключение мы покажем, что в арифметике, можно сказать, волшебным обра¬ зом сокрыта комбинаторика, и объясним величайшую математическую теорему всех времен — теорему Грина — Тао. Кстати, воспользуюсь случаем и поблагодарю Гильермо Наварро за все советы, которые я получил от него, работая над книгой, и Хавьера Фресана, поверивше¬ го в мой просветительский дар. Также я хотел бы поблагодарить Марту Бенагес и Хосе Мигеля Но за то, что они прочли часть рукописи. 8
Глава 1 Посчитаем! Путешествуя по разным странам, мы стремимся попробовать местные кулинарные изыски. Путешествие можно считать состоявшимся, если оно включает какое-ни¬ будь гастрономическое открытие,— в этом случае путешественник задействует все свои органы чувств. Дегустация местных блюд — это не только развлечение, но и возможность лучше понять культуру и обычаи посещаемых мест. К сожалению, часто путешественник, слишком привыкший к кухне родных мест, не может в полной мере оценить заморские гастрономические изыски. В результате он, испытывая некоторое чувство вины, отправляется в один из множества итальян¬ ских ресторанов, которые можно найти в любом уголке земного шара. Фирменное блюдо в любом итальянском ресторане — это, конечно, пицца. И здесь путеше¬ ственник сталкивается с главным вопросом всей жизни: какую пиццу выбрать — «4 сыра» или «4 сезона»? Среднюю или маленькую? С луком или без? Стоит ли добавить еще один ингредиент? При таком многообразии сомнения неизбежны — помимо видов пиццы, указанных в меню, перед путешественником открывается це¬ лая вселенная всевозможных ингредиентов и вкусов. Разумеется, тут же возникает вопрос: сколько видов пиццы можно составить из ингредиентов, которые есть в ресторане? Сделать необходимые подсчеты непро¬ сто по многим причинам: к примеру, некоторые ингредиенты несовместимы друг с другом. Искусство подсчета По-настоящему важно, что подобные вопросы в обычной жизни возникают посто¬ янно. Сколькими способами мы можем выбрать пиджак и галстук из нашего гар¬ дероба так, чтобы сочетания не повторялись и, что особенно важно, чтобы цвета деталей одежды сочетались друг с другом? Или: сколькими способами можно объ¬ ехать милые маленькие городки нашей провинции? Все эти вопросы в той или иной 9
ПОСЧИТАЕМ! степени относятся к перечислительной комбинаторике. Эту науку можно назвать искусством подсчета, так как подсчет — это настоящее искусство, требующее осо¬ бых методов. Искусство подсчета нельзя считать новой наукой. Напротив, счет — одно из са¬ мых естественных и основных понятий математики. Истоки искусства подсчета, как и многих других наук, неясны: на Западе систематическое изучение этой на¬ уки началось из-за ее тесной связи с теорией вероятностей. Еще в XVII веке Блез Паскаль (1623, Клермон-Ферран — 1662, Париж) и Пьер Ферма (1601, Бомон- де-Ломань — 1665, Кастр) рассматривали вопросы теории вероятностей, связан¬ ные с азартными играми, которые предложил страстный игрок шевалье де Мере. В ответах на эти вопросы основное место занимал подсчет числа благоприятных исходов по отношению к общему числу возможных исходов (в теории вероятностей это правило подсчета называется правилом Лапласа). Позднее усилиями великих Готфрида Вильгельма Лейбница (1646, Лейпциг — 1716, Ганновер) и Якоба Бер¬ нулли (1654, Базель — 1705, Базель) комбинаторика оформилась как отдельная дисциплина. Впоследствии, с развитием математического языка и математических методов, стало понятно, что комбинаторика имеет тесное отношение к иному типу задач, выходящих за рамки вероятностей и подсчетов, а именно к задачам на гра¬ фах. Понятие графа впервые ввел Леонард Эйлер (1707, Базель — 1783, Санкт- Петербург) для решения задачи о мостах Кёнигсберга, а Артур Кэли (1821, Рич¬ монд, Великобритания — 1895, Кембридж, Великобритания) получил различные результаты, связанные с перечислением графов, при изучении изотопов насыщен¬ ных углеводородов. Обширные теоретические и практические исследования продол¬ жаются в рамках комбинаторики по сей день. Перечислительная комбинаторика не только описывает алгоритмы счета на паль¬ цах (порой весьма хитроумные), но и позволяет получить качественную информа¬ цию о структуре изучаемых объектов. Хотя эта наука занимает особое место на ма¬ тематическом Олимпе, ее плодами питаются многие другие дисциплины: в теории вероятностей без искусства подсчетов не обойтись, если требуется определить от¬ ношение числа благоприятных исходов к общему числу возможных исходов; в тео¬ рии алгоритмов крайне важно знать, сколько действий содержит тот или иной про¬ цесс, чтобы оценить его эффективность по сравнению с уже известными. Искусство подсчета выходит далеко за рамки этих дисциплин и тесно переплелось с самыми разными науками, в частности с перечислительной геометрией и статистической ме¬ ханикой. 10
ПОСЧИТАЕМ! Создатели комбинаторики Якоб Бернулли (вверху слева), Леонард Эйлер (слева) и Гэтфрид Вильгельм Лейбниц на памятных марках. РАЙМУНД ЛУЛЛИЙ, ЕЩЕ ОДИН ОСНОВОПОЛОЖНИК КОМБИНАТОРИКИ Раймунд Луллий (ок. 1232, Пальма, Испания - 1315, во время морского путешествия близ Пальмы, Испания) родился в семье буржуа на острове Мальорка вскоре после того, как остров был завоеван войсками испанского короля Хайме I Арагонского. Свою жизнь Луллий посвятил множеству самых разных занятий. В юности он был придворным Хайме I и, можно сказать, вел праздную жизнь. Несколько лет спустя, после многочисленных видений, в которых ему являлся Иисус на кресте, Луллий оставил семью и предался созерцанию. Он стал францисканским мис¬ сионером, жил в аскезе и объехал все Средиземноморье, проповедуя христианство и обращая людей в свою веру. Также он оставил ряд трудов по философии, богословию, астрономии и ал¬ химии. Луллий считается основателем многих современных наук, в частности комбинаторики. В своем главном труде «Великое искусство» (Ars Magna, 1305) он описал метод комбинирования религиозных и философских атрибутов, представленных в виде списка. На мысль о комбина¬ торике миссионера навели арабские инструменты, применявшиеся в астрономии и навигации и основанные на комбинировании различных положений для достижения желаемого результата. Луллий пытался найти понятия, позволяющие формулировать суждения и силлогизмы в любой области, а также выстраивать логические рассуждения на основе математических законов. Его целью в некотором роде была механизация и «математизация» знаний на основе комбинато¬ рики. Считается, что труды Раймунда Луллия опосредованно послужили основой для создания компьютерных технологий и искусственного интеллекта. И
ПОСЧИТАЕМ! Считаем на пальцах Начнем наше путешествие в мир комбинаторики со счета на пальцах и некото¬ рых очевидных соображений. Быть может, при подсчетах нам понадобится не 10, а п пальцев! Как вы увидите чуть позже, одни предметы можно подсчитать напря¬ мую, другие — косвенно, а третьи — сразу несколькими способами, и в каждом случае потребуется проявить немалую изобретательность. Чтобы понять основные принципы комбинаторики, сначала научимся переводить фразы, сказанные на обычном языке, в общие, универсальные утверждения. Для начала переведем на язык математики понятия «и» и «или». Рассмотрим простой пример. Допустим, что мы пришли в любимый ресторан пообедать. Мы завтракаем очень рано, поэтому организм просит полноценного обеда из закуски и основного блюда. Или другой вариант: из-за многочисленных нарушений режима в прошлые месяцы наши любимые врачи посоветовали соблюдать строгую диету, поэтому мы ограничимся либо закуской, либо основным блюдом. Рассмотрим первую ситуацию. В этом случае союз «и» означает, что мы должны выбрать два блюда — закуску и основное. Выбор следует делать так: сначала вы¬ берем закуску, которая понравилась нам больше всего, затем — основное блюдо. Пара вида (закуска, основное блюдо) однозначно определяет обед. Абстрактная математическая конструкция, описывающая эту ситуацию, такова. Для двух множеств А и В определим декартово произведение А и В как новое мно¬ жество С (будем обозначать его А * В), элементы которого представляют собой пары. Первый элемент каждой пары принадлежит множеству Ау второй — мно¬ жеству В. В нашем примере множество А будет содержать все закуски, множе¬ ство В — все основные блюда, множество С — все возможные сочетания закусок и основных блюд. Каждое из этих сочетаний будет представлять собой пару (а, Ь), где а — элемент множества А, Ь — элемент множества В. Сколько всего таких пар? Иными словами, как подсчитать число элементов множества С? Отчет очеви¬ ден: нужно умножить число элементов А на число элементов В. В нашем примере для каждой закуски можно выбрать любое основное блюдо. Эти рассуждения носят 12
ПОСЧИТАЕМ! общий характер и описывают правило, которое в комбинаторике называется прави¬ лом умножения: «Пусть А и В — два конечных множества. Тогда число элементов декартова произведения А и В равно произведению числа элементов А и числа элементов В». Теперь рассмотрим вторую ситуацию, когда мы соблюдаем диету и вынуждены ограничиться только одним блюдом. Сколькими способами можно сделать выбор? Число возможных вариантов будет равно сумме числа закусок и основных блюд, так как ни одно блюдо не может быть закуской и основным одновременно. На языке математики это правило записывается следующим образом. Рассмотрим два непе- ресекающихся множества А и В. В нашем примере это будут множества закусок и основных блюд, так как ни одно блюдо не может быть закуской и основным одно¬ временно. Мы хотим выбрать один элемент из одного из этих множеств, то есть некий элемент А или же некий элемент В. Для этого следует объединить множества AylByl выбрать один элемент из полученного объединения. Союз «или» в переводе с обычного языка на язык математики обозначает объ¬ единение множеств. Все приведенные выше рассуждения сводятся к правилу, кото¬ рое в комбинаторике называется правилом сложения: «Пусть А и В — два конечных множества, не имеющие общих элементов. Тогда число элементов объединения А и В будет равно сумме числа элементов А и числа элементов В ». Рисунки ниже иллюстрируют смысл операций объединения и декартова произ¬ ведения множеств, из которых выводятся правило сложения и правило умножения, представленные выше. 13
ПОСЧИТАЕМ! МАТЕМАТИЧЕСКИЕ ОБОЗНАЧЕНИЯ ДЛЯ БАЗОВЫХ ПРАВИЛ И ПРИНЦИПА ВКЛЮЧЕНИЙ-ИСКЛЮЧЕНИЙ Правило умножения и правило сложения в комбинаторике можно записать с помощью матема¬ тических обозначений. Обозначим через |А| число элементов А. Правило умножения можно записать следующим образом: |А*8|-|А|-|8|. Напомним, что объединение А и 8 записывается как А и В. Правило сложения непересека- ющихся множеств А и В будет записываться так: IAUBMAMBI. Правило сложения можно уточнить для случаев, когда множества А и В имеют общие элемен¬ ты. Допустим, что множества А и В пересекаются, и это пересечение содержит некий элемент (на языке математики это утверждение записывается так: А п В * 0). Учитывая, что при сло¬ жении числа элементов А и В мы два раза учтем число общих элементов множества, нетрудно вывести формулу: |АиВ|-|А| + |В|-|АПВ|. Рассуждая аналогичным образом, можно обобщить эту формулу для трех множеств. Пусть А, В, С - конечные множества. Выполняется следующее соотношение: |АиВиСМА| + |В| + |СИАПВ|-|АПС|-|ВПС| + |АПВПС|. Эти рассуждения можно обобщить для произвольного числа множеств. Результатом обобще¬ ния будет принцип включения-исключения, который применяется в комбинаторике и теории чисел множеством способов - так, он позволяет оценить размер объединения нескольких мно¬ жеств, когда размеры их пересечений известны. Правило сложения и правило умножения стоят в самом начале пути в мир под¬ счета. Эти простые правила позволяют получить некоторые элементарные выраже¬ ния, подобные приведенным ниже. Рассмотрим множество А из п элементов и вычислим декартово произведение А с самим собой, взятым некоторое число раз (допустим, г). Полученное множество 14
ПОСЧИТАЕМ! будет состоять из последовательностей вида (av av ..., аг) (в математике такие по¬ следовательности называются кортежами длиной г), где каждый член последова¬ тельности является элементом А. Каково число всех возможных кортежей длиной г? Если бы г равнялось 2, то записанное выше выражение свелось бы к правилу умно¬ жения: п * п = п2. Если г не равно 2, достаточно последовательно применять прави¬ ло умножения, чтобы определить: число кортежей длиной г равно п • гг ... • п = пг. Этот набор называется размещением с повторениями. Немного усложним задачу и предположим, что мы хотим подсчитать такие кор¬ тежи длиной г, в которых ни одна составляющая не повторяется. Первый важный момент при ответе на этот вопрос таков: длина последовательности г должна быть меньше либо равна п — числу элементов А (в противном случае некоторые коор¬ динаты будут повторяться). Чтобы найти искомое число кортежей, заметим, что каждый кортеж (ау av ..., аг), все составляющие которого различны, можно по¬ строить следующим образом. Выберем из всех возможных элементов множества тот, что станет первой составляющей ау Далее выберем второй элемент среди всех возможных, за исключением ау так как мы уже выбрали его на первом шаге. Третью составляющую выберем аналогичным образом среди всех возможных, за исключе¬ нием а] и аг и так далее до г. Чему же будет равно общее число кортежей? Выбрать flt можно любым способом, таким образом, имеем п вариантов. При выборе а2 у нас количество способов выбора будет равно п — 1, и так далее. Получим так называ¬ емые размещения без повторений из п по г. Их число рассчитывается по формуле: п • (п — 1) • (п — 2) •... • (п — г +1). В случае когда г равно п, имеем перестановку п элементов. Формула размещений без повторений при этом записывается так: п • (п — 1) • (п — 2) *... • 2 • 1. Это выражение обычно записывается в сокращенном виде как п! (п факториал). Факториал указывает, сколькими способами можно упорядочить элементы данного множества. Эта формула широко используется в математике: к примеру, с помощью факториалов формулу числа размещений с повторениями можно записать так: и-(и-1)-(и-2)-...-(и-г + 1) = ^-^. 15
ПОСЧИТАЕМ! Факториал определен только для натуральных чисел. Факториал 0 для удобства определяется как 0! = 1. (Такое определение факториала было выбрано из сооб¬ ражений, связанных с некоторыми более общими формулами. Эти формулы имеют отношение к так называемой гамма-функции, использующейся в самых разных раз¬ делах математики, в частности в теории вероятности и аналитической теории чисел.) Логично, что следующим шагом будет переход к неупорядоченным структурам. До сих пор при подсчетах мы учитывали порядок следования элементов и работали с кортежами длиной г, составленными из элементов некоторого множества А. Од¬ нако существует бесконечное множество примеров, в которых порядок элементов не важен. Предположим, мы хотим поехать в горы на пятиместной машине, но в по¬ ездку желают отправиться сразу десять человек. Здесь важнее, кого именно мы выберем, а не в каком порядке. Мы умеем обращаться с упорядоченными объекта¬ ми. Но как подсчитать неупорядоченные? Очень просто: неупорядоченный объ¬ ект — это всего лишь упорядоченный объект, при работе с которым мы забываем о порядке следования элементов. Подмножество А, состоящее из г элементов, — это группа из г элементов, вы¬ бранных из п элементов множества Ау для которых порядок следования не важен. Для данного множества А из п элементов мы хотим узнать, сколько различных подмножеств А содержит г элементов. Это значение называется числом сочетаний без повторений размера г на множестве размера п. Так, для каждого подмножества из г элементов можно определить г! разных кортежей длиной г, где г! определяется в результате перестановки элементов (вспомните приведенное выше определение перестановки). Ранее мы уже определили число размещений без повторений. Чис¬ ло сочетаний без повторений равно числу размещений г элементов без повторений, разделенному на число перестановок. Иными словами, имеем следующую формулу: п! г/(и —г)/* В математике при работе с сочетаниями обычно используется особая нотация и отдельное понятие биномиального коэффициента, который обозначается следую¬ щим образом: ( \ п 16
ПОСЧИТАЕМ! Биномиальные коэффициенты также указывают число перестановок с повторе¬ ниями. Рассмотрим множество А из двух элементов. Для удобства определим их как О и 1. Каким будет число упорядоченных последовательностей длиной п, содержа¬ щих ровно г нулей и п — г единиц? К примеру, примем п = 4 и г = 2. Имеем шесть кортежей длиной 4: (0,0,1,1), (0,1,1,0), (0,1,0,1), (1,1,0,0), (1,0,0,1), (1,0,1,0). Вместо того чтобы напрямую подсчитать число перестановок с повторениями, воспользуемся тем, что мы уже умеем подсчитывать число сочетаний без повторе¬ ний, и поставим в соответствие каждой перестановке с повторением подмножество В = {1, 2, ..., п} из г элементов. Так мы в точности установим соответствие между перестановками с повторениями и подмножествами из г элементов. Для каждой по¬ следовательности длиной п определим подмножество {1, 2, ..., п} следующим обра¬ зом: если ш-я цифра в кортеже длиной г равна 1, то т принадлежит подмножеству, в противном случае — нет. В нашем примере получим следующие соответствия: (0, 0,1,1) {3, 4} (0,1,1, 0) {2, 3} (0,1, 0,1) {2, 4} (1,1, 0, 0) —> {1, 2} (1, 0, 0,1) {1, 4} (1, 0,1,0) -*{1,3} Нетрудно убедиться, что эта операция обратима, и для каждого множества из г элементов можно построить последовательность из единиц и нулей, содержа¬ щую ровно г единиц. Использованный метод называется биективным. Он окажется крайне важным при подсчете объектов, которые кажутся различными, хотя, по сути, одинаковы. Совокупность представленных выше понятий дает начало следующей задаче, из¬ вестной как «задача о комитете». Представьте, что нам нужно сформировать коми¬ тет представителей группы из п человек, причем число членов комитета может быть произвольным (в него даже может не входить ни одного человека). Необходимо определить, сколькими способами можно сформировать такой комитет. Рассмотрим задачу двумя разными способами. 17
ПОСЧИТАЕМ! С одной стороны, комитет будет состоять из г человек, где г принимает значения от 0 (в этом случае в комитете не будет ни одного члена) до п (в комитет войдут все члены исходной группы). Зафиксируем это значение г. Сколько комитетов из г чле¬ нов можно сформировать на основе группы из п человек? Искомое число будет равно числу подмножеств размера г для исходного множества размера п. Как мы указывали выше, это число определяется биномиальным коэффициентом Так как нам требуется найти общее число комитетов для всех возможных значе¬ ний г, по правилу сложения получим, что искомое число равно сумме: ( \ ( \ ( \ п + п п + п Многоточия в этой формуле указывают на то, что нижний индекс биномиальных коэффициентов принимает значения от 0 до п. Посмотрим, как можно получить этот же результат другим способом. Начнем с того, что обозначим каждого члена группы некоторым числом от 1 до п. Каждому человеку будет соответствовать свое число. Теперь рассмотрим кортеж длиной п, в котором каждая составляющая равна О или 1. Каждый из этих кортежей содержит следующую информацию: если в по¬ зиции i записана единица, то человек с номером i является членом комитета. Если же в позиции i записан 0, этот человек не входит в комитет. Например, при п = 4 один из кортежей будет выглядеть так: (0, 0, 1, 1). Это означает, что в комитет войдут люди, обозначенные числами 3 и 4. Теперь можно применить приведенные выше результаты, чтобы найти число кортежей длиной п, составляющие которых равны О или 1. Искомое число будет всего лишь числом размещений с повторениями дли¬ ной п для множества из двух элементов (0 и 1). Это число будет равняться 2П. Два полученных значения (сумма биномиальных коэффициентов и степень) указывают одно и то же число способов, которыми можно сформировать комитет из группы в п человек. Мы доказали следующее свойство: ( \ ( \ ( \ ( \ п + п п + п к л Kn-\J 18
ПОСЧИТАЕМ! ТЕОРЕМА О БИНОМЕ И ЕЕ СЛЕДСТВИЯ В КОМБИНАТОРИКЕ Из правил подсчета неупорядоченных объектов выводится теорема о биноме Ньютона, который назван в честь первого ученого, систематически изучившего биномы, - гениального физи¬ ка и математика Исаака Ньютона (1642, Вулсторп - 1727, Кенсингтон). Рассмотрим бином 1 +х. Многочлен, или полином (1 +х)", будет иметь вид з0 + агх + а/2 + ... + а/1. Коэффициенты этого многочлена можно вычислить с помощью методов комбинаторики. Запишем (1 +х)" как бином 1 +х, умноженный сам на себя п раз: (1+х)-(1+х)-...-(1+х). Ключевой элемент наших рассуждений таков: итоговое выражение результатом выбора 1 или х из каждой скобки всеми возможными способами. Так, чтобы вычислить коэффициент для члена х(. (то есть а), будем действовать следующим способом: выберем х для / одночленов из п одночленов в произведении, а для остальных одночленов выберем 1. Если мы выполним аналогичные действия для всех значений /, получим теорему о биноме, которая будет иметь следующий вид: / \ ( \ ( \ ( \ ( \ п * о + л <1 + Г) х2 + ...+ п х°-' + п я uJ Л л Из этого соотношения можно получить другие, не менее интересные. Так, если мы подставим 1 вместо х, получим формулу из задачи о комитете: ( \ п + ( \ п + ...+ ( \ п ,0, л = (1 + 1)л = 2л. Если мы примем х - -1, получим равенство: п / .\Л ( \ п I- U...+ -1 uJ = (1-1)" = 0. Существует множество соотношений с биномиальными коэффициентами. Одно из них — так называемый треугольник Паскаля, или таблица Тартальи. Треуголь¬ ник Паскаля не просто математическая диковинка. Его можно использовать для до- 19
ПОСЧИТАЕМ! казательства многих соотношений комбинаторики, подобно тому, как для быстрых арифметических расчетов применяется абак. Треугольник был известен еще в древ¬ ности: в Китае, Индии и Персии эта числовая таблица изучалась за 500 лет до того, как ее описал Паскаль. В Китае она называется треугольником Яна Хуэя в честь математика Яна Хуэя, описавшего ее в 1303 году. На рисунке ниже изображены восточная версия треугольника Паскаля и ее упрощенный вариант, который мы бу¬ дем использовать в рассуждениях. Треугольник Яна Хуэя и первые вершины упрощенной модели треугольника Паскаля. При работе с треугольником Паскаля важнейшую роль играет следующее на¬ блюдение. Будем считать точку (0, 0) началом отсчета. Рассмотрим пути, соеди¬ няющие эту точку с точкой (п, т) так, что на каждом шаге пути мы опускаемся на одну строку вниз (влево или вправо). Общее число таких путей равно биноми¬ альному коэффициенту: / \ н И действительно, чтобы попасть в точку (п, ш), нужно выполнить всего п шагов, так как на каждом шаге мы спускаемся на одну строку вниз, или, что аналогич¬ 20
ПОСЧИТАЕМ! но, первая координата возрастает на 1. Кроме того, когда мы будем двигаться вниз по треугольнику, нужно будет выполнить ровно т шагов влево, так как при шагах вправо вторая координата не увеличивается. Следовательно, число способов, кото¬ рыми можно попасть из начала отсчета в точку (п, ш), равно числу перестановок с повторениями, где шаг влево повторяется т раз, а шаг вправо — (п — г) раз. С помощью треугольника Паскаля и его геометрической интерпретации различ¬ ные комбинаторные соотношения можно вывести напрямую, без вычислений. Пер¬ вое из этих соотношений — значение биномиального коэффициента: ( \ п Этот биномиальный коэффициент указывает, сколькими способами можно по¬ пасть из начала отсчета в точку (п, 0). Так как в конечную точку можно попасть только одним способом, значение этого биномиального коэффициента должно рав¬ няться единице. Усложним рассуждения, чтобы получить соотношение поинтереснее. Чтобы по¬ пасть на горизонтальный уровень п, сначала нужно пройти через горизонтальный уровень п — 1. Чтобы попасть в точку (п, ш), сначала нужно пройти через точку (п — 1, т — 1) или через точку (п — 1, ш). (п— 1, т) Часть треугольника Паскаля, на которой изображены пути, ведущие в точку (n, т). По правилу сложения получим: число способов, которыми можно попасть в точ¬ ку (п, гп), равно сумме числа способов, которыми можно попасть в точку (п — 1, т — 1), и числа путей, ведущих в точку (п — 1, т). В виде биномов это утверждение записывается так: / \ п //-1 т — 1 \ + У п — 1 т \ У 21
ПОСЧИТАЕМ! СИММЕТРИЯ В ТРЕУГОЛЬНИКЕ ПАСКАЛЯ В приведенных выше примера* мы использовали особенности структуры треугольника Паскаля. Но применив свойства его симметрии относительно центральной оси, получим, что пути, вы¬ ходящие из начала отсчета и ведущие в точку (л, г), превратятся в пути, выходящие из начала отсчета и ведущие в точку (л, л - г). Следовательно, выполняется следующее свойство: Эти рассуждения можно применить для доказательства более сложных свойств, например такого: Чтобы доказать его, воспользуемся следующим свойством: чтобы попасть из начала отсчета в точку (2л, л), нужно обязательно пройти через точку с координатами вида (л, г). Так как число путей, ведущих из точки (л, г) в точку (2л, л), равно числу путей, ведущих из начала отсчета в точку (л, г) (вспомните свойства симметрии треугольника Паскаля), то приведенная выше формула выполняется в силу правила сложения и правила умножения. (2 п,п) Путь, соединяющий начало отсчета и точку (2п, п), проходит через уровень л. Предлагаем читателю доказать эту формулу с помощью теоремы о биноме, о которой мы уже говорили. (0,0) 22
ПОСЧИТАЕМ! В этом вводном разделе мы рассказали об основах искусства подсчета. Все из¬ ложенное выше будет крайне полезно при чтении следующих глав, в которых мы рассмотрим более сложные темы, в частности графы, карты и деревья, а также при решении задач и парадоксов, возникающих при обычной игре в кости. Теория вероятностей и комбинаторика - науки, идущие рука об руку Плодами комбинаторики пользуются многие другие области знаний. Вычисление вероятностей в азартных играх — один из самых удобных способов познакомиться с ее основами. Изложенные выше правила сложения и умножения, а также связан¬ ные с ними понятия, в частности биномиальные коэффициенты, помогут нам лучше понять некоторые любопытные парадоксы, связанные с азартными играми. Ин¬ тересно, что точные подсчеты часто оказываются важнее, чем интуиция опытного игрока. Теория вероятностей как отдельная дисциплина берет начало в обширной пере¬ писке между Антуаном Гомбо (1607—1684) и математиками Пьером Ферма и Бле¬ зом Паскалем. Хотя Гомбо не был дворянином, он подписывал свои произведения псевдонимом шевалье де Мере — по названию городка, в котором жил и работал. Шевалье де Мере был не только ярым сторонником общественного диалога с мо¬ нархией, но и большим любителем азартных игр. Он обратил внимание на несколько парадоксальных ситуаций, возникавших при игре в кости, и поделился своими сооб¬ ражениями с великим французским философом и математиком Блезом Паскалем. Письмо де Мере Паскалю положило начало обширной переписке между проница¬ тельным игроком и философом, к которой позднее присоединился адвокат и матема¬ тик-любитель Пьер Ферма. Паскаль в письме к Ферма от 29 июля 1654 года оста¬ вил любопытный комментарий: «.. .Шевалье де Мере очень талантлив, но он не гео¬ метр, а это, как вам известно, большой недостаток...» Хотя мы с вами тоже не геометры, попытаемся понять, что означают термины «вероятность» и «случайное событие». Мы поговорим о лотереях, азартных играх и ставках и рассмотрим абстрактные обозначения, которые используются в этих об¬ ластях для решения задач в общем виде. К примеру, когда мы бросаем игральный 23
ПОСЧИТАЕМ ФЕРМА И ПАСКАЛЬ: АДВОКАТ И ФИЛОСОФ, ИЗМЕНИВШИЕ МАТЕМАТИКУ Пьер Ферма служил чиновником в парламенте Тулузы, что не помешало ему стать одним из самых влиятельных мате¬ матиков первой половины XVII века. Среди его важнейших результатов отметим создание основ алгебраической геоме¬ трии и теории вероятностей. Неофициальный титул «король среди любителей» Ферма заслужил благодаря открытиям в теории чисел. Наверное, самая известная из всех исто¬ рий о Ферма гласит, что он записал на полях «Арифметики» Диофанта такие слова:«.. .Невозможно разложить куб на два куба, биквадрат на два биквадрата и вообще никакую сте¬ пень, большую квадрата, на две степени с тем же показате¬ лем. Я нашел этому поистине чудесное доказательство, но поля книги слишком узки для него...» Эта теорема, получившая название великой теоремы Ферма, была доказана более 400 лет спу¬ стя с помощью методов, весьма далеких от тех, которые были известны французскому адвокату. Труды Блеза Паскаля охватывают широкий спектр дисциплин, начиная от математики и за¬ канчивая философией, не говоря уже о физике. Помимо вклада в основы теории вероятностей, Паскаль совершил важные открытия в гидростатике. После того как в 1654 году Паскаль, бу¬ дучи близок к смерти, пережил божественное видение, его вера укрепилась и он стал уделять больше внимания религии. Спустя много лет ученый практически полностью посвятил себя философии и богословию. Именно в этом контексте, на стыке религии и математики, он пред¬ ложил так называемое пари Паскаля в своей книге «Мысли о религии и других предметах». Смысл этого пари таков. Допустим, что нам неизвестно, су¬ ществует ли Бог. Паскаль утверждал: выгоднее ставить на то, что Бог существует. Даже если вероятность этого ничтожно мала, она компенсируется огромным выигрышем - вечной жизнью после смерти. 24
ПОСЧИТАЕМ! кубик, на результат броска воздействует огромное множество факторов: угол бро¬ ска, скорость кубика, момент инерции, высота относительно стола в начальный мо¬ мент времени, трение о воздух и многие другие. Предусмотреть все факторы, воз¬ действующие на результат, невозможно, следовательно, эксперимент с броском ку¬ бика имеет крайне сложную природу. И вся эта сложность скрывается за понятием случайности. При каждом повторении эксперимента начальные условия будут отличаться, и из-за сложности изучаемой системы предсказать результат будет невозможно. Как измерить непредсказуемый результат эксперимента? Мы можем повторить его очень много раз, записать полученные результаты, после чего определить, в какой доле случаев наблюдался желаемый исход. Этот экспериментальный метод позволя¬ ет оценить теоретическую частоту определенного результата. Когда число повторе¬ ний стремится к бесконечности, полученное нами отношение приближается к теоре¬ тическому, абстрактному значению, которое мы называем вероятностью рассматри¬ ваемого исхода. Вероятность — по сути, абстрактное понятие, в некотором смысле отражающее переход к пределу в процессе подсчета частот. При вычислении вероятностей главную роль играет правило Лапласа: «Вероятность события равна отношению числа благоприятных исходов к числу всех возможных исходов». Правило Лапласа позволяет пересечь границу, отделяющую мир случайностей от мира комбинаторики. Теперь, когда вы знакомы с понятием вероятности, мы мо¬ жем рассмотреть вопрос, заданный Паскалю шевалье де Мере. Шевалье изучил частоты связанных между собой событий, наблюдаемых при игре в кости. Однако де Мере не удалось разрешить следующий парадокс: ставить на то, что при четырех бросках кости хотя бы один раз выпадет шесть очков, выгодно, а ставить на то, что при 24 бросках двух костей хотя бы один раз выпадут две шестерки,— невыгодно. Наблюдение де Мере противоречило элементарной арифметике, так как шесть (число возможных исходов при броске кости) относится к четырем (столько раз мы 25
ПОСЧИТАЕМ! бросаем кость) как тридцать шесть (число возможных исходов при броске двух ко¬ стей) относится к двадцати четырем (столько раз мы бросаем две кости). Паскаль нашел решение, применив методы комбинаторики, о которых мы уже рассказали. Рассмотрим две описанные ситуации, применив правило Лапласа. В первом случае число возможных исходов равно 6 * 6 * 6 * 6 = 1296. Благопри¬ ятными будут те исходы, в которых шестерка выпадет как минимум один раз. Обра¬ тите внимание, что число благоприятных исходов равно 1296 минус число исходов, в которых 6 не выпадет ни разу. Подсчитать второе число нетрудно — оно равня¬ ется 5 * 5 * 5 • 5 = 625 (заметьте, что мы вновь применили правило умножения). Следовательно, вероятность того, что при четырех бросках кости хотя бы один раз выпадет 6, равна: 1296-625 1296 0,5177. Во втором случае будем рассуждать аналогичным образом. Вновь применив пра¬ вило умножения, получим, что число возможных исходов равно 3624, число благо¬ приятных исходов — 3624 — 3524. Следовательно, вероятность выигрыша в этом случае такова: 3624 - 3524 3624 0,4914. Эти расчеты показывают, что в первом случае делать ставку выгодно, а во вто¬ ром — нет. Шевалье де Мере, опытный игрок, благодаря своей интуиции почув¬ ствовал небольшое отклонение от равновесия (то есть от вероятности выигрыша или проигрыша, равной 50%), хотя здесь мы имеем дело с поистине астрономическими величинами. С помощью методов комбинаторики мы можем объяснить и еще один парадокс теории вероятностей, известный как парадокс Монти Холла. Впервые он проявился в 1963 году на американской телепередаче «Let’s make a deal», которую вел Монти Холл. Допустим, что нам предложили сыграть в следующую игру. Перед нами три закрытые двери. Мы знаем, что за одной из них скрывается весомый приз (напри¬ мер, автомобиль), за двумя другими ничего нет. В этих условиях, следуя интуиции, мы выбираем одну из дверей. Затем ведущий Монти Холл открывает одну из остав¬ шихся дверей, за которой не скрывается приз. Ведущий дает нам возможность из¬ 26
ПОСЧИТАЕМ! менять выбор. Как лучше поступить — стоит ли твердо придерживаться первона¬ чального выбора или же лучше сделать выбор заново, уже из двух вариантов? Интуиция подсказывает, что вероятность выигрыша не изменится: после того как ведущий открыл дверь, за которой ничего нет, закрытыми остались две двери, следовательно, приз с равной вероятностью находится за одной из них. Однако эти интуитивные рассуждения неверны: за дверью, которую открывает Монти Холл, никогда не будет приза, и это условие объясняет, почему наше предположение о рав¬ ной вероятности ошибочно. Рассмотрим задачу с помощью методов комбинаторики. Обозначим двери числа¬ ми 1, 2 и 3. Обратите внимание, что существует три разных способа выбрать дверь, за которой находится приз, и шесть способов выбрать дверь, за которой ничего нет. Иными словами, по правилу Лапласа вероятность выигрыша равна 1/3, но в боль¬ шинстве случаев (с вероятностью 2/3) нам не повезет, и мы останемся ни с чем. 1/3 2/3 I I В парадоксе Монти Холла вероятность угадать, за какой дверью находится приз, равна 1/3, вероятность проигрыша — 2/3. Следовательно, после того как Монти Холл откроет дверь, в 6 случаях из 9 вы¬ годно сменить выбор, в 3 случаях из 9 — нет. Здесь важно то, что Монти Холл обя¬ зательно откроет дверь, за которой ничего нет, и эту информацию нужно каким-то образом использовать. Теория вероятности подсказывает: если мы хотим выиграть, лучше сделать выбор заново. Как уже понял читатель, этот парадокс скрывает в себе интересный вопрос, вы¬ ходящий далеко за рамки телеконкурсов. Представьте, что мы хотим узнать, с какой вероятностью сегодня пойдет дождь. При этом мы знаем, что погода в последние 27
ПОСЧИТАЕМ! дни была дождливой. Существует некая априорная информация о событии, которая влияет на его результат. Это же происходит и в примере с парадоксом Монти Холла. Теория условных вероятностей нашла отражение в теореме Байеса, названной в честь священника Томаса Байеса (1702—1761), который первым изучил этот во¬ прос. На основе его идей позднее были созданы метод байесовского вывода и ста¬ тистические оценки, которые по известным исходным данным позволяют оценить, какое значение с наибольшей вероятностью будет следующим. Эти идеи применя¬ ются в самых разных областях, в частности в финансах (при оценке курса акций по известным котировкам последних недель), при обработке сигналов (при восста¬ новлении цифровых сигналов с помощью фильтров) или изучении динамики популя¬ ций (при оценке численности популяций по известным данным прошлых периодов). Викторину Монти Холла можно назвать азартной игрой. Как вы увидели, уме¬ ние точно производить необходимые подсчеты дает некоторое преимущество и по¬ зволяет принимать более обоснованные решения. Существуют распространенные заблуждения, связанные с азартными играми, которые нетрудно развенчать с по¬ мощью простых математических рассуждений. Рассмотрим в качестве примера еженедельную лотерею. Многие верят, что одни и те же числа не могут выпасть две недели подряд, а если это и произойдет, то бу¬ дет чем-то из ряда вон выходящим. Это вовсе не так — вероятность того, что одно и то же число выпадет две недели подряд, либо того, что во вторую неделю выпадет любое другое заданное число, одинакова! Рассмотрим простой пример. Допустим, что мы играем в лотерею, где нужно выбрать число от 00 000 до 99 999. Допустим, что мы выбрали число 45567. Какой будет вероятность выигрыша? Вновь приме¬ нив правило Лапласа, получим, что искомая вероятность будет равна 1 100 ооо’ так как благоприятным для нас будет только один исход, а всего возможных исхо¬ дов будет столько же, сколько чисел заключено на интервале от 00 000 до 99 999 (включая границы). Какой будет вероятность выигрыша на следующей неделе, если мы поставим на это же число? Количество благоприятных и возможных исходов останется таким же, следовательно, вероятность выигрыша не изменится! Иными словами, игра не имеет памяти. В теории вероятностей этот принцип называется 28
ПОСЧИТАЕМ! принципом независимости. Он означает, что результаты двух экспериментов, про¬ веденных в одинаковых условиях, никак не влияют друг на друга. Принцип неза¬ висимости применим ко многим азартным играм. Кроме того, изложенные выше рассуждения позволяют показать: не существует каких-либо выгодных комбинаций, помогающих выиграть в азартной игре. В описанной лотерее число 00 001 выпадет с той же вероятностью, что и любое другое, более для нас привлекательное, напри¬ мер 48756. «Красота» чисел никак не влияет на вероятность. РУЛЕТКА, ИЛИ КАК СОРВАТЬ БАНК В КАЗИНО Рулетка - одна из самых популярных игр, которая, к тому же, имеет самую давнюю историю из всех игр казино. Колесо рулетки вращается в горизонтальной плоскости вокруг своей оси и разделено на 37 секторов, раскрашенных в красный и черный цвет и пронумерованных от 0 до 36 в случайном порядке. Крупье бросает шарик в направлении, противоположном направле¬ нию вращения рулетки. Совершив несколько оборотов по колесу, шарик падает в один из сек¬ торов, который и будет выигрышным. При игре в рулетку допускается множество разных ставок и комбинаций (четные сектора, красные сектора и так далее). Следовательно, заранее пред¬ сказать, в какой сектор упадет шарик, невозможно. В большинстве случаев выигрывает казино. Тем не менее члены одной испанской семьи, клана Пелайо, стали всемирно известными по¬ сле того, как им удалось выиграть весьма внушительные суммы в рулетку в самых разных казино мира. В основе их стратегии лежит следующая идея: поскольку колесо рулетки - материальный объект, оно не может быть идеальным (ось вращения будет располагаться не совсем ровно, колесо будет не вполне уравновешено и так далее). Если определить эти неточности эмпири¬ чески, можно предугадать, в какие сектора шарик будет падать с чуть большей вероятностью, чем указывает теория. Применив свои идеи, члены клана Пелайо стали грозой для всех игорных домов. К сожалению нынешних игроков, сегодня столы для игры в рулетку регулярно меняются, поэтому любые стратегии, основанные на статистике, теряют эффективность. Естественное желание сыграть в азартную игру вызвано возможностью полу¬ чить определенную сумму. Но перед тем как ставить на кон наши заветные денеж¬ ки, заработанные потом и кровью, следует сопоставить возможный выигрыш с его вероятностью и оценить потенциальные потери. Проще говоря, мы делаем ставку потому, что существует вероятность выигрыша. В некоторых случаях ставить вы- 29
ПОСЧИТАЕМ! годнее, чем в других. Чтобы определить такие случаи, одной вероятности недоста¬ точно — необходимо вычислить так называемое математическое ожидание. Рассмотрим следующую игру, совершенно не увлекательную и не заниматель¬ ную, которая, однако, поможет объяснить смысл математического ожидания про¬ стым языком. Допустим, что у нас есть два идеально сбалансированных игральных кубика, то есть вероятность выпадания любой грани при броске равна 1/6. Если на обоих кубиках выпадает одинаковое число очков, мы получаем 4 евро, в против¬ ном случае проигрываем 1 евро. Мы не знаем, обманывают ли нас устроители игры: при благоприятном исходе мы получаем сравнительно много, а в случае проигрыша теряем лишь небольшую часть возможного выигрыша. При броске двух кубиков возможны 36 различных вариантов (6 исходов броска первого кубика и 6 исходов броска второго кубика дают 6 • 6 = 36 возможных исходов). Только в 6 из них на обоих кубиках выпадет одинаковое число очков, таким образом, в 6 из каждых 36 случаев мы будем выигрывать 4 евро, а в остальных случаях будем проигрывать 1 евро. Ожидаемый выигрыш рассчитывается как взвешенная сумма вероятностей выигрыша и проигрыша. В нашем случае ожидаемый выигрыш равен: Следовательно, участвовать в игре невыгодно, так как ожидаемый выигрыш от¬ рицателен. Если же в случае благоприятного исхода мы выиграем не 4 евро, а 30, то математическое ожидание будет равно: В этой ситуации играть выгодно, так как высокий выигрыш компенсирует малую вероятность выпадания двух одинаковых значений. Все эти идеи реализуются в классической европейской лотерее «Евромиллио¬ ны». Стоимость билета в ней равна 2 евро, делая ставку, нужно выбрать пять чисел из 50 возможных, а также еще два числа из девяти дополнительных («звезд»). По¬ рядок выбора не имеет значения, важно лишь то, какие именно числа выберет игрок. 30
ПОСЧИТАЕМ! Применив правила, связанные с перечислениями, в которых порядок следования элементов не важен, получим, что общее число вариантов равно: (50) (9) I5/ = 76 275 360. Следовательно, вероятность выиграть первый приз очень мала — 1 к 76 275 360. Не существует магического рецепта выигрыша в лотерею, а вероятность угадать вы¬ игрышную комбинацию чаще всего минимальна, что подтверждают расчеты. Не¬ смотря на это в некоторых случаях стоит рискнуть небольшой суммой, чтобы полу¬ чить шанс немного подзаработать. В ноябре 2006 года главный приз лотереи «Евромиллионы» составил 180 мил¬ лионов евро. Вероятность выигрыша была очень мала, однако устоять перед огром¬ ными деньгами смогли немногие. Вычислим математическое ожидание для этой ло¬ тереи на основе приведенных выше значений. Учитывая число возможных исходов (76275360) и число благоприятных исходов (1), имеем, что ожидаемый выигрыш равен: 180 000 000 ^ 2 • 76 275 359 = 0,3598708941. 76 275 360 76 275 360 Это положительное число, а поскольку главный приз огромен, то можно потратить 2 евро, чтобы попытать счастья. Хотя математики имеют очень четкое представле¬ ние обо всем, что связано с азартными играми, и часто говорят, что «лотерея — это налог на тех, кто плохо знает математику», в этом случае люди, способные сделать необходимые расчеты, получают некоторое преимущество. Математическое ожидание позволяет описать случайное событие лишь частично, но во многих случаях оно дает достаточно интересную информацию для понима¬ ния природы изучаемого события. Как вы узнаете из следующих глав, различные методы теории вероятностей помогают получить намного больше информации, чем может показаться. Они указывают на тесную связь комбинаторики с теорией веро¬ ятностей и помогают обосновать удивительные результаты с помощью остроумных методов и нестандартных идей. 31
ПОСЧИТАЕМ! ФОРМАЛЬНОЕ ОПРЕДЕЛЕНИЕ МАТЕМАТИЧЕСКОГО ОЖИДАНИЯ Вновь вернемся к математике и языку. Допустим, что в результате некоторого эксперимента мы можем получить N различных чисел xlf х2,xN. Вероятность, с которой выпадет результатxv равна pv вероятность получить результат х2 - р2 и так далее до N. Математическое ожидание результата нашего эксперимента определяется как средневзве¬ шенное значение всех возможных результатов. Весом каждого результата будет соответству¬ ющая вероятность. Иными словами, математическое ожидание определяется как следующая сумма: N р,х, + р2х2 + р3х3 +... + pNxN = £р,.х, . /-1 Обратите внимание, что если вероятность всех результатов одинакова, то Pj- р2 - ... - pN - - 1 /А/, и математическое ожидание будет равно среднему арифметическому значению всех возможных результатов. Математическое ожидание следует рассматривать как среднее ариф¬ метическое значение (предоставляющее частичную информацию о рассматриваемом экспери¬ менте), в котором различные значения имеют тот или иной вес в зависимости от их вероятности. 32
Глава 2 Графы и карты Углерод — основа жизни на Земле. Он содержится во всех живых организмах, от простейших бактерий и до огромных млекопитающих. Он настолько широко распространен в природе, что различные соединения атомов углерода между со¬ бой и с атомами других элементов изучает отдельный раздел науки — органиче¬ ская химия. Изучение углерода играет важнейшую роль в фармакологии, биохимии и различных отраслях промышленности. К примеру, путем фракционированной конденсации нефти получаются вещества, необходимые для современного обще¬ ства, в частности бензин и газ бутан. Особенно важно такое семейство органических соединений, как алифатические соединения, в которых атомы водорода и углерода соединяются между собой одинарными, двойными и тройными связями, образуя древовидную структуру без циклов. Ненадолго сменим тему. Каждый из нас слышал о теории эволюции живых существ, созданной Чарльзом Дарвином по результатам наблюдений, которые он произвел в самых разных уголках земного шара во время путешествия на корабле «Бигль» («Ищейка»). Много лет спустя полученные Дарвином результаты легли в основу книги «Происхождение видов», вокруг которой развернулись жаркие спо¬ ры, так как новая теория была совершенно неслыханной для своего времени. В этой книге описывается один объект, весьма интересный для нашего обсуждения,— эво¬ люционное дерево, или дерево жизни. Это дерево имеет сложную структуру и стро¬ ится следующим образом. Рассмотрим множество разных видов и на основе раз¬ личных критериев объединим в группы те виды, которые больше всего схожи между собой. Повторим этот процесс несколько раз, пока все изучаемые виды не окажутся причисленными к той или иной группе. Результатом этого процесса будет эволю¬ ционное, или филогенетическое дерево, отражающее степень родства между более или менее похожими видами. Подобные методы можно применить, к примеру, для анализа родства между живыми организмами, обитающими в некотором регионе, или для того, чтобы продемонстрировать эволюцию Homo sapiens как вида. Читатель наверняка задается вопросом: почему в книге, посвященной матема¬ тике, мы вдруг заговорили об органических молекулах и филогенезе, ведь ими за- 33
ГРАФЫ И КАРТЫ нимаются химия и теория эволюции? Чтобы немного успокоить читателя, далее мы покажем, что эти две дисциплины, подобно многим другим, имеют намного больше общего с комбинаторикой, чем может показаться на первый взгляд. Во многих слу¬ чаях математика описывает абстрактные представления реальных объектов. Это же происходит и в двух представленных выше примерах, так как структура насыщен¬ ных углеводородов и филогенетических деревьев по сути одинакова. Структура органической молекулы и эволюционное дерево, изображенное Чарльзом Дарвином, очень похожи. Глядя на эти иллюстрации, нетрудно заметить, что изображенные на них объекты имеют древовидную структуру. Дерево в комбинаторике — это не молекула и не рас¬ тение, а абстрактная структура, которая применяется множеством способов в реаль¬ ной жизни (в химии, таксономии и так далее), в теоретической информатике (в ба¬ зах данных и алгоритмах принятия решений) и, кроме того, сама по себе обладает интересными математическими свойствами. На основе интуитивных представлений, которые опираются на результаты экс¬ периментов и рассуждения, будем строить абстрактные модели, объясняющие изу¬ чаемые явления хотя бы частично. Любопытно, что многие проблемы из совершенно разных областей описываются одинаковыми математическими моделями (как в уже приведенных нами примерах). Подобное явление часто наблюдается в комбинато¬ рике, и в особенности в теории графов: с помощью дискретных структур, о которых мы еще поговорим, можно смоделировать отношения между людьми, социальные сети, распространение заболеваний, структуру молекул, системы водоснабжения и многое другое. Начнем с определения графа — фундаментального понятия дис¬ 34
ГРАФЫ И КАРТЫ кретной математики и комбинаторики. Как вы увидите, графы описываются исклю¬ чительно с помощью множеств. Далее мы покажем, что при изображении графов на бумаге возникает более жесткая структура, которая называется отображением и обладает многими интересными свойствами. Для простоты и наглядности отобра¬ жения также называют картами. Впервые карты описал один из величайших специ¬ алистов по комбинаторике XX века Уильям Татт. Цель формального определения этих объектов — более строгое изучение одной из важнейших задач XX века — задачи о четырех красках. После того как мы разберемся, что такое граф и карта, перейдем к изучению деревьев и покажем, что они в действительности играют клю¬ чевую роль при анализе более сложных комбинаторных объектов. Мы расскажем о древних тибетских играх, задачах о треугольниках и о числах, сокрытых в природе. Математика правит миром. Графы и карты Основными понятиями этой главы станут «граф» и «карта». Прежде чем дать им четкие определения, расскажем о графах и картах в общих чертах. Представьте себе место, где вы живете, будь то большой город и маленький поселок. Рядом с ним, скорее всего, будет находиться множество других населенных пунктов, между которыми проложены автомобильные дороги. Из одного города в другой можно добраться либо напрямую, либо через какой-то другой город, или даже проехать по мосту, проходящему над другой дорогой. Следовательно, можно ввести понятия связности городов и планарности дорожной сети. Связность указывает, можем ли мы проехать из одного города в другой напрямую, а планарность означает, что до¬ рожная сеть не содержит мостов. Графы отражают идею связности: помеченный граф — это структура, опреде¬ ляемая вершинами (точками), которым присвоены определенные метки. Вершины графа связаны отношениями смежности. Графы, как правило, изображаются в виде множества точек плоскости (и соответствующих меток). Вершины графа соеди¬ няются линиями, или ребрами, тогда и только тогда, когда являются смежными. По этой причине граф С обычно обозначается С = (V, А), где V — множество 35
ГРАФЫ И КАРТЫ вершин, А — множество ребер. Заметьте, что форма ребер графа не имеет значе¬ ния — важно лишь то, какие вершины соединяются между собой. Также обычно говорят о непомеченных графах, которые получаются из помечен¬ ных путем удаления меток. Непомеченный граф представляет собой скелет из ребер и вершин. В зависимости от контекста читатель поймет, о каких графах мы будем говорить далее — о помеченных или непомеченных. Один и тот же граф, изображенный двумя разными способами. Заметьте, что в обоих случаях в каждую вершину входит одинаковое число ребер. Обратите внимание, что на рисунках выше один и тот же граф представлен дву¬ мя принципиально разными способами: на первой иллюстрации мы использовали прямые линии, на второй — кривые. Также важно отметить, что на первом рисунке ребро, соединяющее вершины 5 и 7, пересекает ребро, соединяющее вершины 2 и 3, а на втором рисунке ребра графа не пересекаются между собой. Таким образом, если бы первый граф представлял собой сеть автодорог, нам пришлось бы построить мост, без которого на самом деле можно обойтись (что показывает второй граф). Представления графов на плоскости без пересечения ребер интересны сами по себе. Такое представление (граф может быть помеченным или непомеченным в зависимости от контекста), когда ребра графа пересекаются только в вершинах, называется картой. Изображение графа на плоскости в математике называется вло¬ жением — это понятие обозначает отображение одного объекта на другой. На ил¬ люстрации выше справа определена карта, слева — нет. Один и тот же граф можно представить в виде нескольких карт, соответствующих различным вложениям графа в плоскость. Это объясняется тем, что графы состоят из вершин и ребер между ними, а карты, помимо этого, содержат дополнительную структуру — области, на кото¬ 36
ГРАФЫ И КАРТЫ рые делится плоскость. Эти области называются гранями карты. Следовательно, карты — более жесткие структуры, чем графы, и при их изучении необходимо учи¬ тывать множество особых аспектов. Рассмотрим пример, чтобы прояснить смысл этих понятий. На рисунке изобра¬ жен один и тот же граф, вложенный в плоскость двумя разными способами. Ре¬ зультатом двух разных вложений будут две разные карты: на первой внешняя грань определяется вершинами 6, 3, 7, 5, 4,1, 5, 6 (против часовой стрелки) и ограничена семью ребрами. Вторая карта не содержит ни одной грани, ограниченной таким же количеством ребер. Два вложения одного и того же графа в плоскость определяют две разные карты. История возникновения понятия «граф» подробно описана: графы ввел Леонард Эйлер в 1736 году при решении знаменитой задачи о мостах Кёнигсберга. Понятие «карта», представляющее, по сути, изображение графа, появилось значительно поз¬ же, и его происхождение не столь известно. Формальное определение этого понятия дал математик Джек Эдмондс, первым, кто изучил карты с помощью количествен¬ ных методов, был Уильям Татт,— этот химик, очарованный красотой математики, сыграл важную роль во взломе нацистских шифров во время Второй мировой войны. Уильям Татт родился в английском городе Ньюмаркет в 1917 году. Его отец был садовником, мать — домохозяйкой. Уже в начальной школе он продемонстриро¬ вал немалые способности к наукам, в особенности к химии. Окончив школу, Татт продолжил заниматься химией в Кембриджском университете. Однако его интерес к математике только возрастал, и он часто посещал многочисленные встречи мате¬ 37
ГРАФЫ И КАРТЫ матиков знаменитого кембриджского Тринити-колледжа. Именно в то время в ходе жарких споров Татт вместе с еще тремя многообещающими математиками, Ролан¬ дом Бруксом, Артуром Стоуном и Седриком Смитом, решил задачу о квадрирова- нии квадрата. Задача звучала так: какую целочисленную длину могут иметь стороны квадрата, который можно разбить на несколько квадратов разного размера? Хотя Татт и его соавторы из Тринити-колледжа были еще студентами, они смогли решить задачу, применив рассуждения, связанные с электротехникой. Позднее на основе этих идей была создана так называемая теория потоков в графах. Позднее эта четверка про¬ должила совместную работу над решением задач и подписывала свои работы псев¬ донимом Бланш Декарт. Корректное квадрирование квадрата: все маленькие квадраты имеют разные размеры. К тому моменту уже началась Вторая мировая, и Уильям Татт вовсю занимался химическими исследованиями. Его руководитель заметил, что Татт с его превосход¬ ным абстрактным мышлением мог бы принести пользу британским вооруженным силам и помочь в расшифровке секретных шифров противника. Татт вместе с други¬ ми крупными британскими математиками был направлен в Блетчли-парк, также из¬ вестный как Station X, для перехвата и расшифровки сообщений немецких войск. Именно в Блетчли-парке был взломан код «Энигмы» — возможно, самый извест¬ 38
ГРАФЫ И КАРТЫ ный шифр Второй мировой войны, о котором написано немало книг. Так в январе 1941 года Уильям Татт стал аналитиком на службе союзников и добился впечатляю¬ щих результатов. В официальном указе о присуждении Татту ордена Канады в 2001 году говорилось: «...Этот юный математик и дешифровщик взломал ряд шифров немецкой ар¬ мии, известных под общим названием FISH, что стало одним из величайших интеллектуальных достижений Второй мировой войны...» Некоторые документы, касающиеся этих шифров, засекречены до сих пор, так как содержат военную тайну. Первые сообщения типа FISH попали в распоряжение исследователей Блетчли-парка после перехвата радиообмена между Афинами и Ве¬ ной в 1941 году. 30 августа того же года, после того как была перехвачена дублиро¬ ванная передача одного и того же сообщения, исследователи получили необходимые данные для начала анализа и дешифровки. Взяв эти два сообщения за основу, Татт приступил к поиску закономерностей. Он обнаружил, что шифровальная машина содержала два колеса с 41 и 31 зубцом. В ходе совместной работы с другими иссле¬ дователями ученый понял, что шифровальная машина содержала в общей сложности 12 колес, и постепенно восстановил полный алгоритм шифрования. Это был титани¬ ческий труд — не будем забывать, что в руках у союзников находилось считанное количество зашифрованных сообщений! Уильям Татт и фасад Блетчли-парка. 39
ГРАФЫ И КАРТЫ Татт не только изучил структуру шифров FISH, но и описал алгоритмы их рас¬ шифровки. Позднее эти алгоритмы были успешно реализованы в компьютере «Ко¬ лосс», созданном специально для взлома шифров противника. Обратите внимание, что описываемые события происходили в 1940-е годы, а следовательно, «Колосс» можно считать прадедушкой современных компьютеров. В Блетчли-парке были со¬ вершены поистине удивительные открытия, которые позднее сыграли важнейшую роль в криптографии, теории алгоритмов и проектировании первых компьютеров. Хотя за работу над проектом многие исследователи, в частности Алан Тьюринг, были удостоены различных наград и почестей, общество обошло вниманием заслуги Татта в криптографии. Он стал широко известен лишь много лет спустя, уже в Канаде, когда занялся теорией графов и комбинаторикой. В рамках своих исследований Татт попытался решить проблему четырех красок, применив исключительно количественный под¬ ход. Напомним, что проблема четырех красок звучит так: сколькими красками мож¬ но раскрасить данную карту так, чтобы любые две области, имеющие общий участок границы, были раскрашены в разные цвета? Доказать, что пяти красок достаточно, ПРОИСХОЖДЕНИЕ ГРАФОВ: ПРОГУЛКИ ПО КЁНИГСБЕРГУ В большинстве случаев нельзя с точностью определить, когда именно была создана та или иная научная дисциплина. Теория графов - исключение из этого правила: дата, когда на свет появился этот раздел математики, хорошо известна. В 1736 году в Кёнигсберге (ныне Кали¬ нинград) была предложена задача, решить которую, казалось, было невозможно: никто не мог совершить прогулку по городу так, чтобы пройти по всем мостам через реку Преголя только один раз и вернуться домой. Леонард Эйлер предложил упрощенную модель города, состоявшую из вершин и ребер, где ребрами обозначались мосты, соединявшие разные части города. Путем несложных действий над полученным графом Эйлер объяснил, почему искомого маршрута не существует, и дал начало новому разделу математики. План Кёнигсберга и семи его мостов в 1652 году. 40
ГРАФЫ И КАРТЫ вовсе не трудно, однако показать, что можно обойтись четырьмя красками, неверо¬ ятно сложно — искомое доказательство получили Кеннет Аппель и Вольфганг Ха- кен в 1976 году с помощью компьютера. Татт не смог решить проблему четырех красок, однако попытался подсчитать, сколько карт можно раскрасить четырьмя и пятью красками, и сравнить полученные величины. В этих работах он первым при¬ менил методы комбинаторики для изучения карт. Рассмотрим подробнее тесную взаимосвязь между графами и картами. Есте¬ ственно, возникает вопрос: когда данный граф можно представить в виде карты, то есть изобразить на плоскости так, чтобы его ребра не пересекались? Если граф допускает такое представление, он называется планарным. В первом примере, при¬ веденном в этой главе, мы сначала изобразили граф так, что его ребра пересекались, но затем смогли перерисовать его без самопересечений. Следовательно, приведен¬ ный нами граф был планарным, так как допускал изображение без самопересечений. Возникает еще один вопрос: существуют ли какие-то свойства, позволяющие одно¬ значно определить планарность графа? Этот вовсе не тривиальный вопрос стал од¬ ним из первых в топологической теории графов. Такие свойства действительно су¬ ществуют и определяются особыми внутренними структурами графа, которые на¬ зываются минорами. Минор графа строится следующим образом: объединим в группы вершины, свя¬ занные между собой, после чего рассмотрим смежность различных групп (см. ри¬ сунок ниже). Минор определяется как граф, вершинами которого будут эти группы (серые пятна, содержащие вершины), а ребра будут указывать смежность групп. На рисунке представлено построение минора указанным способом. Гоаф и один из его миноров. 41
ГРАФЫ И КАРТЫ В теории графов выделяются особые графы, играющие очень важную роль и удо¬ стоенные за это особого названия. Именно о них пойдет речь в следующей задаче. В ней рассматриваются два графа, изображенные на рисунке ниже: граф с пятью вершинами, между которыми проведены все возможные ребра (такой граф назы¬ вается полным и обозначается К5), и граф с шестью вершинами и девятью ребрами (обозначается К33). Если читатель попытается изобразить эти графы на плоскости так, чтобы их ребра не пересекались, то убедится, что это невозможно. Также мож¬ но показать, что эти графы можно изобразить требуемым образом, если удалить одно из ребер. Два приведенных графа являются наименьшими (по числу вершин) непланарными графами. Полный граф с пятью вершинами К5 и двудольный граф К3 3. Путем элементарных рассуждений можно показать, что эти графы не являются планарными. Однако по-настоящему удивительно то, что верно и обратное: если два приведенных выше графа не являются минорами данного графа, то он планар¬ ный. Этот результат, занимающий особое место в теории графов, получил польский математик Казимир Куратовский (1896—1980), ярчайший представитель польской математической школы начала XX века. Теорема Куратовского гласит: «Граф планарен тогда и только тогда, когда его минорами не являются К33 или К5». Интересно отметить следующее: топологическое свойство планарности (оно за¬ висит от особенностей поверхности, на которой мы изображаем граф) можно опре¬ делить только с помощью терминов теории множеств (так как минор определяется исключительно через отношения смежности). Следовательно, это свойство прису¬ 42
ГРАФЫ И КАРТЫ ще самому графу, а не способу его изображения на плоскости. Также отметим, что столь сложная задача, как изображение произвольного графа без самопересечений, сводится к обнаружению в нем двух приведенных выше структур. Теорема Куратов- ского — лишь вершина огромного айсберга, которому уделяют основное внимание большинство специалистов по комбинаторике и алгоритмам в теории миноров. Семейство планарных графов называется минорно-замкнутым — это означает, что любой минор планарного графа также является планарным. Этот результат на¬ прямую следует из приведенного выше определения минора. Теорема Куратовско- го гарантирует, что единственной характерной особенностью всех без исключения планарных графов является отсутствие в них двух непланарных графов. Верно ли, что в общем случае любое минорно-замкнутое семейство графов характеризуется ПРОМЫШЛЕННОЕ ПРИМЕНЕНИЕ ПЛАНАРНОСТИ ГРАФОВ Определение планарности графа играет крайне важную роль в промышленности. В электро¬ технике необходимо уметь реализовывать ту или иную модель максимально простым способом, так как с ростом сложности возрастают и затраты на изготовление модели. В частности, после того как определена модель цепи, которую необходимо реализовать, следует установить, мож¬ но ли представить эту цепь на плоской печатной плате. Если реализовать цепь на плоскости без самопересечений невозможно, то стоимость изготовления платы возрастет, так как она будет содержать уже не один, а несколько слоев. Учитывая, что объемы производства плат составляют миллионы экземпляров, изучение планарности электрических цепей играет решающую роль при оптимизации затрат. Существуют компьютерные программы, позволяющие определить, допускает ли заданная модель представ- ление на плоскости, и оптимизировать конфигурацию соответствующей печат¬ ной платы. 43
ГРАФЫ И КАРТЫ конечным множеством «запрещенных» графов? Этот вопрос, названный гипотезой Вагнера, крайне сложен. На него был дан положительный ответ: любое минорно¬ замкнутое семейство графов характеризуется конечным множеством исключенных миноров. Доказательство гипотезы Вагнера занимает важное место в теории графов второй половины XX века. Нил Робертсон и Пол Сеймур заложили основы этой математической теории в титанической серии книг, содержащей более двадцати то¬ мов (все они носят название «Graph Minors» и обозначены соответствующими рим¬ скими цифрами). Этот монументальный труд имеет огромное значение в современ¬ ной теории графов и лежит в основе большей части исследований в этой дисциплине. Результатом совместной работы Робертсона и Сеймура стала следующая теорема, названная их именами: «Рассмотрим бесконечное множество графов. На этом множестве существует два таких графа, что один из них будет минором другого». Теория Робертсона и Сеймура сыграла важную роль в изучении структуры гра¬ фов, и сегодня ей посвящены наиболее активные исследования в комбинаторике и алгоритмах, связанных с теорией графов. Несколько примеров посложнее Чтобы лучше понять, как производятся расчеты в некоторых семействах графов и карт, сделаем небольшую паузу и опишем ряд новых методов, которые помогут нам решать задачи посложнее, чем изложенные выше. Рассмотрим один очень про¬ стой и в то же время весьма наглядный пример. Напомним, что мы описали понятие перестановки и научились подсчитывать чис¬ ло перестановок множества из п элементов. Это число равно п! и определяется как произведение всех натуральных чисел, меньших либо равных п, начиная с единицы. Допустим, нам нужно вычислить значение 120!. Для этого потребуется найти про¬ изведение всех натуральных чисел от 1 до 120. Аналогично, если нам нужно вычис¬ лить значение 119!, потребуется найти произведение тех же чисел, за исключением 120. Обратите внимание, что выполняется соотношение: 120! = 120 • 119!. Что это значит? Если мы уже вычислили значение 119! и записали его, то вычислить 120! по этому соотношению будет нетрудно. Иными словами, мы можем использовать 44
ГРАФЫ И КАРТЫ рекурсивное определение факториала и выполнить необходимые расчеты на основе промежуточных результатов, не вычисляя произведение всех множителей. Это правило очень часто применяется в комбинаторике в расчетах разной слож¬ ности. Еще один пример. Подсчитаем, сколько слов длины п можно составить из букв а и Ь. Обозначим искомое число слов через Р . Это число рассчитывается как число размещений с повторениями. Число слов длиной п будет равно 2П. За¬ пишем Рп = 2". Обратите внимание: чтобы получить любое слово длиной п, нужно приписать букву а или b к слову длиной гг — 1. Имеем рекурсивное соотношение Р = 2 • Р у которое позволяет понять комбинаторную природу задачи. Результат подобных рассуждений — уравнения нового типа, так называемые рекуррентные уравнения. Описанный пример можно было бы решить иначе, однако в других за¬ дачах обойтись без рекуррентных уравнений нельзя. Рассмотрим случай посложнее. Игру «Ханойские башни» изобрел французский математик Эдуард Люка (1842, Амьен — 1891, Париж) в 1883 году. Основана она на древней восточной легенде, описывающей конец света. Чтобы проверить кре¬ пость духа новых жрецов священной гробницы, старейшины предложили им задачу: они разместили 64 кольца разного размера по порядку от меньшего к большему, как показано на рисунке. Цель игры — переместить все кольца на новый стержень, причем на каждом ходу можно перемещать только одно кольцо. Кроме того, нельзя помещать кольцо поверх кольца меньшего размера. При решении головоломки можно использовать промежуточный стержень для вспомогательных перемещений. Исходное положение колец в игре«Ханойские башни» с восьмью кольцами, а также промежуточное и финальное положение. р^>l- 45
ГРАФЫ И КАРТЫ Необходимо найти минимальное число ходов, за которое можно решить задачу. Будем рассуждать просто. Пусть Тп — искомое число ходов для п колец. Ключе¬ вую роль играет следующее наблюдение: чтобы переместить п колец из начального положения в конечное, сначала нужно переместить гг — 1 кольцо на промежуточный стержень, затем переместить самое большое кольцо в конечное положение, после чего снять п — 1 кольцо с промежуточного стержня. Число ходов, которое нужно совершить, равно Tn _ t + 1 + Тл _ у нам потребуется Тл _ t ходов, чтобы переместить п — 1 верхнее кольцо на промежуточный стержень (самое большое кольцо будет оставаться неподвижным), один ход, чтобы поместить большое кольцо в конечное положение, и, наконец, Тл _ t ходов, чтобы переместить в конечное положение п — 1 верхнее кольцо. Обратите внимание: главное — оставить на месте большое кольцо, так как поверх него всегда можно поместить любые кольца меньшего размера. Мы получили рекуррентную зависимость Тл = 2Тл _ х + 1 при Тх = 1 (в случае с одним кольцом головоломка тривиальна и решается в один ход). Найдем формулу для расчета 7\ Последовательность значений Тп имеет вид 1, 3, 7, 15, ... Внима¬ тельно изучив первые числа, можно предположить, что Тп = 2Л — 1. Это действи¬ тельно так: эта формула верна для п = 1, и, кроме того, выполняется соотношение 2Л —1 = 2 (2Л_1 — 1) +1, что совпадает с предложенной выше рекуррентной формулой Тп = 2Tn _ t + 1. Подставив в эту формулу значение п = 64, получим, что юным монахам потре¬ буется совершить 264—1 = 18 446 744 073 709 551615 ходов — поистине непосиль¬ ная задача! В завершение нашего путешествия в мир рекуррентных формул рассмотрим классическую задачу, известную еще в эпоху Возрождения. Начав с двух единиц, построим числовую последовательность так, чтобы каждый ее член был равен сумме двух предыдущих. Третий элемент последовательности будет равен 1 + 1 = 2, чет¬ вертый — 1 + 2 = 3, пятый — 2 + 3 = 5 и так далее. Первые члены последователь¬ ности будут такими: 1,1, 2, 3, 5, 8,13, 21, 34... 46
ГРАФЫ И КАРТЫ Эта знаменитая последовательность называется последовательностью Фибонач¬ чи в честь первооткрывателя — средневекового итальянского мыслителя Леонардо Пизанского, сына Боначчи (отсюда и прозвище Фибоначчи). Числа Фибоначчи рассчитываются по рекуррентной формуле следующим образом. Обозначим через Fn п-й член последовательности. Будет выполняться следующее рекуррентное со¬ отношение: Интересно, что на создание этой последовательности чисел Фибоначчи вдохно¬ вила любопытная задача, связанная с динамикой популяций: пара кроликов, начиная со второго месяца жизни, ежемесячно приносит пару кроликов, которые, начиная со второго месяца жизни, также ежемесячно приносят пару кроликов, и так далее. Каким будет число кроликов по прошествии определенного времени? Решением ЭДУАРД ЛЮКА И ЧИСЛА ФИБОНАЧЧИ Французский математик Эдуард Люка (1842, Амьен - 1891, Париж) большую часть жизни проработал в Па¬ риже, сначала в местной обсерватории, а затем в двух институтах - лицее Людовика Великого и лицее Карла Великого. В его самых известных математических трудах рассматриваются числовые последовательности, близкие к числам Фибоначчи. Люка заметил, что многие свойства чисел Фибоначчи при изменении начальных условий со¬ храняются (напомним, что первые два числа Фибоначчи принимаются равными единице). Существует особая чис¬ ловая последовательность, названная в его честь, - числа Люка, которые определяются подобно числам Фибоначчи, однако первые два числа этой последовательности равны 2 и 1. Числа Фибоначчи и схожие последовательности общего вида - не просто математическая диковинка. Существует особый научный журнал под названием The Fibonacci Quarterly, где пу¬ бликуются результаты, связанные с этими замечательными числами. 47
ГРАФЫ И КАРТЫ этой задачи является последовательность Фибоначчи. Важно, что этот ряд чисел бесконечно возрастает (поскольку определяется как сумма целых положительных чисел), а отношение двух соседних чисел Фибоначчи всегда различно и стремится к следующему значению: — = 1,625, — = 1,615384615, — = 1,619047619. 8 13 21 Отношение последовательных чисел Фибоначчи стремится к так называемому золотому числу, описывающему золотое сечение: -^^ = 1,618033988... 2 Именно этот коэффициент описывает рост численности популяции кроликов в задаче Леонардо Пизанского. Это же соотношение удивительным образом воз¬ никает и во многих других контекстах: оно описывает ветвление деревьев, форму раковин моллюсков и рост численности определенных популяций. Природа подчи¬ няется определенным правилам, а рост биологических структур описывается четко определенными закономерностями. Можно сказать, что природа «выбрала» это число за гармоничность и совершенство, хотя истинные причины носят куда более сложный и прозаический характер. Они относятся к геометрии, и мы не будем оста¬ навливаться на них подробнее. Именно в силу этой гармонии художники, архитекторы и музыканты использо¬ вали так называемую божественную пропорцию в своих произведениях. Гармонич¬ ность золотого сечения проявляется во множестве архитектурных шедевров (в част¬ ности, в афинском Парфеноне), в предметах, с которыми мы сталкиваемся каждый день (например, в кредитных картах и пластиковых удостоверениях личности), и других творениях человеческих рук. Мы подробно рассмотрим всего один при¬ мер — картину «Третье мая 1808 года в Мадриде» великого Франсиско Гойя. Глав¬ ный герой картины, повстанец, которого вот-вот расстреляют, находится в точке, определяемой четырьмя прямоугольниками, стороны которых описываются золо¬ тым сечением. 48
ГРАФЫ И КАРТЫ Художественные каноны часто описываются золотым сечением. Примером этому служит картина «Третье мая 1808 года в Мадриде»» Франсиско Гэйя. Метод двойного подсчета В комбинаторике часто случается так, что очень простые идеи приводят к совер¬ шенно неожиданным и невероятным результатам. Яркий пример этому — так на¬ зываемый метод двойного подсчета. Суть его состоит в подсчете элементов одного и того же множества двумя разными способами. Этот метод позволяет решить одну очень интересную задачу, связанную с картами. Представьте, что мы хотим организовать у себя дома ужин и пригласить самых близких друзей: Марию, Петра, Ивана и Анну. Попросим каждого из них принести с собой какое-нибудь угощение. Мы очень организованны и подготовили таблицу, где указано, какие продукты должен принести каждый из друзей. Сыр Мясо Пирог Вино Я X X X Мария X X Петр X X Иван X X X Анна X X 49
ГРАФЫ И КАРТЫ К примеру, Мария принесет сыр и вино, Петр — мясо и пирог. Основная осо¬ бенность этой таблицы заключается в том, что ее можно прочитать двумя разными способами. Если мы будем читать ее по горизонтали, то узнаем, какие продукты должна принести Мария (сыр и вино). Если же мы будем читать таблицу по верти¬ кали, то увидим, кто принесет с собой сыр (Иван и Мария). Таким образом, мы можем подсчитать итоговое количество продуктов двумя разными способами: опре¬ делив, что принесет с собой каждый гость, или подсчитав, сколько человек принесут каждый продукт. Обобщим задачу и сформулируем метод двойного подсчета. Рассмотрим под¬ множество декартова произведения С = А х В. Напомним, что декартово произве¬ дение множеств А и В — это множество упорядоченных пар (а, Ь), в которых эле¬ менты а и b принадлежат множествам А и В соответственно. Рассмотрим некоторые элементы декартова произведения. В предыдущем примере элемент (Мария, сыр) корректен, элемент (Мария, мясо) — нет, так как Мария принесет сыр, но не мясо. Запишем наш пример в общем виде: А = {ау а2, ..., а) и В = {Ьу Ь2, ..., Ь$}. Теперь представим, что дана таблица, подобная приведенной выше, но на этот раз в ней представлены элементы абстрактных множеств. bi Ь2 Ьз Ь4 bs а1 X X X X Э2 X аз X X X а4 X Э5 X X аг X X X В этой таблице будем обозначать крестами элементы, которые учитываются при подсчете. Элементы, не отмеченные крестами, не войдут в рассматриваемое мно¬ жество. Суть задачи — подсчитать общее число крестов в таблице. Основа метода 50
ГРАФЫ И КАРТЫ двойного подсчета заключается в том, что подсчет можно провести двумя разными способами и получить один и тот же результат. Первый способ подсчета — по строкам: выберем элемент а. (индекс i лежит на интервале от 1 до г) и посмотрим, сколько крестов содержится в соответствую¬ щей строке. Если мы выполним аналогичные подсчеты для всех значений индекса и сложим результаты, то получим общее число крестов. Рассмотрим второй способ: будем складывать числа не по строкам, а по столбцам. Иными словами, для каждого элемента Ь. (теперь индекс j лежит на интервале от 1 до s) определим, сколько кре¬ стов содержится в соответствующем столбце, после чего найдем общую сумму для всех столбцов. На основе изложенных выше рассуждений метод двойного подсчета можно вы¬ разить формулой: Z\{(a,b):beB}\=Z\{(a,b):ae Л}\. ,i€ A Ьев' Посмотрим, как следует читать эту формулу. Знак Z (греческая буква «сигма») означает «сумма», двоеточие означает «такие, что», е — «принадлежит», верти¬ кальная черта | обозначает «число элементов», а фигурные скобки {} определяют множество. Первое выражение соответствует сумме по строкам (для каждого эле¬ мента А мы подсчитываем число элементов в соответствующей строке), второе обо¬ значает сумму по столбцам. Посмотрим, как метод двойного подсчета применяется в теории графов. Рассмо¬ трим граф G. Обозначим множества его вершин и ребер через V и А соответствен¬ но. Рассмотрим следующее множество: С = {( v9 е ): v G V, е еЛ, ребро е инцидентно вершине и}. Обратите внимание, что это множество является подмножеством декартова про¬ изведения V х Ау так как для каждой вершины мы рассматриваем только ребра, инцидентные ей (то есть ребра, соединяющие эту вершину с какой-либо другой). Применим метод двойного подсчета к этому множеству и получим несколько ин¬ тересных результатов. Ключевой момент наших рассуждений таков: каждое ребро инцидентно ровно двум вершинам, так как ребро определяется двумя конечными вершинами. В следующем примере множество пар будет таким: 51
ГРАФЫ И КАРТЫ (Ы), (3,А), (2,£), о,В), (2,0, (4,0, (3,D), (4.D), (3,£), (5,£) 3 Гэаф с пятью вершинами описывается множеством, к которому мы применим метод двойного подсчета. Введем некоторые обозначения, чтобы упростить последующие рассуждения. Будем называть степенью вершины v число инцидентных ей ребер. Будем обозна¬ чать это число d(v). Перейдем к подсчетам. Число элементов множества С мож¬ но вычислить двумя разными способами: как сумму относительно ребер (для этого рассмотрим вершины, инцидентные каждому ребру) или как сумму относительно вершин (для этого рассмотрим ребра, инцидентные каждой вершине). Выполнив подсчеты первым способом, получим удвоенное число ребер — как мы уже отмеча¬ ли, каждое ребро инцидентно ровно двум вершинам. Аналогично, по определению произвольная вершина v инцидентна d(v) ребрам. Получим, что сумма степеней вершин равна удвоенному числу ребер, что можно записать с помощью знака суммы следующим способом: 2\л\ = l,d(v). re V Здесь мы явно указываем, что находим сумму степеней всех вершин. Обрати¬ те внимание, что приведенное соотношение выполняется для любого графа и любой карты, так как зависит исключительно от его скелета. С помощью этой формулы мы можем получить весьма интересную информацию. Напомним, что сумма двух четных или нечетных чисел всегда будет четной, а сумма четного и нечетного чис¬ ла всегда будет нечетной. Так как в левой части предыдущего равенства записано 52
ГРАФЫ И КАРТЫ четное число, то число вершин с нечетной степенью обязательно должно быть чет¬ ным. И действительно, в противном случае правая часть равенства будет нечетной, что невозможно. Это наблюдение кажется уже не столь очевидным. Если мы про¬ должим рассуждения в этом направлении, то получим вовсе не тривиальную лемму Шпернера — одну из подлинных жемчужин комбинаторики, точнее элементарной комбинаторики. Допустим, что треугольник с вершинами, отмеченными 1, 2 и 3, разделен на не¬ сколько мелких треугольников. Иными словами, построим дополнительное множе¬ ство вершин на сторонах исходного треугольника и внутри него. Затем проведем дополнительные ребра так, чтобы каждая грань графа была ограничена ровно тремя ребрами. Далее обозначим все новые вершины исходными метками 1, 2 и 3. Введем единственное дополнительное условие: вершины, расположенные на стороне, опре¬ деляемой вершинами 1 и 2, могут быть помечены только числами 1 или 2 (аналогич¬ но для двух других сторон треугольника). Согласно лемме Шпернера, при указан¬ ных условиях существует треугольник, все вершины которого будут иметь разные метки. На следующем рисунке представлен пример такого треугольника. Сплошной толстой линией обозначен треугольник, обладающий искомым свойством. В доказательстве леммы Шпернера нетривиальным способом применяется принцип двойного подсчета: нужно показать, что число подходящих треугольников (то есть треугольников, все вершины которых отмечены разными метками) должно 53
ГРАФЫ И КАРТЫ ЭММАНУЭЛЬ ШПЕРНЕР, ЕГО ТЕОРЕМЫ И ИХ СЛЕДСТВИЯ Лемма Шпернера применяется множеством удивительных способов. Одно из ее следствий - так называемая теорема Брауэра о неподвижной точке, согласно которой для определенных функ¬ ций существуют неподвижные точки. Удивительно, что во всех доказательствах этой теоремы, полученных до того, как была открыта лемма Шпернера, применялись намного более сложные методы, чем описанные выше. По этой причине лемма Шпернера считается одной из первых в так называемой комбинаторной топологии. Эммануэль Шпернер (1905, Вальдорф - 1980, Зульцбург) проводил свои исследования в Гамбургском университете. Его важнейшие открытия относятся к комбинаторике: это уже упомянутая лемма Шпернера, а также теорема Шпернера, связанная с непересекающимися множествами фиксированного размера. По теореме Шпернера, для данного множества А = {1, 2,..., п] семейством Шпернера называется такое семейство подмножеств, в котором ни одно не заключено в другом. К примеру, семейство {{1}, {2}} будет семейством Шпернера, а семей¬ ство {{1}, {1,2}} - нет, так как {1} - подмножество {1,2}. Каково максимальное число элементов семейства Шпернера? Согласно теореме Шпернера, оно не может превышать г \ п /»'2, элементов при четном п и ( \ п Л”-1)'2, при нечетном п. Эти биномиальные коэффициенты показывают, сколько элементов содержит семейство подмножеств {1, 2 п] из п/2 элементов при четном п и (п - 1) / 2 элементов при нечетном п. К примеру, для п = 4 такое семейство будет выглядеть следующим образом: {{1,2}, {1,3}, {1,4}, {2,3}, {2,4}, {3,4}}. Теорема Шпернера - одна из основных в комбинаторной теории решеток и частично упоря¬ доченных множеств. Кроме того, она представляет собой частный случай более общей теоремы под названием теорема Дилворта. 54
ГРАФЫ И КАРТЫ быть отличным от нуля. Лемма Шпернера не позволяет найти число треугольников, обладающих этим свойством,— она лишь доказывает, что число таких треугольни¬ ков должно быть нечетным. Любое нечетное число отлично от нуля, следовательно, обязательно найдется треугольник, обладающий этим свойством. Читателю, жела¬ ющему подробнее ознакомиться с леммой Шпернера, рекомендуем заглянуть в при¬ ложение к этой книге. Деревья - главные герои теории графов Вернемся к картам и подсчетам. Мы уже показали, что между графами и картами существует огромная разница, и возможность изобразить граф без самопересечений зависит не от нашего опыта, а от свойств самого графа. Рассмотрим подробнее графы без циклов, то есть без замкнутых маршрутов, со¬ единяющих пары вершин. Такие графы занимают особое место в математике и назы¬ ваются деревьями. Деревья играют огромную роль в алгоритмах, хранении данных, а также в далеких от математики областях, например в химии и биологии. Деревья получили свое название за характерную форму: дерево, изображенное на плоскости, определяет единственную грань, так как оно не содержит ни одного цикла, и поэто¬ му не может иметь внутренней и внешней грани. Будем считать, что каждое дерево имеет корень — вершину, отмеченную стрелкой и занимающую особое положение по сравнению с остальными. Корень дерева — не математическая условность: он обозначает исходное состояние системы, которую моделирует дерево. Дерево с корнем. Этот граф имеет всего одну грань (внешнюю) и не содержит циклов. 55
ГРАФЫ И КАРТЫ Рассмотрим такую важную разновидность деревьев, как бинарные деревья. В би¬ нарных деревьях каждая вершина инцидентна либо трем, либо одному ребру. Вер¬ шина, инцидентная трем ребрам, называется внутренней. Вершина, степень которой равна единице, обычно называется листом дерева. Вершина, следующая за корнем, также считается внутренней. Сколько существует бинарных деревьев с заданным числом внутренних вершин? Рассмотрим первые бинарные деревья. Бинарные деревья с 0,1, 2 и 3 внутренними вершинами. К примеру, два бинарных дерева с тремя внутренними вершинами различаются, хотя, по сути, в их основе находится один и тот же граф. Мы получили последова¬ тельность 1, 1, 2, 5. Определить, какое число будет следующим членом этой после¬ довательности, непросто. Подсчитать число бинарных деревьев с четырьмя вну¬ тренними вершинами путем прямого подсчета затруднительно. Здесь нам помогут методы комбинаторики, с которыми вы уже знакомы,— они позволят определить искомое число бинарных деревьев, при этом изображать все возможные варианты не потребуется. Используем рекуррентную структуру дере¬ вьев: обратите внимание, что с корнем любого дерева соединены другие деревья, содержащие определенное число внутренних вершин. Эта особенность представлена на следующем рисунке, где показано, как можно разложить бинарное дерево на два более мелких. Произвести обратную операцию также нетрудно — для этого нужно «приклеить» два корня к новой вершине. 56
ГРАФЫ И КАРТЫ I А Разложение бинарного дерева на два более мелких. Общее число внутренних вершин при этом разложении уменьшится на единицу. Это условие можно представить с помощью рекуррентных уравнений следую¬ щим образом. Обозначим через Сл число бинарных деревьев с корнем и п внутрен¬ ними вершинами. Из вышеприведенных расчетов получим: CQ = Ct = 1, С2 = 2, С3 = 5. Дерево, имеющее п внутренних вершин, можно разложить на два дерева с a и Ъ внутренними вершинами так, что сумма а и Ь будет равна п — 1 (мы исключили всего одну внутреннюю вершину из п — ту, что следует за корнем). Таким образом, общее число деревьев с п внутренними вершинами будет равно числу всех возмож¬ ных пар поддеревьев, имеющих п — 1 внутреннюю вершину. Это условие выражает¬ ся следующим рекуррентным уравнением: Согласно этому уравнению, число элементов размера п равно общему числу всех возможных способов, которыми можно выбрать упорядоченную пару из п — 1 эле¬ мента. Подставив различные значения в эту формулу, получим, что числовая после¬ довательность, описывающая количество бинарных деревьев с различным числом внутренних вершин, такова: По-настоящему любопытная особенность этой последовательности заключается не в том, что она описывается необычной формулой, а в том, что она описывает многие другие объекты. Определим еще одно семейство объектов, которое, на пер¬ вый взгляд, не имеет ничего общего с бинарными деревьями. Рассмотрим правиль¬ ный п-угольник, вершины которого обозначены метками 1, 2, ..., п против часовой стрелки. Посмотрим, сколькими способами можно разделить этот многоугольник на треугольники (этот процесс называется триангуляцией п-угольника). На следу - 1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16 796, 58 786, 208 012, 742 900, 2674 440... 57
ГРАФЫ И КАРТЫ ющем рисунке показаны возможные триангуляции для одного ребра (это вырожден¬ ный случай многоугольника, который мы рассмотрели из соображений удобства), треугольника, квадрата и пятиугольника. Триангуляции треугольника, квадрата и пятиугольника. Любопытно, что число различных способов триангуляции описывается той же числовой последовательностью: 1, 1, 2, 5... Неужели два семейства столь разных объектов описываются одной числовой последовательностью? Да, это действитель¬ но так. Чтобы показать, что каждой триангуляции можно поставить в соответствие единственное бинарное дерево, используем карту, двойственную данной карте. Ее вершины строятся внутри каждой грани исходной карты, и две вершины соединяют¬ ся ребром в случае, если они соответствуют смежным граням. В случае с триангуля¬ цией это построение выполняется следующим образом. Построим вершину на каж¬ дой грани, полученной в результате триангуляции. Кроме того, изобразим вершину степени 1 (то есть лист) для каждого ребра многоугольника, которое не определено вершинами 1 и 2. Ребру, заданному вершинами 1 и 2, поставим в соответствие ко- 58
ГРАФЫ И КАРТЫ рень бинарного дерева. Посмотрим на следующий рисунок, где показано построение для десятиугольника. 2 1 Триангуляция десятиугольника и построение соответствующего бинарного дерева. Обратите внимание, что полученная карта не содержит циклов: в противном слу¬ чае в результате триангуляции мы получили бы точку внутри многоугольника, что по определению невозможно. Кроме того, все вершины этой карты имеют степень, равную либо трем (это вершины, соответствующие треугольникам), либо единице (вершины, соответствующие ребрам многоугольника). Следовательно, карта, двой¬ ственная исходной, будет бинарным деревом, внутренние вершины которого соот¬ ветствуют треугольникам в триангуляции. Верно и обратное: можно показать, что для каждого бинарного дерева с п внутренними вершинами можно построить триан¬ гуляцию многоугольника сп + 2 сторонами, двойственной картой для которой бу¬ дет исходное бинарное дерево. Следовательно, между триангуляциями и деревьями существует взаимно однозначное соответствие, поэтому число триангуляций и де¬ ревьев определенного размера одинаково (размером считается число вершин много¬ угольника и число внутренних вершин дерева соответственно). Любопытно, что приведенное выше загадочное уравнение встречается в решени¬ ях самых разных комбинаторных задач. Решение этого рекуррентного уравнения описывается числами Каталана, названными в честь бельгийского математика Эже¬ на Каталана: С = и 1 п +1 2 п п \ / Числа Каталана стали первыми числами в комбинаторике, которые нельзя по¬ лучить посредством прямых подсчетов. Они встречаются во множестве самых 59
ГРАФЫ И КАРТЫ разных задач и примеров. Именно поэтому Ричард Стэнли, один из крупнейших специалистов по перечислительной комбинаторике, в задаче 6.19 своего справоч¬ ника «Enumerative Combinatorics» («Перечислительная комбинаторика») приводит свыше шестидесяти различных семейств объектов, которые описываются числами Каталана. Мы рассказали всего о двух таких семействах — совсем не плохо для введения в комбинаторику. Даже внутри очень сложных сущностей можно найти хорошо знакомые нам объ¬ екты — так, например, триангуляции неявно содержат в себе деревья. Эта фило¬ софия преобладала в комбинаторике на протяжении всего XX века, однако приоб¬ рела особую важность благодаря трудам ученого, пошатнувшего основы дискретной математики. Этот ученый не имел ни дома, ни личных вещей и обладал невиданной страстью к математике. Он был вечным странником, а его целью было распростра¬ нение математики и постижение тайн знания. «ОСТАТЬСЯ В ЖИВЫХ» В СЛОВАРЕ ЧИСЛОВЫХ ПОСЛЕДОВАТЕЛЬНОСТЕЙ Подобно тому как писатель обращается к словарю синонимов и антонимов, чтобы обогатить свой язык, математик в своих исследованиях также обращается к определенным ресурсам. Представьте, что нам встретилась некая числовая последовательность, но мы не знаем, какой формулой она описывается. Не проблема - если кто-то уже изучал эту последовательность, она обязательно содержится в «Энциклопедии целочисленных последовательностей» («The On-Line Encyclopedia of Integers Sequences»), расположенной по адресу http://oeis.org/. Этот проект поддерживает исследователь Нейл Слоан из исследовательской лаборатории компании АТ & Т. Каждая новая числовая последовательность снабжается аннотацией и занимает свое место в каталоге. Таким образом, если мы получили некую числовую последовательность и нужно определить, встречалась ли она кому-либо еще и какие объекты она описывает, достаточно ввести первые несколько членов последовательности в строку поиска. Читатель может найти в «Энциклопедии целочисленных последовательностей» самую зна¬ менитую и загадочную последовательность чисел в истории телевидения - код из сериала «Остаться в живых»: 4,8,15,16,23,42. Эта последовательность занимает свое место в энци¬ клопедии и имеет свой номер А104101. 60
Глава 3 Вечный странник Если числа не прекрасны, то я не знаю, что тогда прекрасно. Пал Эрдёш «Из-за погодных условий прибытие рейса из Ватерлоо задерживается примерно на 30 минут». Это объявление по громкой связи еще сильнее обеспокоило внуши¬ тельную группу математиков, нервничавших в ожидании самолета. Они напоминали скорее фанатов какой-нибудь рок-звезды, чем участников научного конгресса. Вол¬ нение ученых было более чем оправданным — не каждый день доводится встре¬ чаться с живой легендой. Наконец самолет приземлился, и спустя несколько минут в здание аэропорта вошли первые пассажиры. Среди них выделялся седой худощавый человек в тем¬ ной потрепанной рубашке. Он был в годах и держался довольно неуверенно, хотя и старался казаться невозмутимым. В одной руке он нес небольшой чемодан, в дру¬ гой — стопку смятых бумаг. Многие из его попутчиков за время полета наверняка решили, что этот пожилой господин был бродягой или даже сумасшедшим. Вряд ли кто-то из них догадывался, что рядом с ними сидит один из величайших умов со¬ временности. Появление в зале аэропорта этого необычного человека вызвало оживление сре¬ ди предвкушавших встречу математиков. Их лица просияли, чувствовалось всеоб¬ щее возбуждение. Пожилой джентльмен утратил невозмутимость. Он взглянул на встречающих, направился к ним и, широко улыбаясь, воскликнул: «Мой разум открыт для вас!» Так начался очередной визит дядюшки Пала, который привез с со¬ бой новые увлекательные задачи, недоказанные гипотезы и неизвестные теоремы. «Мой разум открыт для вас!» Во всех областях знания всегда будут существовать личности, которые в одиночку творят историю. Таким человеком был и Пал Эрдёш. Во второй половине XX века 61
ВЕЧНЫЙ СТРАННИК описанная только что сцена не раз и не два повторялась в самых разных частях света. Отправляться в путь Эрдёша всякий раз заставляло одно — безграничная любовь к математике. Специалисты из различных областей науки характеризуют труды этого ученого совершенно по-разному. Если не вдаваться в детали, то важ¬ нейшими особенностями его работ были широта и многообразие. Если бы мы со¬ ставили рейтинг математиков по объему написанных работ, то первое место с боль¬ шим отрывом занял бы Леонард Эйлер — он и сегодня остается самым плодовитым математиком. Но если Эйлера можно назвать чемпионом по объему публикаций, то Эрдёш, бесспорно, стал бы чемпионом по их количеству: его перу принадлежали более 1500 статей, в которых он охватил множество областей теоретической мате¬ матики, начиная от математического анализа и заканчивая алгеброй, не говоря уже о геометрии. Однако несмотря на всю широту математического творчества, ученый питал особую слабость к дискретной математике. Он совершил свои главные откры¬ тия в этом мире конечных геометрий, графов, аддитивных проблем и хитроумных подсчетов на пальцах. Именно благодаря Палу Эрдёшу комбинаторика впервые стала считаться от¬ дельной дисциплиной, достойной того, чтобы занять собственное место на матема¬ тическом Олимпе. До этого дискретные задачи рассматривались как частные случаи или вовсе математические диковинки, занимавшие последние места в математиче¬ ской иерархии. Благодаря открытиям Эрдёша и предложенным им задачам (а также целым разделам математики, которым эти задачи дали начало), комбинаторика при¬ обрела современный вид и стала отдельной дисциплиной. Даже если не учитывать вклад Эрдёша в науку, что само по себе непросто, нель¬ зя не отметить еще одно его важное достижение: только благодаря этому леген¬ дарному ученому математика стала считаться разновидностью социальной деятель¬ ности — видом творчества, в котором могут принимать участие сразу несколько человек. Большинство научных работ, созданных до середины 20-х годов XX века, были написаны без соавторов. Эрдёш попытался покончить с этим неписаным пра¬ вилом и сформировал целую сеть из сотрудничавших с ним ученых. В результате насчитывается более 500 его соавторов — у большинства людей не наберется столь- 62
ВЕЧНЫЙ СТРАННИК ко знакомых! Эта «социальная сеть» упрочилась еще и благодаря тому, что Эрдёш провел большую часть жизни в путешествиях. Он переезжал из университета в уни¬ верситет, с континента на континент, всякий раз увозя с собой все (весьма немного¬ численные) личные вещи. Этот гениальный математик по праву станет нашим проводником в мире совре¬ менной комбинаторики — дисциплины, в которую дядюшка Пал, как он просил себя называть, внес ключевой вклад благодаря головоломкам, гипотезам и доказа¬ тельствам. Многие из его задач были решены, но некоторые не поддались даже самым выдающимся умам XX столетия. Впрочем, прежде чем начать путь к этим задачам, давайте познакомимся по¬ ближе с самим Эрдёшем, человеком-легендой. Чем лучше мы узнаем нашего прово¬ дника, тем увлекательнее будет путешествие. Пал Эрдёш — человек, разделивший историю комбинаторики на «до** и«после**. 63
ВЕЧНЫЙ СТРАННИК Детство Интеллектуальная, творческая и научная среда Будапешта в первой половине XX века переживала период расцвета. Дунай был не естественной границей между городами Буда и Пешт, а, скорее, связующим звеном между разными культурами. В кафе, на бульварах и в парках венгерской столицы ощущалась особая творческая атмосфера, сравнимая с атмосферой Парижа и Лондона. Немалую роль в бурном культурном развитии города сыграла местная еврейская община. Благодаря особой политической обстановке в стране, со второй половины XIX века, еще со времен Австро-Венгерской империи, евреи обладали полными правами и могли занимать общественные и политические должности. Культурное и экономическое влияние ев¬ рейской общины в Будапеште того времени было столь велико, что злопыхатели презрительно называли город Юдапештом. Этот скрытый антисемитизм вырвался на свободу много лет спустя, когда все евреи города были заключены в гетто и позднее отправлены в концентрационные лагеря. Однако эти печальные события настанут еще не скоро, а пока никто и пред¬ положить не мог, что город ждут столь постыдные перемены. Именно в этой среде в 1913 году в семье еврейских математиков Анны и Лайоша Эрдёшей родился сын Пал. Ребенок не знал своих старших сестер Магду и Клару — они умерли во время эпидемии скарлатины, поразившей город. После этой траге¬ дии родители целиком посвятили себя образованию мальчика и относились к нему с величайшей любовью и нежностью, порой излишне оберегая его. Антисемитизм в Будапеште уже набирал обороты, и жизнь молодой еврейской семьи становилась все сложнее. Но это было лишь начало череды неприятностей: когда маленькому Палу исполнился год, в Сараево был убит эрцгерцог Франц Фердинанд, наследник австро-венгерского престола. Политическая обстановка была крайне напряженной, и в ответ на эту провокацию Австро-Венгрия объявила войну Сербии. Так началась Первая мировая война. Лайош, отец Пала, был мобилизован. 64
вечный странник ОБЩЕСТВО В ПЕРИОД ИНТЕЛЛЕКТУАЛЬНОГО РАСЦВЕТА Неудивительно, что с развитием творческой среды в Будапеште в период между мировыми вой¬ нами появилось множество крупных ученых и деятелей искусства. Помимо Пала Эрдёша, здесь работали многие юные и не очень юные математики, создавшие впоследствии новые теории и открывшие новые пути в науке. Среди них был и Липот Фейер, один из основоположников со¬ временного математического анализа, который спустя много лет стал научным руководителем Эрдёша при написании докторской диссертации. Фейер основал целую школу из юных блестя¬ щих математиков, среди которых выделялись Пал Туран, Дьёрдь Пойа и Тибор Радо. Отметим и одного из самых известных учеников Фейера - Джона фон Неймана, который заложил основы современной квантовой физики и стал одним из создателей теории игр и информатики. Много лет спустя, уже после переезда в США, фон Нейман был одним из первых гражданских лиц, при¬ нявших участие в знаменитом «Проекте Манхэттен», направленном на создание атомной бомбы. Вклад Венгрии в мировую науку и культуру не ограничивается математикой: работы инженера Теодора фон Кармана, специалиста в области воздухоплавания, были использованы при созда¬ нии сверхзвуковых самолетов, а нобелевский лауреат Дьёрдь де Хевеши совершил множество открытий, связанных с радиоактивностью, в самых разных областях. Разумеется, нельзя не от¬ метить венгерских деятелей искусства: это и дирижер Георг Шолти, и композитор Бела Барток, и художник Ласло Мохой-Надь, и режиссер Александр Корда, и даже иллюзионист Эрик Вайс, известный во всем мире под именем Гарри Гудини. Будапешт в 1910 году.
ВЕЧНЫЙ СТРАННИК Вскоре семью постигла трагедия: Лайош Эрдёш был захвачен русскими вой¬ сками и на шесть лет сослан в далекую холодную Сибирь. Анна Эрдёш не знала, увидит ли она когда-нибудь мужа, поэтому отдала все силы воспитанию сына. Она излишне опекала мальчика, и маленький Пал не ходил в школу с другими детьми, а обучался дома. Его образованием занимались сама Анна и приглашенный репети¬ тор. В те годы Пал очень привязался к матери. Много лет спустя, когда он начал свои странствия, Анна Эрдёш неустанно сопровождала его во всех поездках. Талант Пала не остался незамеченным: можно сказать, что считать он научился раньше, чем ходить. В три года малыш уже умел складывать числа, в четыре — про¬ изводил в уме сложные вычисления, в частности, перемножал большие числа или подсчитывал, сколько минут прожил тот или иной человек. Еще в нежном возрасте он узнал о существовании отрицательных чисел, и перед ним открылись новые гори¬ зонты. Эрдёш понял: в математике нет пределов для разума. Развитию его дарова¬ ния способствовала особая среда, благоприятная для интеллектуального творчества. В те времена Венгрия отличалась передовой системой образования, в которой глав¬ ная роль отводилась выявлению индивидуальных способностей каждого ученика. Школьные учителя занимали важное место в обществе и не просто вели занятия, но были настоящими властителями дум. Видные и авторитетные исследователи про¬ водили часы за обсуждением задач с юными талантами. Диалог между поколениями имел множество форм. Одной из них стали матема¬ тические журналы, в частности популярный в те годы журнал KoMaL, учрежден¬ ный в 1894 году профессором Даниэлем Арани. По словам Арани, целью создания журнала было «...дать преподавателям и студентам мощный источник задач...» (Журнал издается до сих пор, с последними публикациями вы можете ознакомить¬ ся на сайте www.komal.hu.) В изданиях ежемесячно публиковались новые задачи, и школьникам предлагалось их решать — так издатели могли выявить тех, кто об¬ ладал особыми способностями к наукам. Стоит отметить, что эти задачи представ¬ ляли определенную сложность не только для детей, но и для самих исследователей, но какой математик устоит перед соблазном разгадать еще одну загадку? Спустя много лет из этих журналов выросли местные и национальные матема¬ тические конкурсы, на основе которых впоследствии были созданы международ¬ 66
ВЕЧНЫЙ СТРАННИК ные олимпиады по математике (а также по физике, химии и даже по информати¬ ке) — соревнования высшего уровня для школьников разных стран. Подобно тому как спортивные олимпиады требуют самой серьезной подготовки, математические олимпиады требуют строгого отбора, упорного труда и немалых способностей. Именно с участия в олимпиадах начали свой путь в науке многие великие ученые второй половины XX века. Но вернемся в Будапешт, к юному Палу Эрдёшу. По окончании Первой миро¬ вой войны обстановка в Венгрии только ухудшилась. Антисемитизм и антикомму¬ низм приобрели неожиданный размах в 1920 году, когда власть в стране захватил правый националист, командующий австро-венгерскими войсками Миклош Хорти. Придя к власти, он принял множество законов, подобных тем, которые 13 лет спу¬ стя появятся в Германии и положат начало варварскому уничтожению евреев. Но в жизни семьи Эрдёшей была и капля радости — из ссылки вернулся Лайош. В обстановке семейного счастья Пал оживился и стал еще более любопытным. В это время у него появились знакомые, которые в будущем станут близкими спутниками ученого в мире математики: Пал Туран, Дьёрдь Секереш и Эстер Клейн — люби¬ тели решать задачи, предлагавшиеся в журналах для школьников. Друзья создали небольшую группу юных математиков, которые много лет спустя стали авторами множества новых прекрасных теорий. Ситуация в городе осложнялась все больше, ненависть к евреям росла. Тем вре¬ менем Эрдёш вырос и начал профессионально заниматься математикой — сначала он окончил университет, затем защитил докторскую диссертацию и в конце концов покинул любимый Будапешт. Юность и изгнание Интерес Эрдёша к математическим задачам неуклонно возрастал, и уже в юном возрасте он стал известен в других странах. Один из первых важных результатов юноша получил всего в 19 лет: он нашел альтернативное доказательство так называ¬ емого постулата Бертрана. Чтобы читатель смог лучше понять эту теорему, напом¬ ним, что такое простые числа. Число называется простым, если оно делится только 67
ВЕЧНЫЙ СТРАННИК на единицу и само себя. Так, простыми являются 2, 7 и 11, но не 6, так как оно делится на 2. Постулат Бертрана гласит: «На интервале между любым числом и числом в два раза больше обязательно найдется простое число». К примеру, между 4 и 8 находится простое число 5, между 13 и 26 — 17, также простое число. Первое доказательство постулата Бертрана привел Пафнутий Чебы- шёв в 1850 году, использовав при этом весьма сложные рассуждения. Несколько лет спустя гениальный Сриниваса Рамануджан нашел другое доказательство, ко¬ торое, однако, по-прежнему содержало несколько непростых моментов. Наконец, в 1932 году Пал Эрдёш получил очень красивое и простое доказательство с по¬ мощью биномиальных коэффициентов, о которых мы уже подробно рассказывали. Именно в те годы Эрдёш начал тесно сотрудничать с другими венгерскими ма¬ тематиками. Многие из них, как и Эрдёш, активно публиковались в математических журналах. Талантливые математики перезнакомились уже в юном возрасте и начали регулярно встречаться для обсуждения математических задач. Место встреч было неизменным — возле памятника на могиле неизвестного писателя в городском пар¬ ке Будапешта Варошлигете, рядом с замком Вайдахуняд. Памятник был воздвиг¬ нут в честь неизвестного летописца славнейшего царя Белы (Gloriossissimus Belae Regis) — по преданию, это был один из первых летописцев в истории Венгрии, живший в XII веке. Как гласила местная легенда, прикосновение к бронзовому перу в руке статуи приносит удачу, поэтому оно всегда блестит. Перо действительно при¬ несло Эрдёшу и его товарищам удачу на пути к знаниям. Пребывание Эрдёша в университете завершилось довольно быстро. В те годы евреям был заказан путь в некоторые университеты, но Эрдёша запреты не косну¬ лись — он получил высшую оценку на государственном экзамене среди школьников всей страны и автоматически был зачислен в будапештский Университет Петера Пазманя в 1930 году. Там же в 1934 году юноша защитил докторскую диссертацию под руководством великого венгерского математика Липота Фейера. Эрдёш выде¬ лился и здесь — степень доктора была присуждена талантливому иссследователю всего в 21 год (он поступил в университет в 17 лет и за четыре года успел и получить диплом, и защитить диссертацию!). 68
ВЕЧНЫЙ СТРАННИК Могила неизвестного писателя — место встречи Эрдёша с коллегами-математиками. Евреи в Венгрии каждый день ожидали новых ухудшений, и Эрдёш решил по¬ кинуть родину: быть ученым-евреем оказалось вдвойне непросто. Он направился в Англию, в Манчестерский университет, по приглашению великого еврейского ма¬ тематика американского происхождения Луиса Джоэла Морделла. Рассказывают, что сам Эрдёш так описывал свое прибытие в совершенно незнакомый ему Манче¬ стер: «Я ничего не ел с самого утра и приехал к Морделлу только вечером. В пять подали чай. Я был очень голоден, но стеснялся признаться, что не умел на¬ мазывать масло на хлеб. Я стал повторять за остальными и обнаружил, что это совсем не так трудно, как могло бы показаться...» 69
ВЕЧНЫЙ СТРАННИК Эта история дает понять, как сильно мать опекала Эрдёша в детстве и юности. В Англии ему впервые пришлось действовать самостоятельно, и он успешно спра¬ вился с задачей. С этой поездки начались путешествия Эрдёша, и спустя много лет он стал вести по-настоящему кочевой образ жизни. В том же 1934 году в Кем¬ бридже ученый познакомился с великим Годфри Харолдом Харди, годом позже — со Станиславом Уламом. Встреча с Уламом сыграла важнейшую роль значительно позже, когда перед Эрдёшем наконец распахнулись двери в Новый Свет. Пока Эрдёш разъезжал по Великобритании, обстановка на континенте накали¬ лась. Впрочем, это не помешало ему трижды навестить любимый Будапешт. Но си¬ туация становилась все хуже, и в 1938 году Австрия оказалась под властью Гитлера. Видя, что нацисты набирают силу (это подтвердил и конфликт в Судетской обла¬ сти бывшей Чехословакии, произошедший 3 сентября того же года), Эрдёш решил эмигрировать в США, где планировал начать работу в Институте перспективных исследований в Принстоне — научном и интеллектуальном центре самого высокого уровня. Математик уехал из Будапешта, оставив друзей и родителей и не зная, до¬ ведется ли им встретиться вновь. Эта встреча состоялась — 10 лет спустя. А пока ИССЛЕДОВАТЕЛЬСКИЙ ИНСТИТУТ ВЫСОЧАЙШЕГО УРОВНЯ Институт перспективных исследований в Принстоне был основан в 1930 году для того, чтобы предо¬ ставить ведущим ученым из самых разных областей все условия для работы и избавить их от не¬ обходимости преподавать. Институт не зависел от Принстонского университета, хотя между ними сформировались многочисленные неформальные и рабочие связи. Это заведение весьма отлича¬ лось от классических университетов: здесь работало небольшое количество профессоров, к которым ежегодно присоединялись приглашенные специалисты, проходившие строгий отбор. Исследовате¬ лям предоставлялась полная свобода действий: их не ограничивали контракты и руководство извне, они сами выбирали направление работ. Плата с присутствующих не взималась, финансирование поступало исключительно в виде пожертвований. Согласно уставу института, одной из его целей было предоставление убежища ученым-евреям, которые не могли работать в Принстонском университете из-за царившего там официального анти¬ семитизма. Так сотрудниками института стали многие великие ученые XX века, в частности Альберт Эйнштейн, Роберт Оппенгеймер («отец атомной бомбы») и Джон фон Нейман. Курт Гёдель, хотя не был евреем, написал диссертацию совместно с еврейским математиком Хансом Ханом и также работал в институте первые несколько лет после его создания. Условия для работы, казалось, были 70
ВЕЧНЫЙ СТРАННИК 18 сентября, взяв курс из Лондона на Нью-Йорк, Эрдёш покинул старушку Евро¬ пу. .. На какое-то время. США, Израиль... Жизнь странника В США Эрдёш сразу же приступил к работе в Институте перспективных исследо¬ ваний в Принстоне. Впрочем, он провел там меньше времени, чем ожидалось: после года работы руководство отказалось продлевать контракт с ученым. Официальной причиной стала нехватка средств, однако ходили слухи, что тяга Эрдёша к совмест¬ ной работе беспокоила великих ученых, которые в те годы работали в Принстоне. К счастью, тогдашний глава математического отделения института Освальд Веблен выхлопотал для Эрдёша зарплату в 750 долларов в месяц, и этого было достаточно, чтобы остаться в США еще на год. В 1941 году математик перешел на работу в Пенсильванский университет, и по¬ сле этого на Лонг-Айленде произошло на первый взгляд незначительное событие, которое, впрочем, имело серьезные последствия. Однажды Эрдёш бурно спорил с двумя другими исследователями, и вдруг их дискуссию прервал полицейский. идеальными, но многие выдающиеся ученые критиковали эту модель. Легендарный физик Ричард Фейнман в своей знаменитой книге «Вы, конечно, шутите, мистер Фейнман?» писал: «...Когда я в 40-х годах был в Принстоне, то мог видеть, что произошло с великими умами в Институте перспективных исследований, с умами, которые были специально отобраны за потрясающие способности. Им предоставлялась возможность сидеть в хорошеньком до¬ мике рядом с лесом безо всяких студентов, с которыми надо заниматься, безо всяких обя¬ занностей. Эти бедняги могут только сидеть и думать сами по себе, так ведь? А им не при¬ ходят в голову никакие идеи: у них есть все возможности что-то делать, но у них нет идей. Мне кажется, что в этой ситуации тебя гложет что-то вроде чувства вины или подавленности, и ты начинаешь беспокоиться, почему к тебе не приходят никакие идеи. Но ничего не полу¬ чается - идеи все равно не приходят. Ничего не приходит потому, что не хватает настоящей деятельности и стимула. Ты не общаешься с экспериментаторами. Ты не должен думать, как ответить на вопросы студентов. Ничего!..» 71
ВЕЧНЫЙ СТРАННИК Незадачливые математики не заметили, что во время спора зашли за ограничитель¬ ную линию, и на Эрдёша завели досье в ФБР. В эпоху маккартизма этой мелочи оказалось достаточно, чтобы у математика возникли проблемы. Хотя разум Эрдёша пребывал в мире науки, его сердце находилось по другую сторону Атлантики. В 1943 году больше всего ученого волновала судьба семьи и страны: с 1941 года до самого освобождения Будапешта в 1945 году он не получил от родных ни единой весточки. А когда известия дошли, Эрдёш узнал, что его отец умер несколько лет назад, в 1942 году. И это еще не все: нацисты были особенно жестоки к будапештским евреям, и многие из них закончили свои дни в Освенциме. Жертвами холокоста стали многие родственники математика, но его любимая мать, Анна, выжила. Эрдёш смог вернуться на родину только в конце 1948 года — он всем сердцем стремился повидать близких. Так он и начал путешествовать между Старым Светом и Новым, где его ждала исследовательская работа в Университете Нотр-Дам в Индиане. 1954 год стал для нашего героя переломным: в тот год Международный матема¬ тический конгресс проходил в Амстердаме, и Эрдёша пригласили выступить с ре¬ чью. Так как ученый не был гражданином США, для возвращения ему пришлось оформить визу. Однако обширная переписка со множеством математиков, в том числе и проживавших по ту сторону железного занавеса, вызвала подозрения у со¬ трудников иммиграционной службы. Надо помнить, что в то время в США активно велась «охота на ведьм». Сыграло свою роль и досье, заведенное в ФБР после ин¬ цидента на Лонг-Айленде. В результате Эрдёшу запретили возвращаться в США. Он воспоминал: «...Чиновники задавали мне всевозможные глупые вопросы...» Последней каплей стал вопрос о Марксе, на который Эрдёш ответил так: «...Я не¬ достаточно компетентен, чтобы судить о нем, но он, несомненно, был великим че¬ ловеком...» Эрдёш смог вернуться в «страну возможностей» только в 1958 году, когда ему была выдана специальная виза для участия в научной конференции. Мате¬ матик так описывал все эти события: «.. .Внешняя политика США основана на двух принципах: недопущении коммунистического Китая в ООН и недопущении Пала Эрдёша в США...» Математик поступил на работу в Израильский технологиче- 72
ВЕЧНЫЙ СТРАННИК с кий институт, Технион, где провел больше десяти лет. В это же время в нем про¬ снулась тяга к странствиям, которая начала проявляться еще в юности. После возвращения из США отношения Эрдёша с матерью стали более тесны¬ ми: он жил с ней, когда не путешествовал, а она полностью устраивала быт сына, чтобы он мог сосредоточиться исключительно на науке. Они были так близки, что с 1964 года Анна Эрдёш, будучи уже в преклонном возрасте — ей исполнилось 84 года, — начала путешествовать с сыном. Мать была для него управляющим, наставником и советчиком. Пал Эрдёш с матерью. После смерти Анны в 1971 году чудачества Эрдёша стали проявляться все силь¬ нее. Бывая в Будапеште, он отказывался даже входить в родительскую квартиру и останавливался у друзей. Ученый мог появиться среди ночи и заявить, что готов 73
ВЕЧНЫЙ СТРАННИК поговорить о математике. Он исступленно работал по 19 часов в сутки, а его диета по большей части состояла из крепкого кофе и амфетаминов. Постепенно давал себя знать и возраст, но Эрдёш не снижал оборотов: он отка¬ зывался от операции по удалению катаракты, ведь для этого ему пришлось бы на какое-то время прекратить работу. У ученого было слабое сердце, помочь ему могла бы установка электрокардиостимулятора — несложная операция, которая, однако, требовала госпитализации. Эрдёш не хотел ночевать в больнице: это поме¬ шало бы ему присутствовать на конференции, в которой он участвовал. Наконец, он дал согласие на операцию, после чего отправился на конференцию по математике в сопровождении двух кардиологов. Ученый неустанно работал до последнего дня. Он уже не отличался прежней бы¬ стротой ума, но по-прежнему много путешествовал и останавливался там, где его принимали, неизменно принося с собой новые и новые задачи. В 1996 году, во время конференции в Варшаве, сердце Эрдёша остановилось. Ему было 83 года. С этой смертью осиротели все члены большого семейства специалистов по комбинаторике. Личность гения: гипотеза и доказательство Необычный путь, выбранный Эрдёшем, в немалой степени сформировал его харак¬ тер. Можно сказать, что математика была главным объектом интереса ученого. Он постоянно находился в мире абстракций, поэтому наиболее яркой его личной чертой было абсолютное равнодушие ко всему материальному — деньгам, титулам и долж¬ ностям. Эрдёш никогда не беспокоился о жилье и трудоустройстве, а зарабатывал на жизнь тем, что помогал молодым талантливым математикам. В 1984 году он получил премию Вольфа — одну из самых престижных премий в мире математи¬ ки, сопоставимую с современной Абелевской. Денежная часть награды составляла 50 тысяч долларов, из которых Эрдёш оставил себе всего 720 долларов. Большую часть премии в знак признательности он пожертвовал Техниону — власти этого института согласились принять математика после того, как ему был запрещен въезд в США. Часть средств пошла на финансирование программы постдокторантуры, учрежденной Эрдёшем в честь родителей, а остаток денег он просто раздал дру¬ зьям, родственникам, студентам и коллегам. Немалую часть заработка Эрдёш выдавал в качестве премий за доказательство гипотез, с которыми не мог справиться самостоятельно. Размер этих премий со¬ ставлял от 1 доллара (за решение задач, которые казались Эрдёшу очень простыми) 74
ВЕЧНЫЙ СТРАННИК ИЗВЕСТНЫЕ ИЗРЕЧЕНИЯ КАК ПРОЯВЛЕНИЕ ХАРАКТЕРА Жизненная философия Пала Эрдёша лучше всего проявлялась в его максиме «гипотеза и до¬ казательство». Однако ученый интересовался не только математикой, но и политикой, фило¬ софией, богословием. Заслуживают внимания следующие цитаты, которые помогают лучше понять его характер: «Верить в Бога необязательно, но необходимо верить в Книгу» (Книгой Эрдёш называл сборник красивейших математических доказательств); «В могиле будет достаточно времени, чтобы отдохнуть»; «Бог - верховный фашист»; «Телевидение изобрели русские, чтобы уничтожить американское образование»; «Задачи, достойные решения, доказывают свою ценность в борьбе»; «Быть может, Бог не играет в кости со Вселенной, но с простыми числами определенно что-то не так»; «Я ожидаю, что мы сможем решить эти задачи прежде, чем выйдем из дома»; «Один французский социалист сказал, что частная собственность - это грабеж, а я говорю, что частная собственность - это гадость»; «Пройдут миллионы лет, прежде чем мы сможем хоть как-то, пусть и не до конца, понять, почему мы стремимся познать бесконечность». до 10 тысяч долларов (за крайне сложные задачи, в решении которых в ближайшие годы, по его мнению, не ожидалось значительных успехов). Эти премии были всего лишь предлогом для того, чтобы математики принялись за решение сложных задач дядюшки Пала, который часто выплачивал награду необеспеченными чеками. Когда подобное стало повторяться все чаще, друг и советчик Эрдёша Рональд Грэм, за¬ менивший ученому мать после ее кончины, начал перечислять средства для выплаты премий на общий банковский счет. Любопытно, что все, кому удавалось решить ту или иную задачу, хотели получить не только деньги, но и чек с автографом живой легенды! Увы, множество гипотез, предложенных Эрдёшем, до сих пор не доказаны. Бо¬ лее того, даже не ожидается, что в ближайшее время будут получены какие-либо значимые результаты в этой сфере. Следующую гипотезу Эрдёш формулировал со¬ вместно с другом детства, Палом Тураном, и за ее доказательство полагалась одна из крупнейших премий Эрдёша размером 3 тысячи долларов: 75
ВЕЧНЫЙ СТРАННИК «Пусть А = {ау av ау ...} — бесконечное множество натуральных чисел. Если ряд расходится (иными словами, его сумма равна бесконечности), то А содержит сколь угодно большие арифметические прогрессии». Чтобы понять эту гипотезу, сначала следует пояснить понятия, которые могут быть незнакомы читателю. Что такое ряд и что означают слова «ряд расходится»? Очевидно, что если дано конечное множество чисел, мы можем найти их сумму (сложить первое со вторым, затем сложить полученный результат с третьим и так далее). Этой суммой всегда будет некоторое число. Если же дано бесконечное мно¬ жество чисел, мы уже не можем действовать аналогичным образом, так как нам потребуется выполнить сложение бесконечное число раз, что невозможно. Под сум¬ мой ряда понимается предел, к которому стремятся эти суммы: будем складывать первое число со вторым, результат сложения — с третьим, и так далее. Если полу¬ ченные суммы будут постепенно приближаться к некоторому числу, будем называть это число суммой ряда. Некоторые суммы ряда обладают интересным свойством: если по мере сложения членов ряда их сумма неограниченно возрастает, то говорят, что такой ряд расходит¬ ся. К примеру, этим свойством обладает сумма чисел, обратных натуральным (они образуют ряд, называемый гармоническим),— достаточно взять в руки калькуля¬ тор и вычислить первые несколько сумм: Чем больше слагаемых мы рассмотрим, тем больше будет сумма. Она может быть сколь угодно большой. Еще одно понятие — это понятие арифметической прогрессии. Множество из п чисел называется арифметической прогрессией из п + 1 члена с разностью Ь, ал ау . + - + — = 2,928968254; 9 10 i+ - + - + ... + — + — = 5,187377518; 1 2 3 99 100 - + - + - + ... + — + —!— = 7,485470861. 1 2 3 999 1000 76
ВЕЧНЫЙ СТРАННИК если все члены прогрессии можно представить в виде а + bk, где k принимает значе¬ ния от 0 до п. Следовательно, гипотеза Эрдёша — Турана гласит: если об исходном множестве известно лишь то, что сумма его элементов расходится, это множество обязательно будет содержать четко определенные структуры (арифметические про¬ грессии произвольной длины). Эта простая на первый взгляд гипотеза в действительности оказалась наделена глубоким смыслом и стала стимулом к развитию некоторых важных математических теорий второй половины XX века. Но не будем забегать вперед. ДОКАЗАТЕЛЬСТВО РАСХОДИМОСТИ РЯДА Рассмотрим подробнее, как можно доказать расходимость гармонического ряда. Во-первых, необходимо учесть, что если а < Ь, то 1 1 Ь а Взяв это соотношение за основу, убедимся, что выполняются следующие неравенства: 1 1- 111 1- 1J_J_J_J._1.J_ J_ 3>4' 5' б' 7>8' 9' 10' 11' 12' 13' 14' 15 > 16 * С учетом этих неравенств преобразуем гармонический ряд и получим, что его сумма будет ограничена сверху следующим выражением: 1111 2 2 13 4 1 1 (1 11 2 2 [4 4J + (J 1 1 г + ' \ 1 1 1 1 1 1 11 1 5 6 7 8 ^9 10 11 12 13 14 15 16 J / \ / + 1111 + 11111111 1 1 1 h 1 Н 1 8 8 8 8) J6 16 16 16 16 16 16 16 1 1 2 4 8 = - + - + — + — + + ...= 2 2 4 8 16 1111 = - + - + - + - + 2 2 2 2 Очевидно, что последний ряд расходится. 77
ВЕЧНЫЙ СТРАННИК Принцип гипотезы и доказательства проявился в неустанном поиске соавторов во всех уголках планеты — Эрдёша не волновали национальность, происхождение и политические взгляды коллег. Страстная любовь к совместному творчеству при¬ вела к тому, что Эрдёш стал самым плодовитым математиком всех времен — он на¬ писал более 1500 статей, а его соавторами стали более 500 ученых. В результате ро¬ дилось любопытное понятие «число Эрдёша». Каждый человек имеет определенное число Эрдёша. Сам Пал Эрдёш, главный герой этой «пьесы», — единственный, кто имеет число Эрдёша, равное 0. У всех его соавторов число Эрдёша равно 1. Анало¬ гично, число Эрдёша равно 2 у всех, кто рука об руку работал с учеными, имеющими число Эрдёша, равное 1, и так далее. Наконец, если человек никак не связан с Эрдё¬ шем (то есть не является соавтором кого-то, кто имеет определенное число Эрдёша), то говорят, что у такого человека либо нет числа Эрдёша, либо оно не определено (либо бесконечно велико, как считают некоторые специалисты). О числах Эрдёша в мире математики сказано многое, и даже создан целый ис¬ следовательский проект, с которым можно ознакомиться по адресу http://www. oakland.edu/enp/. При эмпирическом изучении этих чисел было отмечено, что они очень малы: доказано, что у всех действующих математиков последней четвер¬ ти XX века, имеющих определенное число Эрдёша, оно не превышает 15 (почти у всех оно равно 8), а среднее число Эрдёша равно 5. В силу того что различные науки тесно связаны друг с другом, число Эрдёша перешагнуло границы математи¬ ки. К примеру, лингвист Ноам Хомский и астроном и писатель Карл Саган имеют число Эрдёша, равное 4, следовательно, их соавторы, которые не являются матема¬ тиками, также будут иметь определенное число Эрдёша. Живительнее всего, что для случайно выбранного ученого число Эрдёша будет невелико вне зависимости от области, в которой он работает. Схожие закономерно¬ сти наблюдаются и в больших социальных сетях, при распространении некоторых заболеваний и в иерархии Всемирной паутины. Эти закономерности — результат так называемого эксперимента «мир тесен» (англ, small world experiment), который первым провел психолог Стэнли Милгрэм в 1967 году, хотя различные авторы вы¬ сказывали схожие идеи еще в первой половине XX века. 78
ВЕЧНЫЙ СТРАННИК Суть эксперимента Милгрэма проста. Допустим, что у нас 100 знакомых, у каж¬ дого их них — примерно столько же друзей. Говорят, что эти друзья находятся от нас на расстоянии 2, а наши непосредственные знакомые — на расстоянии 1. Число зна¬ комых наших знакомых по правилу умножения примерно равно 100 • 100 = = 10000 человек (следовало бы учесть общих друзей, но для простоты предполо¬ жим, что они отсутствуют). Обобщив рассуждения, получим, что число людей на расстоянии п от нас должно иметь порядок 100л. Таким образом, с увеличением расстояния от нас число людей возрастает экспоненциально (то есть очень быстро). Всего за несколько этапов наша «социальная сеть» охватит великое множество лю¬ дей. Читатель может убедиться в этом и проверить, сколько людей отделяют его от президента США, актера Роберта де Ниро или знаменитого спортсмена Карла Льюиса. Мы гарантируем, что вас отделяет от них намного меньше знакомых, чем могло бы показаться на первый взгляд. Чтобы изучить вопрос эмпирически, Стэнли Милгрэм попросил несколько че¬ ловек с западного побережья США отправить посылку другому человеку, живше¬ му в Массачусетсе. Сложность эксперимента заключалась в том, что его участники не знали точный адрес получателя посылки — им были известны лишь его имя, про¬ фессия и штат проживания. Милгрэм указал, что каждый участник должен передать посылку тому знакомому, который, по его мнению, с большей вероятностью знал получателя. Этот знакомый должен был передать посылку дальше по тому же прин¬ ципу, и так далее, пока посылка не дойдет до адресата. Хотя участники экспери¬ мента ожидали, что посылки пройдут через множество рук, для доставки по адресу понадобилось в среднем от пяти до шести человек. Открытия Милгрэма были опубликованы в журнале Psychology Today и дали начало так называемой теории шести рукопожатий, которые отделяют друг от друга двух любых человек на нашей планете. Об этой теории был снят полнометражный фильм и телесериал. Она прочно укоренилась в современной культуре вместе с из¬ вестным изречением Энди Уорхола: «У каждого есть свои 15 минут славы». Наш глобальный мир со множеством связей подобен графу. 79
□ ГЧИЫИ СТРАННИК ФРАГМЕНТ ФИЛЬМА «ШЕСТЬ СТЕПЕНЕЙ ОТЧУЖДЕНИЯ» В вышедшем на экраны в 1993 году фильме «Шесть степеней отчуждения» режиссера Фреда Скеписи неявно упоминается теория шести рукопожатий. Герою фильма Полу (его играет моло¬ дой Уилл Смит) удается войти в мир Уизы и Флэна Киттриджа, которые занимаются продажей произведений искусства в Нью-Йорке, представившись сыном актера Сидни Пуатье. Когда Уиза обнаруживает, что Пол не тот, за кого себя выдает, она говорит: «Я где-то читала, что любых жителей Земли отделяют друг от друга всего шесть человек. Шесть степеней отчуждения отделяют нас от остальной планеты: от президента США, венецианского гондольера, любого другого человека. Меня сильнее всего успокаивает то, что мы так близки, и в то же время это подобно китайской пытке - чтобы соеди¬ ниться с нужным человеком, нужно найти этих шестерых. Эти шестеро необязательно известные личности, это и индеец Амазонии, и житель Огненной Земли, и эскимос. Ты и я связаны с остальной планетой узкой тропинкой, которую протоптали шесть чело¬ век. Это глубокая мысль. Как нас нашел Пол? Как найти человека, сыном которого он представляется, хотя я в этом сомневаюсь? Каждый человек - новая дверь в другие миры. Между нами и остальной планетой - шесть степеней отчуждения. Но нужно найти правильных людей». Афиша фильма «Шесть степеней отчуждения». 80
ВЕЧНЫЙ СТРАННИК Эрдёш использовал особый язык: к примеру, он называл Книгой собрание самых красивых математических доказательств. По мнению Эрдёша, в Книге хранилось божественное знание. Он часто использовал еще одно понятие — «эпсилон» — называя так маленьких детей, потому что в математике этой греческой буквой, как правило, обозначаются малые, незначимые величины. И самое важное — «уме¬ реть» для него означало прекратить заниматься математикой, а «уйти» означало физическую смерть. Ученый не мыслил жизни без математики. Как вы узнаете из следующих глав, Эрдёш не умер, а всего лишь ушел: его мате¬ матическое наследие до сих пор разработано не полностью. 81
Глава 4 Считаем (уже не на пальцах) Как мы осмеливаемся говорить о законах случайного? Разве случайность не есть полная противоположность любого закона? Бертран Рассел В каждой культуре существует множество забавных анекдотов об иностранцах. В мире математики также не обошлось без стереотипов и сравнений с другими на¬ уками. Одна из таких шуток, известная в самых разных вариантах, звучит следую¬ щим образом. Инженер, математик и физик остановились в гостинице на ночь. Инженер за¬ метил, что кофейник дымится, поэтому встал с кровати, отключил его, полил холодной водой и улегся спать. Чуть позже дым почувствовал физик. Он встал с кровати и увидел: от окурка, упавшего в корзину для бумаг, ее содержимое загорелось. Физик задумался: «Если огонь распространится, это может быть опасно — высокая температура убьет нас. Нужно погасить огонь. Как это сделать? Посмо¬ трим... Можно охладить корзину ниже температуры возгорания бумаги или перекрыть доступ кислорода к огню... Для этого полью бумагу водой». Фи¬ зик взял корзину, отнес ее в душ, залил водой, после чего со спокойной душой отправился спать. Чуть позже и математик почувствовал, что под ним загорелась кровать, так как он просыпал на матрас пепел из своей трубки. Он ничуть не удивился, подумал: «Не стоит беспокоиться — эта проблема имеет решение»,— после чего преспокойно остался лежать в кровати, охваченной огнем. Несмотря на весь юмор этой истории, она дает понять, как мыслят и действуют математики вообще, а не только при тушении пожара. 83
СЧИТАЕМ (УЖЕ НЕ НА ПАЛЬЦАХ) Что мы видим и чего не видим В мире математики особый интерес вызывает поиск определенных математических объектов (графов с интересными свойствами или множеств натуральных чисел с особыми характеристиками) или доказательство того, что объекты с подобными свойствами не существуют. В первом случае достаточно одного конкретного при¬ мера. Но как быть, если такой пример мы не можем найти? Тогда, к сожалению, нам придется довольствоваться доказательством существования объекта с нужными свойствами. Приведем простой пример. Допустим, что в классе, где учится наш сын, был проведен медосмотр. По результатам медосмотра оказалось, что средний рост уче¬ ников в классе — один метр шестьдесят сантиметров. На основе этих данных мы не можем определить рост нашего сына (мы ведь не можем утверждать, что его рост равен одному метру и шестидесяти сантиметрам). Но несмотря на это можно с полной уверенностью высказать следующее утверждение: в классе найдется как минимум один ученик, рост которого будет больше либо равен одному метру и ше¬ стидесяти сантиметрам. Мы знаем, что такой ученик есть, но не можем сказать, кто это конкретно. Однако наш вывод очевиден, в противном случае средний рост учеников в классе будет меньше указанного значения. В этой главе мы покажем, как схожие идеи применяются для поиска скрытых структур в объектах, которые кажутся беспорядочными. Вы узнаете, что «абсолют¬ ный беспорядок не может существовать», точнее, что в достаточно больших систе¬ мах всегда можно выделить меньшие упорядоченные системы, связанные с графами, точками на плоскости и даже числовыми множествами. Чтобы лучше объяснить эти идеи, поговорим о голубях и ящиках, встречах одноклассников и эластичных сферах. Как разделить завтрак Опишем элементарный принцип, который имеет намного более важные послед¬ ствия, чем может показаться на первый взгляд. Допустим, что мы в порыве щедро¬ 84
СЧИТАЕМ (УЖЕ НЕ НА ПАЛЬЦАХ) сти купили для всех коллег свежих булочек — по одной булочке каждому. Мы мо¬ жем быть уверены — за завтраком наши коллеги точно будут пребывать в хорошем расположении духа. К сожалению, мы не учли, что один из них заболел и не пришел на работу. Следовательно, одна булочка оказалась лишней. Если мы хотим, чтобы все булочки были съедены за завтраком, то кто-то должен сделать над собой усилие и съесть не одну булочку, а целых две. Это пример так называемого принципа Дирихле, который в английском и неко¬ торых других языках называется принципом голубей и ящиков. Основан он на сле¬ дующем наблюдении: если мы хотим поместить N голубей в N — 1 ящик, то в каком- нибудь из ящиков обязательно окажутся два голубя или более. Этот пример с голу¬ бями аналогичен нашему примеру с булочками, мы всего лишь заменили булочки голубями, а коллег — ящиками. Забудем о голубях и булочках и сформулируем принцип Дирихле в общем виде: «Если у нас есть N шаров и мы хотим поместить их в М ящиков, где N > М, то как минимум в одном ящике будет лежать больше одного шара». Далее в этой же главе мы получим более сложные результаты, а пока что отметим следующее: принцип Дирихле гарантирует, что некий элемент обладает определен¬ ным свойством, но не указывает, какой именно. В примере с голубями какие-то два голубя обязательно окажутся в одном ящике, но мы не знаем, какие именно. Иными словами, мы доказали, что в рамках некой структуры существует другая, более мел¬ кая структура известной формы. Эта идея сыграет ключевую роль при изучении так называемой теории Рамсея и способов ее применения в геометрии, комбинаторике и теории чисел. Принцип Дирихле применяется множеством способов. Чтобы использовать его, достаточно уметь определять, что будет «голубями», а что — «ящиками» в каждом конкретном случае. Рассмотрим любопытный пример. Приведем перевод фрагмента введения из книги Пера Пуч-и-Адама «Курс метрической геометрии», том I «Ос¬ новы», о роли опыта, интуиции и логики в возникновении науки. Эта книга счита¬ 85
СЧИТАЕМ (УЖЕ НЕ НА ПАЛЬЦАХ) лась основным руководством для студентов инженерных специальностей в Испании во второй половине XX века. «Интуиция часто недостаточна или обманчива, чему имеется множество при¬ меров и любопытных фактов. Для краткости и простоты ограничимся двумя приведенными ниже примерами. 1. Допустим, что наш собеседник — человек средних знаний, которому известно, что в Испании проживает более 20 миллионов человек, а во¬ лосяной покров на голове человека содержит менее 5 волосков на ква¬ дратный миллиметр. Спросим его: найдется ли двое испанцев с одина¬ ковым числом волос на голове? Представить подобное сравнение ДИРИХЛЕ И ИСТОКИ АНАЛИТИЧЕСКОЙ ТЕОРИИ ЧИСЕЛ Иоганн Петер Густав Лежён Дирихле (1805, Дюрен - 1859, Гёттинген) известен своими от¬ крытиями в теории чисел. Он родился в бельгийской семье из Рихле (отсюда и фамилия Лежён Дирихле - le jeune de Richelet, «юноша из Рихле») и учился у лучших математиков своего вре¬ мени сначала в Германии, затем во Франции. Некоторое время он работал в университетах Вроцлава и Берлина, после чего возглавил кафедру в Гёттингене - должность заведующего осталась вакантной после смерти Гаусса. Дирихле женился на Ребекке Мендельсон, сестре известного композитора Феликса Мендельсона. Ученый не только описал названный в его честь принцип комбинаторики, о котором мы уже расска¬ зали, но й совершил важный вклад в математический анализ - в частности, он первым применил анали¬ тические методы для решения задач в теории чисел. С помощью этих методов в 1837 году Дирихле дока¬ зал гипотезу Гаусса о простых числах, получившую название теоремы Дирихле. Эта теорема, о которой мы поговорим чуть позже, считается первой теоремой аналитической теории чисел. 86
СЧИТАЕМ (УЖЕ НЕ НА ПАЛЬЦАХ) на практике невозможно, поэтому наш собеседник без малейших сомне¬ ний заявит, что ответить на этот вопрос невозможно. Тем не менее простейшие рассуждения помогут нам попасть туда, куда не приведет интуиция, и мы сможем ответить на этот вопрос утвер¬ дительно. Если бы у всех испанцев было разное число волос на голове, то у одного из них на голове было бы более 20 миллионов волосков, но для этого площадь его головы должна составлять более 4 квадратных метров. 2. ...» Пер Пуч-и-Адам использует принцип Дирихле в неявном виде: в его примере голубями будут жители Испании, ящиками — волосы на голове. В результате во¬ прос, на который, кажется, невозможно дать ответ, разрешается с помощью элемен¬ тарного математического принципа. Рассмотрим еще один пример, показывающий, как принцип Дирихле применяет¬ ся в геометрии. Допустим, что мы отметили пять точек внутри квадрата, длина сто¬ роны которого равна единице. Заметим, что всегда найдутся две точки, удаленные друг от друга не более чем на л/2 /2. Чтобы доказать это утверждение, разделим исходный квадрат на четыре равных квадрата со стороной 1/2. Пять точек внутри квадрата, длина стороны которого равна единице. По принципу Дирихле две из них будут расположены в одном квадрате со стороной 1/2. Эти две точки послужат доказательством исходного утверждения. Теперь мы можем определить, что будет выступать в роли «голубей» и «ящиков» в этой задаче. Так как даны пять точек и четыре квадрата, где их можно располо¬ жить, по принципу Дирихле две точки обязательно будут находиться внутри одного квадрата. Так как отрезок максимальной длины, который можно нарисовать внутри квадрата,— это его диагональ, точки, лежащие в одном квадрате со стороной 1/2, 87
СЧИТАЕМ (УЖЕ НЕ НА ПАЛЬЦАХ) будут отстоять друг от друга на расстояние, не превышающее длину диагонали ква драта, равную Любители математических задач и головоломок могут обобщить приведенные рассуждения и показать, что если мы изобразим внутри исходного квадрата десять как мы используем принцип Дирихле, нельзя указать, какие именно точки будут обладать этим свойством, но они обязательно существуют! Наконец, покажем, как принцип Дирихле применяется в арифметике. Проде¬ монстрируем задачу, которую чаще всего использовал Пал Эрдёш, чтобы опреде¬ лить способности юных математиков. Эрдёш имел талант предлагать нужные задачи нужным людям. Стремясь выявить математически одаренных людей, он завязывал дружеские отношения с молодыми студентами, которые проявляли особые способ¬ ности к наукам. Так, на обеде с юным Лайошем Поса Эрдёш задал ему следующий вопрос. Рассмотрим множество А = {1, 2, ..., 2п}. Пусть В — произвольное под¬ множество А, содержащее п + 1 элемент. Тогда на множестве В найдутся два эле¬ мента а и b такие, что один из них будет делителем другого. Обед еще не закончил¬ ся, а юный Поса уже нашел ответ! Несколько лет спустя он написал несколько работ в соавторстве с Эрдёшем и стал одним из авторитетнейших профессоров Венгрии. Перед тем как рассмотреть решение Поса, обратимся к конкретному примеру. Пусть п = 7. Подмножеством В (одним из многих возможных) будет множество {2, 3, 5, 6, 7, 8, 11, 13}. Оно содержит числа 2 и 8, 8 делится на 2 без остатка. Если читатель попробует найти подмножество из 8 элементов, которое не обладало бы этим свойством, то все его попытки окончатся неудачей. Чтобы доказать это, запишем элементы множества А в виде 2km, где т — не¬ четное натуральное число, a k больше либо равно 0 (оно будет равно 0, только если исходное число нечетное). Так как все элементы множества будут меньше либо рав¬ ны 2п, число т всегда будет принадлежать множеству {1, 3, 5, 7, ..., 2п — 1}. Обратите внимание, что это множество содержит п элементов, следовательно, т можно выбрать п способами. Поскольку теперь наше множество В содержит п + 1 элемент, согласно принципу Дирихле найдутся два элемента В, для которых точек, то найдутся две точки, отстоящие друг от друга не более чем на V2 / 3. Так 88
СЧИТАЕМ (УЖЕ НЕ НА ПАЛЬЦАХ) значения т будут равны. Наименьший из них будет иметь вид 2гш, наибольший — 2sm, где г < s. Нетрудно видеть, что первое число — делитель второго, что и тре¬ бовалось доказать. Принцип Дирихле позволяет решить широкий спектр задач, где требуется по¬ казать существование определенной закономерности или схемы в некой структуре, о которой мы не располагаем полной информацией. Как вы увидите в следующем разделе, этот принцип можно применить и в более сложных случаях, получив при этом удивительные результаты. Они дают начало прекраснейшему разделу матема¬ тики — теории Рамсея, которая охватывает логику, комбинаторику, анализ и другие области. На встрече одноклассников Ситуация, которую мы опишем, возможно, знакома читателю. Как-то раз, совер- шенно неожиданно, мы получаем весточку от бывшего одноклассника, с которым вместе учились в начальной школе. Жизненный путь нашего товарища по детским играм в большинстве случаев будет отличаться от нашего. Но чтобы вспомнить бы¬ лые времена и увидеть тех, с кем мы вместе играли длинными летними вечерами и кому впервые признавались в любви, мы организуем встречу всех старых дру¬ зей, с которыми когда-то делили эти незабываемые моменты. Идея, конечно, не¬ однозначна: с одной стороны, встреча одноклассников может воскресить в памяти детские и юношеские эмоции, но с другой — может открыть давно затянувшиеся сердечные раны. Предположим, что мы решили пойти на встречу. Мы удивимся, как много людей пришло, и постараемся узнать в пополневших серьезных мужчинах своих озорных товарищей по детским шалостям. За прошедшие годы могло про¬ изойти что угодно: можно считать, что все бывшие одноклассники постоянно под¬ держивали общение либо, напротив, никто не смог узнать старых друзей. Но в дей¬ ствительности все не так. Подобно тому как теорема Дирихле описывает критерии существования, в си¬ туациях, подобных нашей, мы можем гарантировать определенные закономерности в неупорядоченных множествах. Можно утверждать, что если на встречу пришло более шести человек, то среди них всегда найдутся трое, которые поддерживали 89
СЧИТАЕМ (УЖЕ НЕ НА ПАЛЬЦАХ) контакт между собой, либо, напротив, трое, которые потеряли друг друга из вида. Чтобы объяснить, почему это так, прибегнем к теории графов, которая позволит нам исключить ненужные подробности и сосредоточиться на важных условиях за¬ дачи. Каждому человеку на встрече одноклассников поставим в соответствие вер¬ шину с меткой (метками, к примеру, могут быть натуральные числа). Соединим все возможные пары вершин ребрами. Полученный граф, в котором каждая пара вершин будет соединена одним ребром, называется полным. В отличие от примеров из предыдущих глав, раскрасим ребра графа разными цветами: одним цветом будем обозначать ребра графа, соединяющие людей, которые поддерживали связь между собой, другим цветом — ребра, связывающие тех, кто все эти годы не общался друг с другом. На рисунках будем обозначать ребра разных цветов сплошными и пун¬ ктирными линиями. Обратите внимание, что связи между людьми будут симметрич¬ ными: если Иван поддерживал связь с Петром, то Петр, конечно же, поддерживал связь с Иваном. На рисунке показаны графы для пяти и шести человек, обозначен¬ ных числами от 1 до 5 и от 1 до 6 соответственно. Слева — ребра полного графа с пятью вершинами, где нет ни одного треугольника, все стороны которого имели бы одинаковый цвет. Справа — ребра полного графа с шестью вершинами. Обратите внимание, что во втором случае стороны треугольника с вершинами 246 имеют одинаковый цвет. Теперь, когда мы представили встречу выпускников в виде помеченного графа, нужно доказать следующее свойство: в полном графе, имеющем более шести вер¬ шин, ребра которого помечены двумя разными способами (сплошными или пун¬ ктирными линиями), всегда найдется три ребра, определяющие треугольник со сто¬ ронами, помеченными одинаково. Если найдутся три человека, которые поддержи¬ вали контакт между собой, им будут соответствовать три ребра, обозначенные 90
СЧИТАЕМ (УЖЕ НЕ НА ПАЛЬЦАХ) сплошными линиями и образующие треугольник. Также будет существовать треу¬ гольник, образованный пунктирными линиями, если найдется три человека, которые не поддерживали связь друг с другом. Докажем это утверждение. Сначала упростим задачу и приведем доказательство для множества из шести человек. Заметим, что мы можем выделить аналогичную структуру в любом полном графе, поэтому если мы докажем необходимое утвержде¬ ние для частного случая с шестью вершинами, то общее утверждение будет доказано автоматически. Рассмотрим вершину с номером 1. Этой вершине смежны пять других вершин, с которыми она соединена ребрами разного цвета. Ключевую роль играет следую¬ щее наблюдение: так как даны пять ребер и две разные метки (цвета), то найдется метка, которую будут иметь минимум три ребра. Этот результат можно получить, перебрав все возможные случаи либо применив принцип Дирихле. Допустим, что три ребра или более отмечены пунктирными линиями. Рассмотрим вершины, со¬ единенные с вершиной 1 пунктирными линиями. По нашей гипотезе, найдется как минимум три такие вершины. Предположим, что они имеют метки 2, 3 и 4 (для про¬ стоты не будем рассматривать другие варианты) — в противном случае достаточно поменять метки вершин. Возможны два случая: либо одно из ребер между вершинами 2, 3 и 4 будет отме¬ чено пунктирной линией, либо все три ребра будут отмечены сплошными линиями. В обоих случаях наблюдается требуемое свойство. В первом случае ребро, отмечен¬ ное пунктирной линией, вместе с ребрами, соединяющими вершины с вершиной 1, входит в треугольник из пунктирных линий. Во втором случае все ребра, соединяю¬ щие вершины 2, 3 и 4, будут отмечены сплошными линиями, таким образом, эти три вершины определят одноцветный треугольник. Рассмотрим ребра, отмеченные пунктирными линиями. В этом конкретном случае одноцветным будет треугольник с вершинами 2,3 и 4. 91
СЧИТАЕМ (УЖЕ НЕ НА ПАЛЬЦАХ) Таким образом, мы доказали, что в полном графе, имеющем шесть вершин или более, где ребра имеют две различные метки, всегда найдется треугольник, образо¬ ванный ребрами с одинаковыми метками. И вновь заметим, что доказанное утверж¬ дение всего лишь гарантирует существование такого треугольника, но мы не можем указать, какой именно треугольник обладает этим свойством. Усложним задачу. Мы доказали, что если на встречу одноклассников пришли шесть человек или более, то среди них обязательно найдутся трое, которые поддер¬ живали контакт между собой, либо, напротив, трое, которые потеряли друг друга из вида. Можно ли доказать похожее утверждение для групп из четырех, пяти или любого другого числа человек? Изложим задачу на языке теории графов. Выберем определенное значение k. Существует ли N такое, что любой полный граф с ребрами, помеченными двумя разными цветами, имеющий более N вершин, будет содержать одноцветный полный граф с k вершинами? Мы решили эту задачу для k = 3: любой полный граф, имеющий более шести вершин, содержит одноцветный треугольник. Можно ли показать, что это свойство будет выполняться для любого значения k? Как вы узнаете чуть позже, на этот вопрос можно ответить совершенно неожи¬ данным образом — при этом даже не потребуется строить граф! Хотя задача слиш¬ ком сложна и ее нельзя решить элементарными методами, вы увидите, что фунда¬ ментальные принципы решения останутся прежними. Решение этой задачи в общем виде, которое уже нельзя было получить по принципу Дирихле, открыло двери в но¬ вый мир внутри математической вселенной. В 1930 году Фрэнк Пламптон Рамсей (1903, Кембридж — 1930, Лондон) нашел способ решить эту задачу, доказав тео¬ рему Рамсея: «Пусть k — целое число. Существует значение N такое, что любой полный граф с ребрами, окрашенными в один из двух разных цветов, имеющий более N вершин, содержит одноцветный полный граф с k вершинами». Рамсей родился во влиятельной английской семье: его отец возглавлял Магда- лен-колледж (один из колледжей Кембриджского университета), а брат, Майкл Рамсей, впоследствии стал архиепископом Кентерберийским. В юности Рамсей продемонстрировал выдающиеся способности не только к математике, но и к дру¬ гим наукам, в частности экономике, психоанализу и теории принятия решений. Он окончил Кембриджский университет и с 1924 года до самой смерти работал 92
СЧИТАЕМ (УЖЕ НЕ НА ПАЛЬЦАХ) в Кингс-колледже, куда был принят по рекомендации выдающегося экономиста Джона Мейнарда Кейнса. Фрэнк Пламптон Рамсей. Научную карьеру Рамсея оборвала преждевременная смерть — он всю жизнь отличался слабым здоровьем. Но все же ученый успел совершить настоящий прорыв в науке. Он опубликовал всего три статьи по экономике, в которых использовал ва¬ риационное исчисление (изначально созданное для решения задач математической физики) и изложил принципиально новые идеи, связанные с теорией оптимального налогообложения и экономического роста. Лауреат Нобелевской премии по эконо¬ мике 1970 года Пол Самуэльсон называл работы Рамсея «великим наследием, ко¬ торое стало результатом его удивительной страсти к математике и знанию». В статье «Истина и вероятность» (Truth and Probability) Рамсей описал собственную теорию вероятностей, которая позднее стала основой современной теории субъективной ве¬ роятности, теории полезности и теории принятия решений. Исследователь интенсивно и плодотворно сотрудничал с философом Людвигом Витгенштейном, создателем позитивизма, и перевел его «Логико-философский трактат» на английский язык. Именно благодаря усилиям Рамсея Витгенштейн по¬ лучил должность в Кембридже — его книга была приравнена к докторской диссер¬ тации. 93
СЧИТАЕМ {УЖЕ НЕ НА ПАЛЬЦАХ) КЕЙНС, РАМСЕЙ И КЕЙНСИАНСКАЯ ЭКОНОМИЧЕСКАЯ ШКОЛА За свою короткую жизнь Фрэнк Рамсей успел до¬ биться поистине удивительных результатов как в теоретической математике, так и в других науках, особенно в экономической теории. Джон Мейнард Кейнс, первый барон Кейнс (1883, Кембридж - 1946, Сассекс), был основателем кейн¬ сианской экономической школы. Одно из основных положений этой школы - необходимость государ¬ ственного вмешательства (фискального и моне¬ тарного) в экономику для устранения проблем, возникающих при смене экономических циклов. Труды Кейнса имели настолько большое влияние, что многие считают его создателем современной макро¬ экономики. Кейнс знал о выдающихся способностях Фрэнка Рамсея и так отзывался о нем: Джон Мейнард Кейнс. «Уже в очень раннем возрасте - если мне не из¬ меняет память, ему было всего 16 - он заинтересовался проблемами экономики». Юный Рамсей уже в 19 лет опубликовал критическую рецензию на «Трактат о вероятности» Кейнса под названием «Господин Кейнс о вероятности». Критика Рамсея оказалась столь жест¬ кой, что Кейнсу пришлось пересмотреть некоторые свои рассуждения. Вклад Рамсея в математику, особенно в математическую логику, также имел ог¬ ромное значение: в труде «Основания математики» (The Foundations of Mathematics) он переработал некоторые логические теории, изложенные в «Началах математи¬ ки» Рассела и Уайтхеда. Движимый интересом к основам математики, Рамсей об¬ ратил внимание на так называемую проблему разрешения (Entscheidungsproblem). Суть ее в том, чтобы найти алгоритм, позволяющий определить, можно ли в рамках определенной теории доказать произвольное математическое высказывание, при¬ надлежащее к так называемой логике первого порядка. В работе «Об одной про¬ блеме формальной логики» Рамсей привел решение частного случая этой проблемы и сформулировал теорему, известную сегодня как теорема Рамсея. 94
СЧИТАЕМ (УЖЕ НЕ НА ПАЛЬЦАХ) Портрет Людвига Витгенштейна, создателя позитивизма и крупного исследователя языка. Эта теорема положила начало новому разделу математики — теории Рамсея, в которой изучаются упорядоченные структуры в неупорядоченных множествах. Вместе с теорией Рамсея родилась новая парадигма, новый «объект желания» — исследователи захотели понять, почему в определенных математических структурах, которые на первый взгляд кажутся совершенно неупорядоченными, существуют четко определенные и упорядоченные подструктуры. Теорема Рамсея гласит, что вне зависимости от того, как мы раскрасим ребра графа (то есть неупорядоченной структуры), в нем всегда найдется одноцветный полный подграф (упорядоченная подструктура). Любопытно, что совершенно независимо от ученого различные ис¬ следователи, незнакомые с его теоремой, обнаружили похожие результаты в самой природе, но в совершенно иных контекстах. Иными словами, открытие новой пара¬ дигмы независимо друг от друга совершили несколько ученых. Благодаря своей интуиции и проницательности Пал Эрдёш обнаружил упорядо¬ ченные структуры в совершенно беспорядочных объектах. Перенесемся в 1933 год, в маленькую будапештскую квартиру, где одна девушка, беспорядочно отметив на листе несколько точек, заметила нечто, что изменило всю ее дальнейшую жизнь. 95
СЧИТАЕМ (УЖЕ НЕ НА ПАЛЬЦАХ) Задача со счастливым концом Под статуей неизвестного летописца славнейшего царя Белы в маленьком парке Бу¬ дапешта группа молодых людей энергично обсуждала математику. Разговор начался случайно, с реплики одной из участниц. В какой-то момент она сделал невинную и, казалось бы, ничем не примечательную ремарку, не подозревая, что она впослед¬ ствии изменит всю ее жизнь. Из этой ремарки позднее родилась так называемая задача со счастливым концом. В 1933 году юная Эстер Клейн совершенно случайно сделала интересное откры¬ тие, имевшее намного большие последствия, чем она могла предположить. Чтобы понять суть ее догадки, сначала дадим определение выпуклой оболочке множества точек. Возьмем обычную резинку и рассмотрим множество точек плоскости, изо¬ браженных в области, границей которой будет резинка. Предположим, что эти точ¬ ки зафиксированы на плоскости, подобно столбам, и сдвигать их нельзя. Резинка, напротив, допускает любые деформации, при которых она не будет проходить над какой-либо из точек. Предположим, что мы начали натягивать резинку. В какой-то момент она коснется нескольких точек. Когда резинку уже нельзя будет растягивать дальше, область, заключенная внутри нее, определит выпуклую оболочку исходного множества точек. Резинка и множество точек, заключенных внутри нее. На рисунке слева изображена резинка до натяжения, на рисунке справа — после. 96
СЧИТАЕМ (УЖЕ НЕ НА ПАЛЬЦАХ) Выпуклая оболочка множества точек обладает интересными свойствами. К при¬ меру, она всегда будет выпуклым многоугольником, то есть многоугольником, в ко¬ тором для любых двух точек соединяющий их отрезок будет лежать внутри много¬ угольника. Многоугольник также является выпуклым, если все его внутренние углы меньше 180 градусов. Выпуклый и невыпуклый многоугольник. Рассмотрим пять точек, расположенных на плоскости в общем положении, то есть так, что никакие три точки не лежат на одной линии. Допустимо любое расположение точек, для которого выполняется указанное условие. Покажем, что на этом множестве точек всегда найдется подмножество из четырех точек, которые определяют выпуклый четырехугольник. В доказательстве используем внешнюю оболочку этого множества точек, которая может иметь три, четыре или пять сторон. Рассмотрим все возможные случаи по отдельности. 1. Допустим, что внешняя оболочка имеет пять сторон. В силу выпуклости пяти¬ угольника, для того чтобы получить выпуклый четырехугольник, достаточно рассмотреть подмножество из любых четырех его вершин. 2. Рассмотрим случай, когда внешняя оболочка имеет четыре стороны. Объем¬ ных рассуждений не требуется: вершинами искомого четырехугольника будут точки исходного множества, которые определяют внешнюю оболочку. 3. Наконец, рассмотрим случай, когда внешняя оболочка представляет собой треугольник. Это более сложный случай, требующий объемных рассуждений. Согласно исходной гипотезе, две точки, не находящиеся на эластичной грани¬ 97
СЧИТАЕМ (УЖЕ НЕ НА ПАЛЬЦАХ) це внешней оболочки, будут заключены внутри треугольника. Рассмотрим прямую, соединяющую эти точки. Две точки исходного треугольника будут располагаться по одну сторону этой прямой (это следует из условия, согласно которому точки исходного множества находятся в общем положении). Если теперь мы соединим эти две точки с точками, которые находятся внутри треу¬ гольника, получим выпуклый четырехугольник. Три возможных случая в задаче Эстер Клейн. Мы решили задачу, известную как задача со счастливым концом: «На множестве из пяти точек плоскости всегда найдутся четыре точки, опреде¬ ляющие выпуклый четырехугольник». Читатель наверняка недоумевает, почему задача получила такое название, ведь она вовсе не имеет счастливого конца. Все дело в финале этой истории. Юные вен¬ герские математики, натренированные решать математические задачи, быстро обоб¬ щили утверждение Эстер Клейн для пятиугольников. Но верно ли, что для данно¬ го п существует такое значение Дп), что любое множество, состоящее более чем из Дп) точек в общем положении, содержит выпуклый п-угольник? Ответ на этот вопрос был далеко не очевидным. Увидев новые горизонты, которые открыло наблюдение Эстер Клейн, горизон¬ ты, в которых сливались воедино геометрия и комбинаторика, Эрдёш приступил к работе над задачей вместе со своим другом Дьёрдем Секерешем. Талантливый ма¬ тематик почувствовал, что открытие Клейн было лишь частным случаем в намного более общей теории об упорядоченных структурах среди беспорядка, которая через несколько лет стала известной как теория Рамсея. Спустя некоторое время Эрдёшу 98
СЧИТАЕМ (УЖЕ НЕ НА ПАЛЬЦАХ) и Секерешу удалось решить задачу, и в 1933 году они сформулировали знаменитую Если мы рассмотрим N > Дп) точек на плоскости в общем положении, то среди них всегда найдется подмножество из п точек, определяющее выпуклый п-угольник». Теорема Эрдёша — Секереша формально относится к геометрии, но описывает общие закономерности, сокрытые посреди хаоса. Ученые открыли новую галактику в математической вселенной. Спустя несколько лет Эрдёш обнаружил, что суть его теоремы уже сформулировал юный математик Рамсей, в честь которого была на¬ звана целая теория. ОДИН НЕПРОСТОЙ ВОПРОС Естественным образом возникает вопрос - к какому числу ближе значение f(n) в теореме Эр¬ дёша - Секереша: к 2n_2 + 1 или Этот вопрос до сих пор остается открытым. Более того, Эрдёш и Секереш, помимо своей теоремы, также высказали следующую гипотезу: «Любое множество из 2n_2 + 1 точек плоскости в общем положении содержит подмножество из л точек, образующих выпуклый л-угольник». Сегодня известно, что эта гипотеза верна для значений л, меньших либо равных 6. Для остальных значений известно лишь, что f(n) удовлетворяет следующему неравенству: теорему Эрдёша — Секереша: «Пусть п — целое число. Тогда существует значение /(п) такое, что 99
СЧИТАЕМ (УЖЕ НЕ НА ПАЛЬЦАХ) И все же, почему теорема Эстер Клейн получила такое необычное название? Все дело в том, что в ходе совместной работы Эрдёша и Секереша последний познако¬ мился с Эстер Клейн, они поженились и прожили вместе всю оставшуюся жизнь. Именно поэтому Эрдёш, который, можно сказать, стал их сватом, и назвал теорему «теоремой со счастливым концом». Дьёрдь Секереш и Эстер Клейн спустя много лет после «счастливого конца». Они прожили всю жизнь вместе и умерли с разницей в один час. И снова о теории вероятностей. Вероятностный метод Вы увидели, что для вычисления вероятности выигрыша в азартной игре нужно ис¬ пользовать методы комбинаторики, позволяющие подсчитать число благоприятных исходов. Эти подсчеты помогают определить, стоит ли делать ставку или разумнее воздержаться. Методы комбинаторики широко используются в теории вероятно¬ стей. В этом разделе мы покажем, что некоторые выводы в комбинаторике можно получить совершенно неожиданным образом — с помощью теории вероятностей! Основное правило, которым мы будем руководствоваться, звучит так: «вероятное событие — это возможное событие». Иными словами, если мы доказали, что некое событие может произойти с определенной вероятностью, то оно возможно. К при¬ меру, маловероятно, что в пустыне Сахара пойдет дождь, однако вероятность этого события отлична от нуля, поэтому оно все-таки может произойти. 100
СЧИТАЕМ (УЖЕ НЕ НА ПАЛЬЦАХ) Важно помнить, что вероятность — это число, заключенное между 0 и 1. Веро¬ ятность, равная 0, соответствует невозможному событию, вероятность, равная 1, — абсолютной истине. Если вероятность некоторого события равна числу р, заключен¬ ному на интервале от 0 до 1, то вероятность противоположного события будет равна 1 — р. К примеру, если вероятность того, что в нашем городе завтра пойдет дождь, равна р, то вероятность того, что завтра дождя не будет, равна 1 — р. Это объясня¬ ется тем, что с абсолютной уверенностью можно утверждать: «завтра либо пойдет дождь, либо нет». С учетом сказанного заметим: если мы доказали, что вероятность некоторого события строго меньше 1, то вероятность противоположного события (то есть ве¬ роятность того, что рассматриваемое событие не произойдет) будет отлична от 0. Это противоположное событие будет возможным, так как существует некая вероят¬ ность, сколь бы малой она ни была, что это событие произойдет. Таким образом, если мы доказали, что вероятность некоторого события строго меньше 1, то проти¬ воположное событие обязательно будет возможным. Это утверждение поможет нам гарантировать существование определенных объектов с интересными свойствами, при этом нам не потребуется описывать, как такие объекты строятся. Наша цель — объединить эту идею с правилами перечислительной комбинато¬ рики, о которых вы узнали в начале этой книги, чтобы получить некоторые оценки, имеющие отношение к теореме Рамсея. Допустим, что дан полный граф с N верши¬ нами и каждое его ребро раскрашено в один из двух цветов. Раскрасим ребра графа следующим образом: для каждого ребра подбросим равновесную монету (вероят¬ ность выпадания орла или решки будет одинаковой и равной 1/2), после чего рас¬ красим его тем или иным цветом в зависимости от того, какой стороной вверх упадет монета. Какова вероятность того, что граф будет раскрашен заранее определенным образом? Обратите внимание, что полный граф с N вершинами имеет столько же ре¬ бер, сколько и неупорядоченных пар вершин. Неупорядоченные пары вершин пред¬ ставляют собой подмножества из двух вершин. Общее число таких подмножеств будет равно числу сочетаний по 2 из N, то есть Каждое из ребер графа будет раскрашено в тот или иной цвет с вероятностью 1/2. По правилу Лапласа общая вероятность того, что граф будет раскрашен за¬ данным образом, равна 101
СЧИТАЕМ (УЖЕ НЕ НА ПАЛЬЦАХ) 1 Иными словами, все возможные схемы раскрашивания будут иметь одинаковую вероятность! Не следует удивляться — аналогичный результат мы продемонстриро¬ вали в примере с лотереями в одной из предыдущих глав. Теперь проведем чуть более сложные подсчеты: оценим, с какой вероятностью полный граф с N вершинами при раскрашивании указанным способом будет со¬ держать полный одноцветный подграф с k вершинами. Вычислим искомую оценку путем следующих рассуждений. Выберем k из N вершин графа, которые образуют одноцветный полный граф с k вершинами. Эти k вершин можно выбрать N к разными способами. Биномиальный коэффициент в этой формуле указывает, сколь¬ кими способами можно выбрать k вершин из N, а коэффициент 2 указывает, что ребра графа могут быть раскрашены одним из двух возможных цветов. Вероятность того, что мы раскрасим одним цветом все V Ч2У ребер, соединяющих выбранные вершины, равна 2 торых равно {!) Остальные ребра, число ко- г V N 2 \ могут быть раскрашены любым цветом, следовательно, результат броска монеты для этих ребер не имеет значения. Вероятность того, что при случайном раскрашивании полного графа с N вер¬ шинами мы получим одноцветный полный граф с k вершинами, будет меньше либо равна 102
СЧИТАЕМ (УЖЕ НЕ НА ПАЛЬЦАХ) СЛУЧАЙНЫЕ ГРАФЫ Для некоторых событий наиболее эффективным методом анализа является вероятностный анализ. Сюда относятся динамика социальных сетей, практически мгновенное создание тысяч интернет-сайтов - их можно объяснить только с помощью теории вероятностей. Отправной точкой в объяснениях подобных феноменов служат так называемые случай¬ ные графы, построить которые можно множеством способов. Один из таких графов, модель G(n, р), описанная Эдгаром Гилбертом в 1957 году, строится следующим образом. Рассмотрим п вершин и для каждой пары вершин проведем ребро с вероятностью р (вероятность того, что мы не проведем это ребро, будет равна 1 - р). Эта модель, которая может показаться прими¬ тивной, в течение нескольких десятилетий применялась для решения сложных вероятностных задач, связанных с графами. Похожие модели описали Эрдёш и его коллега, венгерский математик Альфред Реньи, в 1959 году. Любопытнее всего то, что эти ученые не могли и предположить, какую роль сы¬ грают их идеи в изучении компьютерных сетей или распространении эпидемий. Процитируем самого Эрдёша: «Эволюция случайных графов моделирует (в упрощенном виде) эволюцию некоторых реальных коммуникационных сетей, к примеру, сетей железных дорог или электросетей в странах и регионах, а также рост неорганических и органических структур и даже раз¬ витие социальных связей. Разумеется, если кто-то захочет описать какую-либо реальную ситуацию, нашу модель случайного графа потребуется заменить более сложной и более реалистичной моделью». Слова «меньше либо равна» означают, что мы привели верхнюю границу иско¬ мой вероятности. Вполне может случиться так, что при раскрашивании графа мы получим сразу несколько одноцветных полных графов с k вершинами. Рассмотрим приведенное выражение подробнее. Если оно меньше 1, это означает, что событие, противоположное рассматриваемому (иными словами, раскрашивание графа, при котором в нем не будет одноцветных полных графов с k вершинами), произой¬ дет с некоторой вероятностью, следовательно, является возможным. Если приве- 103
СЧИТАЕМ (УЖЕ НЕ НА ПАЛЬЦАХ) денное выше выражение меньше 1, будут существовать способы раскрашивания ис¬ ходного графа, при которых в нем не будет одноцветных полных подграфов. Нетрудно видеть, что первое значение N, для которого это выражение будет больше 1 (и, следовательно, приведенные выше рассуждения уже не будут выпол¬ няться), равно N = 2к/2. Мы получили нижнюю границу для теоремы Рамсея: «Чтобы полный граф с N вершинами при раскрашивании ребер в один из двух цветов случайным образом всегда содержал одноцветный полный подграф с k вер¬ шинами, число N должно быть равно как минимум N = 2Ь/2». Это утверждение, доказанное Эрдёшем в 1947 году, дало начало использованию вероятностных методов в комбинаторике. Минимальное значение, для которого вы¬ полняется теорема Рамсея, называется числом Рамсея и обозначается R(k) (в этой главе мы уже показали, что R(3) = 5). Первый метод, изложенный выше, стал первым шагом к созданию ряда методов, цель которых — получение в комбинаторике, геометрии и теории чисел различных структур, в которых основную роль играет вероятность. Подобные структуры ос¬ нованы на так называемом вероятностном методе. Теоретическое и практическое значение этого метода в математике столь велико, что ему посвящены сразу два специализированных научных журнала: Combinatorics, Probability and Computing («Комбинаторика, вероятность и вычисления») и Random Structures and Algorithms («Случайные структуры и алгоритмы»). Один важный результат, полученный с помощью этого вероятностного метода без построений в явном виде, можно встретить и в теории графов. Он достаточно сложен, поэтому мы ограничимся его кратким изложением, но сначала рассмотрим некоторые определения. Хроматическое число графа — это минимальное число цветов, требуемое для раскрашивания вершин графа таким образом, чтобы любые две вершины, соединенные ребром, были окрашены в разный цвет. Обхватом на¬ зывается длина наименьшего цикла в графе. К примеру, полный граф с п вершинами имеет хроматическое число п (каждая его вершина соединена со всеми остальными, следовательно, чтобы раскрасить их требуемым образом, понадобится п цветов) и обхват, равный 3 (любые три вершины полного графа определяют треугольник — он и будет наименьшим циклом в графе). 104
СЧИТАЕМ (УЖЕ НЕ НА ПАЛЬЦАХ) КАК ТОЧНО ВЫЧИСЛИТЬ ЧИСЛО РАМСЕЯ? Помимо оценки, полученной Эрдёшем, известно, что 2 kl2<R(k)< Вычислить точное значение R(k) совсем не просто - для этого необходимо выполнить огром¬ ное количество расчетов. Достаточно привести оценку Эрдёша для к - 5: Допустим, что мы хотим проверить, будет ли некое целое число л, находящееся в этом интер¬ вале, равно числу Рамсея R(5). Нам нужно проверить, что полный граф с л вершинами при лю¬ бом раскрашивании ребер будет содержать одноцветный полный подграф с пятью вершинами и что существует как минимум один способ раскрасить ребра полного графа с л - 1 вершиной так, чтобы он не содержал одноцветный полный подграф с пятью вершинами. Объем расчетов для графа с л вершинами будет иметь порядок таково число возможных способов раскрасить граф. Даже для небольших значений л это число будет астрономическим (для л - 100 оно будет примерно равным 210000/2), поэтому задача не допускает прямого алгоритмического решения (компьютер не в силах выполнить такое число действий). Сам Эрдёш предчувствовал сложность задачи и как-то раз так высказал сомнение относительно того, что решение когда-либо будет найдено: «Допустим, что инопланетяне захватили Землю и угрожают уничтожить ее, если через год люди не назовут им точное значение числа Рамсея R(5). За год лучшие умы чело¬ вечества и самые быстрые компьютеры, возможно, смогут рассчитать точное значение Я(5). Но если инопланетяне попросят вычислить значение R(6), нам останется только нанести упреждающий удар». 105
СЧИТАЕМ (УЖЕ НЕ НА ПАЛЬЦАХ) 1 1 3 1 2W 3 Гоаф с хроматическим числом 3 (раскраска вершин обозначена числовыми метками) и обхватом, равным 4 (граф не содержит треугольников, однако имеет цикл длиной 4). Обратите внимание, что если граф содержит много ребер, то многие его вершины окажутся связаны между собой, следовательно, хроматическое число графа будет велико. Найти очень короткие циклы в таком графе нетрудно, и его обхват будет небольшим (как в нашем примере с полным графом). Если же, напротив, граф со¬ держит мало ребер, его хроматическое число будет невелико, так как между собой будут связаны лишь немногие его вершины. Обхват такого графа, как мы уже от¬ мечали, будет большим. Таким образом, между обхватом графа и его хроматическим числом существует обратная зависимость: большим хроматическим числам соответ¬ ствуют маленькие обхваты, маленьким хроматическим числам — большие обхваты. Естественно, возникает вопрос: можно ли построить граф, для которого и обхват, и хроматическое число будут большими? Существование такой структуры Эрдёш доказал в 1959 году с помощью передо¬ вых вероятностных методов. Суть его рассуждений была прежней: чтобы доказать существование некоего объекта, достаточно доказать, что он наблюдается с ненуле¬ вой вероятностью. Теорема Эрдёша о хроматическом числе гласит: «Для любых фиксированных значений г и s существует граф, хроматическое чис¬ ло которого больше г, а обхват больше s». Алгоритм построения графа, который обладал бы двумя указанными свойствами одновременно (большим обхватом и большим хроматическим числом), до сих пор не найден. Как видите, порой нам, как математику из анекдота, нужно довольство¬ ваться самим фактом существования решения и спокойно отправляться спать, даже если весь дом охвачен огнем. 106
Глава 5 Комбинаторика чисел Порядок — прекраснейшее украшение жилища Пифагор Существует особая разновидность комбинаторики, связанная с целыми числами и их свойствами,— комбинаторика, которую можно считать элементарной, по¬ скольку ее задачи напрямую вытекают из базовых определений. Этот раздел ма¬ тематики, находящийся на стыке между теорией чисел и комбинаторикой, обычно называют комбинаторной, или аддитивной, теорией чисел. И вновь краеугольный камень этой дисциплины заложил Пал Эрдёш. В аддитивной теории чисел ведутся обширные исследования — во многом благодаря результатам и задачам, о которых мы расскажем в этой главе. Начнем с простых чисел — несомненно, одного из основных понятий арифмети¬ ки. Затем мы расскажем о функциях представления, которые содержат множество важной информации и достойны звания основных элементов комбинаторики чисел. Мы продемонстрируем, как функции представления связаны со старыми задачами, которые до сих пор не решены, в частности со знаменитой гипотезой Эрдёша — Ту- рана. Далее мы вновь коснемся теории Рамсея и рассмотрим новый тип комбинатор¬ ных задач из аддитивной теории чисел. В частности, вы узнаете, что еще в 1927 году Бартель Леендерт ван дер Варден сформулировал теорему, связанную с теорией Рамсея, но имеющую отношение не к графам, а к числам. Живительно, что первые результаты в теории Рамсея были получены разными авторами в разных областях и совершенно независимо друг от друга, но примерно в одно и то же время. Теорема ван дер Вардена — всего лишь верхушка огромного айсберга. Мы объясним, что такое плотность множества чисел, и покажем, что при определенных условиях, нося¬ щих весьма общий характер, мы можем многое узнать о внутренней структуре мно¬ жества. Также мы расскажем о теореме Семереди — вершине комбинаторики вто¬ рой половины XX века, и закончим наш рассказ теоремой Грина — Тао, доказанной в 2003 году Беном Грином и Теренсом Тао. За доказательство теоремы Теренс Тао был удостоен Филдсовской премии на Международном математическом конгрессе 107
КОМБИНАТОРИКА ЧИСЕЛ в Мадриде в 2006 году. Но путь к математическому Олимпу, где обитают лауреаты Филдсовской премии, мы начнем из подземелья, то есть с самых основ арифметики. Основы арифметики Не боясь ошибиться, можно сказать, что простые числа — самые популярные из всех чисел. Они просты и естественны, их очень просто определить, но при этом они таят удивительные математические загадки. Как говорил немецкий математик Леопольд Кронекер, «Бог создал целые числа, все остальное — дело рук человека». Следовательно, можно сказать, что в простых числах заключена сама суть матема¬ тики. ФИЛЬМ «КУБ» И АСТРОНОМИЧЕСКИЕ ВЫЧИСЛЕНИЯ В фильме «Куб» режиссера Винченцо Натали (Канада, 1997) группа незнакомцев просыпается по¬ среди футуристической кубической комнаты. Они должны найти выход из нее, пройдя через мно¬ жество комнат, полностью идентичных первой. Со временем герои фильма обнаруживают, что в не¬ которых комнатах находятся смертельные ловушки. Студентка-математик Левен разгадывает шифр, указывающий, в каких комнатах нет ловушек: на двери в каждую комнату записаны три трехзначных числа. Если какое-то из этих чисел равно некоторой степени простого числа, то в комнате находится ловушка, которую нужно избежать. Таким образом, чтобы обнаружить ловушку, нужно найти простые делители всех чисел, записанных на двери в комнату. Однако Левен утверждает, что произвести необходимые расчеты очень сложно: «...Никто в целом мире не сможет сделать эти расчеты в уме. Посмотри на числа: 567,898,545. Разложить их на множители невозможно - потребуется огромный объем расчетов!» Заметьте, что все исходные числа меньше 1000, а >/1000 =31,62... Таким образом, чтобы опре¬ делить, является ли трехзначное число простым, достаточно определить, делится ли оно на 2,3,5, 7, И, 13,17,19,23,29 или 31. Чтобы произвести подобные расчеты в уме, необходимы терпение и сноровка, однако они вполне посильны. Более того, в нашем случае нетрудно показать, что 567 делится на 3, 898 - на 2, 545 - на 5. 108
КОМБИНАТОРИКА ЧИСЕЛ Как вам хорошо известно, натуральное число называется простым, если оно де¬ лится только на 1 и само себя. Простые числа составляют фундамент арифметики, следовательно, понимать их необходимо. В первую очередь возникает вопрос — как определить простые числа? Иными словами, существуют ли какие-то критерии, по¬ зволяющие определить, является ли данное целое число п простым? В теории этот вопрос тривиален — достаточно перебрать все возможные потенциальные делите¬ ли п и убедиться, что остаток от деления всегда будет отличен от нуля. Но на прак¬ тике определение простых чисел требует объемных вычислений: представьте, что нам нужно найти делители числа, состоящего, например, из миллиона цифр. Эта задача неподвластна современным компьютерам. Как правило, подобные задачи Афиша фильма «Куб». На Неделе фильмов ужасов и фантастики 1998 года, прошедшей в Ситжесе, этот фильм был удостоен двух премий — «Лучший фильм» и «Лучший сценарий». 109
КОМБИНАТОРИКА ЧИСЕЛ очень сложны, так как вычислительные мощности компьютеров все же ограничены. Эта сложность используется, к примеру, в системах шифрования данных при защите транзакций, выполняемых через интернет. Следующий вопрос звучит так: существуют ли общие формулы, позволяющие получить все простые числа или хотя бы некоторые из них? Так, выражения п2 win позволяют найти все квадраты и все числа, кратные 7, соответственно (для это¬ го достаточно заменить п натуральными числами). Существует ли математическая формула, результатом которой для каждого п будет простое число? Такой формулы не существует, поскольку простые числа поистине загадочны. Можно даже сказать, что они распределены случайным образом. Так как найти общую формулу для вычисления простых чисел невозможно, воз¬ никает вопрос: как определить, сколько простых чисел меньше данного числа п? И вновь ответить в общем виде нельзя. Любопытно, что поиском приближенных решений этой задачи занимались многие выдающиеся математики разных эпох. По легенде, в 1792 году король математиков Карл Фридрих Гаусс (1777, Бра¬ уншвейг — 1855, Гёттинген), когда ему было всего 15 лет, получил удивительный результат: хотя количество простых чисел, меньших данного, по всей видимости, не подчинялось никакой закономерности, его рост описывался формулой п In (и) Это означает, что разность между реальным количеством простых чисел и полу¬ ченным по формуле намного меньше п, то есть точность приближения очень вы¬ сока. Таким образом, функция, полученная Гауссом, достаточно точно описывает реальную функцию распределения простых чисел. Живительно, что этот результат получил пятнадцатилетний юноша, выполнивший расчеты вручную! Гаусс отступил¬ ся от задачи, посчитав ее слишком сложной. Много лет спустя, когда эта задача стала известной всем, он вновь удивил научное сообщество, опубликовав решение, найденное еще в юности. На основе результатов Гаусса в 1798 году свою гипотезу сформулировал Адриен Мари Лежандр (1752, Париж — 1833, там же), который, рассмотрев частные слу¬ 110
КОМБИНАТОРИКА ЧИСЕЛ чаи, пришел к тем же выводам, что и Гаусс семью годами ранее. Над решением этой задачи упорно трудились многие математики, но ответ всякий раз ускользал от них. Именно изучению количества простых чисел, меньших данного числа, посвящена единственная работа Бернхарда Римана (1826, Брезеленц, Германия — 1866, Се- ласка, Италия) по теории чисел. Риман, ученик Гаусса, в 1859 году написал свою знаменитую статью «О числе простых чисел, не превышающих заданной величи¬ ны», в которой попытался описать аналитический метод решения этой задачи. Най¬ ти решение не удалось, однако работа ученого стала одной из важнейших в теории чисел XIX века — в ней описывается, возможно, самая знаменитая функция в те¬ ории чисел, дзета-функция Римана, а также изложена важнейшая математическая гипотеза XX столетия — гипотеза Римана. Прошло много лет, и только в 1898 году, независимо друг от друга, Жак Адамар и Шарль Жан ла Валле Пуссен, взяв за основу работу Римана, нашли решение этой задачи, применив сложные аналитические методы. Гипотеза Лежандра стала теоре¬ мой о распределении простых чисел, которая звучит следующим образом: «Количество простых чисел, меньших п, имеет порядок —— ». Ми) В доказательстве теоремы о распределении простых чисел, которое использова¬ лось в первой половине XX века, применялись очень сложные аналитические ме¬ тоды, связанные с дзета-функцией Римана, поэтому считалось, что теорема о рас¬ пределении простых чисел описывает некоторые неотъемлемые и весьма сложные особенности функций, упоминающиеся в ее доказательстве. Эту точку зрения пре¬ красно выразил Годфри Харолд Харди на конференции, прошедшей в 1921 году под эгидой Копенгагенского математического общества: «Элементарное доказательство теоремы о распределении простых чисел не¬ известно. Логично задаться вопросом — существует ли вообще подобное до¬ казательство? Если кто-нибудь найдет элементарное доказательство данной теоремы, это будет означать, что все нынешние точки зрения ошибочны, что основы математики выглядят совершенно иначе, нежели мы думаем, и пришел час переписать нынешнюю теорию». ill
КОМБИНАТОРИКА ЧИСЕЛ Сверху вниз, слева направо — Гэусс, Лежандр и Риман, которые посвятили изучению распределения простых чисел целых сто лет. В 1948 году математики всего мира лишились дара речи: Пал Эрдёш объявил, что вместе с еще одним великим математиком, Атле Сельбергом (1917—2007), 112
КОМБИНАТОРИКА ЧИСЕЛ обнаружил элементарное доказательство теоремы о распределении простых чисел, в котором использовались исключительно основные свойства логарифмов. К несча¬ стью, это открытие заслонили другие события, никак не связанные с математикой. Какой ученый не хочет знать, что его имя останется в вечности и в его честь будет названа бессмертная теорема? Теорема о распределении простых чисел причинила немало беспокойств Палу Эрдёшу и стала темой одного из самых жарких споров о теории чисел в XX веке. Поводом для дискуссии стал результат, полученный, но не опубликованный Сельбергом. Этот гениальный скандинавский математик нашел альтернативное и очень простое доказательство теоремы Дирихле, также известной как теорема о простых числах в арифметической прогрессии (о ней мы поговорим чуть позже). Хотя Сельберг не опубликовал доказательство, он объяснил его венгерскому мате¬ матику Палу Турану, который в то время находился в Принстоне с визитом. Затем Сельберг покинул Принстон и отправился с рабочей поездкой в Канаду. За время его отсутствия Туран взял на себя смелость провести в Институте перспек¬ тивных исследований семинар, на котором он рассказал о результатах, полученных Сельбергом. Волею судьбы в аудитории оказался и Пал Эрдёш. Проницательный венгр понял, что изложенный Тураном новый элементарный подход поможет найти принципиально иное доказательство теоремы о распределении простых чисел, и изо всех сил принялся за работу. По возвращении из Канады Сельберг обнаружил, что Эрдёш с головой ушел в работу над доказательством: он был уверен, что стоит немного поднажать, и путь к заветному доказательству откроется. Сельберг оптимизма Эрдёша вслух не раз¬ делил, хотя при этом покривил душой: он тоже понимал, что путь к элементарно¬ му доказательству теоремы о распределении простых чисел открыт. Сельберг, как и Эрдёш, отличался математической интуицией и умением находить простые и эле¬ гантные решения сложных задач. Однако он был одиночкой и не работал с соавто¬ рами — в отличие от Эрдёша, который, напротив, занимал первое место по числу соавторов среди всех математиков. Спустя несколько дней Эрдёш смог уточнить результат, полученный Сельбергом, и, кроме того, доказал теорему о распределении простых чисел элементарными методами. Поиски, длившиеся свыше 200 лет, на¬ конец увенчались успехом. 113
КОМБИНАТОРИКА ЧИСЕЛ Атле Сельберг, автор «фундаментальной леммы», которая стала основой элементарного доказательства теоремы о распределении простых чисел. Кесарю — кесарево: Эрдёш опять обратился к Сельбергу, чтобы обрадовать его. Но тот вновь был недоволен: после того как Эрдёш опубликовал свое доказатель¬ ство, теорема стала называться его именем. Несмотря на всю скромность Сельберга, такое положение дел не понравилось норвежцу, и когда Эрдёш предложил ему опу¬ бликовать совместную статью, он решительно отказался. В результате два этих уче¬ ных опубликовали каждый свое доказательство теоремы (Сельбергу удалось адап¬ тировать свой метод нужным образом и доказать теорему независимо от Эрдёша). Именно за это доказательство (а также за вклад в аналитическую теорию чисел) Сельберг был удостоен Филдсовской премии в 1950 году. Эрдёш никогда не полу¬ 114
КОМБИНАТОРИКА ЧИСЕЛ чил эту престижную награду, хотя позднее, в 1951 году, был отмечен авторитетной премией Фрэнка Нельсона Коула, присуждаемой Американским математическим обществом за работы по теории чисел. Функции представления Рассмотрим комбинаторную задачу, которая заметно отличается от всех изложен¬ ных выше. Она покажется вам проще, чем уже рассмотренные, но специалисты по комбинаторике знают — в этой дисциплине существует множество задач с про¬ стой формулировкой, которые невозможно решить. Начнем с элементарной задачи, которую поймут даже дети — более того, они непременно найдут решение! Дано множество натуральных чисел А = {0, 1, 3, 4, 5, 8}. Сколькими способами можно представить выбранное натуральное число в виде суммы двух элементов множества А (возможно, равных)? К примеру, 0 можно за¬ писать единственным образом как 0 + 0, 1 — как 1 + 0 или 0 + 1 (обратите внима¬ ние, что порядок слагаемых не имеет значения), 2 — только как 1 + 1,8 — как 3 + + 5, 5 + 3, 8 + 0, 0 + 8 или как 4 + 4. На языке математики число способов, ко¬ торыми можно представить натуральное число п в виде суммы двух элементов мно¬ жества А, называется числом представлений этого натурального числа относительно А, или функцией представления, связанной с А. В нашем примере число представ¬ лений 0 и 2 равно 1 (эти числа можно представить только как 0 + 0 и 1 + 1 соот¬ ветственно), число представлений 5 равно 4(5 + 0, 0 + 5,1 + 4и4 + 1),а число 15 нельзя представить ни одним способом, следовательно, соответствующее число представлений будет равно 0. Сформулированная задача проста, поскольку множество А — конечное: так как число элементов А можно сосчитать на пальцах, это множество содержит наиболь¬ ший элемент, и любое число, в два раза большее этого элемента, нельзя представить в виде суммы двух элементов множества. В нашем примере число представлений числа 16 равно 1 (8 + 8), а для любого п > 16 функция представления будет рав¬ на 0, так как элементы А слишком малы, чтобы п можно было представить требу¬ емым способом. Эта задача представляет особый интерес для бесконечного мно¬ жества А. Высочайшая ее сложность связана именно с тем, что рассматриваемое множество содержит бесконечно много элементов. 115
КОМБИНАТОРИКА ЧИСЕЛ Начнем с того, что радикально упростим задачу. Существует ли бесконечное множество целых чисел А такое, что любое число можно записать как сумму всего двух элементов этого множества? Очевидно, что нет. Чтобы требуемое условие вы¬ полнялось, 0 должен принадлежать множеству — иначе мы не сможем предста¬ вить 0. Аналогично, число 1 также должно принадлежать множеству — иначе мы не сможем представить 1 нужным образом. Следовательно, единицу можно будет представить двумя разными способами — как 1 + 0 и как 0 + 1. Мы доказали, что множества Ау обладающего требуемым свойством, не существует. Путем похожих рассуждений доказывается, что не существует бесконечного множества А, в кото¬ ром число представлений для всех натуральных чисел будет одинаковым (иными словами, такого множества, что вместо числа 1 можно будет подставить любое дру¬ гое число). Все это наводит на мысли рассмотреть более слабые условия — так мы сможем лучше понять природу функций представления для бесконечных множеств. Суще¬ ствует ли бесконечное множество А такое, что его функция представления начиная с определенного момента будет постоянной? В этом случае для небольших значе¬ ний число представлений может быть любым, но начиная с определенного значения и до бесконечности число представлений должно оставаться постоянным. Эта задача нетривиальна, и чтобы решить ее, потребуется как следует поразмыс¬ лить. Первое решение получили Эрдёш и один его коллега Пал Туран в 1941 году. В своих рассуждениях Эрдёш и Туран использовали очень сложные методы, в част¬ ности так называемую теорему Фабри для функций, определенных на диске. Любо¬ пытно, что доказать отсутствие решений этой задачи очень просто. Ключевой момент доказательства заключается в том, что для элемента а мно¬ жества А число представлений 2а будет нечетным, число представлений 2а + 1 — четным. Так как множество бесконечно велико, функция представления будет при¬ нимать четные и нечетные значения бесконечное число раз. Следовательно, не су¬ ществует такого значения, начиная с которого функция представления будет по¬ стоянной. Как это доказать? Разумеется, с помощью комбинаторики! Рассмотрим число представлений натурального числа 2а. Обратите внимание, что а — элемент мно¬ жества, а + а — корректное представление числа 2а. Ключевой момент состоит в следующем: если существует какое-либо еще представление 2а, его слагаемые обязательно должны быть различными. К примеру, если Ь + с = 2а, где Ь иене рав¬ ны между собой, то представление с + Ь будет отличаться от представления b + с, 116
КОМБИНАТОРИКА ЧИСЕЛ и число представлений 2а обязательно будет нечетным: 2а будет иметь единственное представление, в котором оба слагаемых равны, плюс четное число представлений, в которых слагаемые отличаются. И напротив, число вида 2а + 1 нельзя представить в виде суммы двух равных слагаемых, так как это число нечетно. Следовательно, любое представление этого числа будет содержать различные слагаемые, и общее число представлений будет четным. МНОЖЕСТВА СИДОНА, ИЛИ КАК ЭРДЁШ ОТКРЫЛ АДДИТИВНУЮ ТЕОРИЮ ЧИСЕЛ Теория вероятностей применяется в комбинаторике, комбинаторика - в теории графов... Раз¬ ные науки связаны между собой совершенно неожиданным образом, и комбинаторная теория чисел не исключение. Одна из ключевых проблем этой теории берет начало в очень далеком от нее разделе математики - гармоническом анализе. В 1932 году венгерский специалист по анализу Симон Сидон задал юному Эрдёшу вопрос о частотах определенных математических функций. В этом вопросе сплелись воедино ариф¬ метика и комбинаторика, и задача показалась юному студенту особенно интересной, так как была связана с комбинаторикой, и Эрдёш не раз и не два возвращался к ней в своих работах. Множество целых чисел называется множеством Сидона, если суммы всех пар элементов множества (порядок следования не важен) отличаются. К примеру, множество {1, 4, 7, 10} не является множеством Сидона, так как 4 + 7 - 1 + 10. Существует бесконечно много задач, связанных с этими множествами, например задача об оценке числа элементов множества Си¬ дона, все элементы которого меньше данного целого числа. Любопытно, что множества Сидона используются в прикладных областях, в частности при проектировании радаров и систем связи. Как видите, междисциплинарные теории порой находят совершенно неожиданное применение. Видя результат, который мы только что доказали, читатель может задаться во¬ просом — что произойдет в более общем случае, когда число представлений не оди¬ наково, а изменяется в заранее установленных пределах (например, равняется толь¬ ко 1, 2 или 5)? Это один из важнейших открытых вопросов комбинаторной теории 117
КОМБИНАТОРИКА ЧИСЕЛ чисел. Этот вопрос вновь предложили Туран и дядюшка Пал в 1941 году. За дока¬ зательство гипотезы Эрдёша — Турана полагалась премия в 500 долларов. Точная ее формулировка звучит так: «Пусть А — бесконечная последовательность натуральных чисел. Если функ¬ ция представления отлична от 0 для некоторого значения и всех последующих, то функция представления не может быть ограниченной». Смысл этой гипотезы таков. Рассмотрим бесконечное множество А такое, что любое достаточно большое натуральное число можно записать в виде суммы двух ГИПОТЕЗА С ДАВНЕЙ ИСТОРИЕЙ В 1742 году математик Кристиан Гольдбах написал письмо великому ученому Леонарду Эйлеру, жившему в Базеле, чтобы прояснить замеченную закономерность: по всей видимости, любое четное число можно было представить как сумму двух простых. Эйлер закономерность объяснить не смог, и с годами это скромное наблюдение превратилось в ключевую задачу теории чисел. Гипотеза Гольдбаха - не более чем очередная задача о функциях представления. В поисках полного ее доказательства математики не добились значительных успехов: с помощью мощных компьютеров и передовых вычислительных методов удалось показать, что гипотеза верна для очень больших чисел, однако она до сих пор остается недоказанной. С гипотезой Гольдбаха связан ряд очень интересных вопросов, на которые в свое время удалось найти ответы. Среди них - теорема Виноградова и теорема Чена. Согласно теореме Виноградова, все достаточно большие нечетные числа можно представить в виде суммы трех простых чисел. Теорема Чена - более узкое утверждение: согласно ей, любое достаточно большое четное число можно записать как сумму двух простых чисел либо как сумму простого и полупростого числа (то есть числа, равного произведению двух нечетных простых чисел). В теореме Чена нельзя указать, какие именно четные числа можно представить тем или иным способом. К сожалению, аналитические методы, использованные для доказательства этих двух теорем, не позволяют получить удовлетворительное доказательство гипотезы Гольдбаха. Сегодня эта гипо¬ теза остается предметом интенсивных исследований многих ведущих математиков. 118
КОМБИНАТОРИКА ЧИСЕЛ элементов А. В этих условиях функция представления не может всегда принимать значения, меньшие, например, 100, 1000 или 10000: всегда найдется некоторое значение (оно может быть очень велико), для которого число представлений будет больше заранее установленного значения. С этой гипотезой, имеющей, казалось бы, простую формулировку, связана за¬ дача о конфликте интересов. Мы уже видели, что граф с большим хроматическим числом должен иметь малый обхват, и наоборот. С натуральными числами связана похожая, но более сложная задача. Вероятностный метод позволяет найти границы, в которых оба числа (и хроматическое число, и обхват) будут сколь угодно большими. Обложка романа «Дядюшка Петрос и гипотеза Гэльдбаха» греческого писателя Апостолоса Доксиадиса. Гэрой романа, математик на пенсии, предлагает племяннику доказать знаменитую гипотезу. 119
КОМБИНАТОРИКА ЧИСЕЛ В нашем случае «конфликт интересов» таков: если множество А содержит много элементов, с их помощью можно будет представить большинство натуральных чи¬ сел, однако одно и то же число, возможно, будет иметь много разных представлений. И напротив, если мы хотим, чтобы количество различных представлений числа было небольшим (а еще лучше — ограниченным), следует выбрать множество Ау содер¬ жащее не слишком много элементов. Но в этом случае некоторые большие числа, возможно, не удастся представить в виде суммы элементов выбранного множества. Эрдёш и Туран сформулировали эту гипотезу в 1941 году, и математики до сих пор не слишком приблизились к ее доказательству. Сегодня известно лишь, что если последовательность А удовлетворяет условиям гипотезы Эрдёша — Турана, то функция представления будет принимать некое значение, большее 7. Чтобы до¬ браться до бесконечности, потребуется пройти долгий путь! Вес имеет значение Продолжим рассматривать бесконечные последовательности натуральных чисел, но с иной точки зрения — обратимся к теории Рамсея. Напомним, что согласно принципу Дирихле, если голуби рассажены в ящики так, что их число больше числа ящиков, то найдутся два голубя, которые попали в один ящик. В этом разделе мы рассмотрим похожий вопрос, содержащий дополнительное условие: число голубей может быть бесконечно велико. Рассмотрим множество натуральных чисел и рас¬ красим каждый его элемент (то есть каждое число) каким-нибудь цветом. Наша палитра цветов содержит конечное число оттенков. Таким образом, мы раскрасим элементы бесконечного множества конечным числом цветов. Возможно, доля чисел определенного цвета будет близка к доле чисел другого цвета. Возможно, будет наблюдаться совершенно противоположная ситуация. Пер¬ вое, на что следует обратить внимание, — один из цветов (возможно, несколько) обязательно будет преобладать, то есть доля чисел некоторого цвета в общем мно¬ жестве будет сравнительно велика. В противном случае все цвета будут использо¬ ваны считанное число раз, что невозможно — ведь мы хотим раскрасить все целые числа! Чтобы уточнить эту мысль, применим четко структурированные объекты, которые помогут лучше понять рассматриваемую задачу. Этими объектами будут арифметические прогрессии. 120
КОМБИНАТОРИКА ЧИСЕЛ Арифметической прогрессией длиной г с разностью Ь называется последователь¬ ность чисел вида а + bk, где k принимает значения от 0 до г — 1. Арифметические прогрессии занимают в арифметике то же место, что и одноцветные полные гра¬ фы — в теории графов: это упорядоченные структуры, которые неизбежно воз¬ никают при изучении абсолютно неупорядоченных объектов. На множестве нату¬ ральных чисел определено великое множество арифметических прогрессий самой разной длины. Если мы хотим уточнить, почему при раскрашивании бесконечного множества конечным числом цветов всегда найдется преобладающий цвет, нужно найти некоторое свойство, позволяющее преобразовать одно множество в другое. Здесь нам поможет теорема, доказанная голландским алгебраистом Бартелем Леендертом ван дер Варденом (1903, Амстердам — 1996, Цюрих) и ставшая крае¬ угольным камнем теории Рамсея в приложении к арифметической комбинаторике. Теорема ван дер Вардена гласит: «Если мы раскрасим натуральные числа конечным числом цветов, найдется од¬ ноцветное множество, содержащее арифметические прогрессии сколь угодно боль¬ шой длины». Фотография юного ван дер Вардена, автора теоремы, носящей его имя. 121
КОМБИНАТОРИКА ЧИСЕЛ Обратите внимание, что согласно этой теореме существуют элементы определен¬ ного цвета (мы не знаем, какого именно — теорема гарантирует исключительно су¬ ществование такого цвета), которые будут в высшей степени упорядоченными: сре¬ ди них будут содержаться арифметические прогрессии сколь угодно большой длины (5, 50 и так далее). Теорема ван дер Вардена — по сути, частный случай намного более общего утверждения, описывающего натуральные числа и арифметические прогрессии. Ключевое условие этой теоремы заключается в том, что при раскраши¬ вании мы используем конечное множество цветов, и во многих случаях это условие будет слишком строгим. В результате найдется по крайней мере один цвет, которым будет раскрашена значительная доля натуральных чисел. Эта доля называется плот¬ ностью множества. Рассмотрим это понятие подробнее. В больших числовых последовательностях часто можно обнаружить скрытые структуры, обладающие особыми свойствами (вспомните, как мы обнаружили упо¬ рядоченные структуры в совершенно беспорядочных объектах в главе 4). Опре¬ делим понятие, которое позволит нам уточнить смысл слов «доля» и «часть» для бесконечного множества. Для этого вернемся к теории вероятностей и вспомним правило Лапласа. При этом мы столкнемся еще с одной трудностью: число благо¬ приятных и возможных исходов бесконечно велико. Начнем с простейшего случая. Допустим, что мы хотим определить, какую имен¬ но часть множества натуральных чисел занимает некоторое конечное множество, также состоящее из натуральных чисел. Очевидно, что конечное множество будет иметь пренебрежимо малый вес, так как множество натуральных чисел бесконечно велико. Числом благоприятных исходов будем считать число элементов конечного множества, а общее число возможных исходов будет бесконечно велико. Можно сказать, что вес конечного множества будет равен 0, так как его размер относитель¬ но размеров множества натуральных чисел пренебрежимо мал (что такое конечное число объектов в сравнении с бесконечностью?). Усложним задачу и рассмотрим бесконечное число элементов, в частности бес¬ конечную арифметическую прогрессию — например, 0, 5, 10, 15, 20 и так далее до бесконечности. Выберем одно число из бесконечного множества случайным об¬ разом. С какой вероятностью это число будет принадлежать прогрессии? Рассма¬ триваемая прогрессия содержит бесконечно много элементов, следовательно, мы не можем применить классическое правило Лапласа — единственный известный нам метод вычисления вероятностей. 122
КОМБИНАТОРИКА ЧИСЕЛ Но интуиция подсказывает: любое число либо кратно 5, либо при делении на 5 дает остаток 1, 2, 3 или 4 (если число кратно 5, остаток от деления будет равен 0). Следовательно, остатки от деления на 5 в некотором роде позволяют классифициро¬ вать целые числа. Если мы будем выбирать числа случайным образом, то один раз из каждых пяти это число будет кратно 5. Интуиция подсказывает, что этим свой¬ ством обладает пятая часть всех натуральных чисел, следовательно, плотность рас¬ сматриваемого множества будет равна 1/5 (иными словами, пятая часть всех нату¬ ральных чисел кратна 5). Как формализовать эту идею? Правило Лапласа в этом случае неприменимо, так как число благоприятных и возможных исходов бесконечно велико, однако мы мо¬ жем рассмотреть все числа от 1 до Л (где N — очень большое число) и произвести подсчеты. Пусть N — большое целое число. Число возможных исходов равно N/5. Разделив его на N, получим искомую плотность. Это значение не зависит от вы¬ бранного значения N и всегда будет равно 1/5. Таким образом, плотность множества определена однозначно. Аналогично можно доказать, что плотность арифметиче¬ ской прогрессии с разностью т равна 1/ш. Схожим образом следует рассуждать всякий раз, когда необходимо вычислить плотность более сложных бесконечных множеств. В общем случае правило Лапласа в подобных задачах неприменимо, так как число благоприятных и возможных ис¬ ходов бесконечно велико, а мы не слишком хорошо умеем выполнять действия над бесконечными величинами. Поэтому при работе с подобными множествами лучше всего как-то ограничивать их в размере (иными словами, выбирать некое значение N и выполнять расчеты только для целых чисел, меньших N). Искомую плотность мы получим тогда, когда рассмотрим бесконечно большое значение N. Теперь вы располагаете всеми необходимыми знаниями для того, чтобы понять следующую теорему — теорему Семереди, названную в честь своего автора: «Пусть А — последовательность натуральных чисел положительной плотности. Тогда существуют арифметические прогрессии сколь угодно большой длины, обра¬ зованные элементами А». Этот удивительный результат означает: если наше бесконечное множество чисел имеет достаточно большую плотность относительно множества всех чисел (то есть если рассматриваемое множество имеет положительную плотность), то мы всегда сможем выбрать т элементов нашего множества А (где т может быть сколь угодно 123
КОМБИНАТОРИКА ЧИСЕЛ большим) так, что они образуют арифметическую прогрессию. И вновь вы видите, как в хаотических объектах проявляются упорядоченные структуры. Теорема Семереди стала одной из важнейших в математике второй полови¬ ны XX столетия. Она вновь доказывает, что эта наука представляет собой единое целое, а не ряд разрозненных дисциплин. Первый шаг на пути к решению этой задачи сделал британский математик Клаус Рот в 1956 году — ему удалось доказать теорему для арифметических прогрессий длиной 3 (иными словами, если А — последовательность натуральных чисел с по¬ ложительной плотностью, она содержит бесконечно много арифметических прогрес¬ сий из 3 чисел). Несколько лет спустя, применив исключительно комбинаторные методы, вен¬ герский математик Эндре Семереди смог найти доказательство для арифмети¬ ческих прогрессий длиной 4. В общем виде теорему доказал все тот же Семере¬ ди в 1975 году, остроумно применив передовые комбинаторные методы. Затем, в 1977 году, израильский математик Гарри Фюрстенберг нашел новое доказатель¬ ство, применив принципиально иные методы, относящиеся к эргодической теории и связанные с так называемыми динамическими системами. Наконец, в 2001 году британский математик Уильям Тимоти Гауэре нашел третье доказательство с помо¬ щью аналитических методов. Самое удивительное в этой истории то, что во многих случаях доказательства одного и того же утверждения, полученные совершенно разными методами, по сво¬ ей сути ничем не отличаются. Иными словами, одни и те же идеи можно изложить разными способами в зависимости от специализации их автора. В случае с тео¬ ремой Семереди все обстоит с точностью до наоборот: в трех ее доказательствах были использованы совершенно разные идеи, и одна и та же теорема была доказана с принципиально разных позиций. Иными словами, не существует какого-то спосо¬ ба, позволяющего вывести аналитические рассуждения Гауэрса из комбинаторного доказательства Семереди. Как вы узнаете чуть позже, Бен Грин и Теренс Тао применили именно этот под¬ ход в доказательстве своей теоремы, которая теперь носит название теоремы Гри¬ на — Тао об арифметических прогрессиях. В ней речь вновь идет о главных действу¬ ющих лицах всей математики — простых числах. 124
КОМБИНАТОРИКА ЧИСЕЛ Сверху вниз, слева направо — Семереди, Фюрстенберг и Гэуэрс, авторы трех доказательств одной теоремы. ...Несмотря на это, существуют арифметические прогрессии... Простые числа всегда были предметом очень интересных задач — потому что они составляют одну из основ всей математики или потому что обладают поистине за¬ гадочными свойствами. Задачи, связанные с простыми числами, можно встретить 125
КОМБИНАТОРИКА ЧИСЕЛ во многих разделах математики. В этом, последнем разделе нашей книги мы погово¬ рим о связи простых чисел с комбинаторикой. Вернемся к спору между Эрдёшем и Сельбергом. Как мы уже отмечали, поводом для разногласий этих двух титанов послужила теорема Дирихле о простых числах в арифметических прогрессиях. Эту теорему предложил Гаусс, а доказательство на¬ шел Дирихле только в 1837 году. Формулировка теоремы Дирихле о простых числах в арифметических прогрессиях очень проста: «Пусть а и b — целые числа, не имеющие нетривиальных общих делителей. Тог¬ да существует бесконечно много простых чисел вида а + bk». Обратите внимание: для того чтобы теорема выполнялась, необходимо, чтобы а и Ь не имели общих делителей — в противном случае а и Ь будут делиться на не¬ которое целое число ш, следовательно, вынеся общий множитель за скобки, мы получим, что все числа вида <z+ bk также будут кратны т. Существует еще одна, намного более глубокая и сложная гипотеза, связанная с теоремой Дирихле. Она гласит: определенная арифметическая прогрессия может содержать бесконечно много простых чисел. Однако эта гипотеза не указывает, на¬ сколько далеко друг от друга будут находиться эти простые числа. Иными словами, интересно определить, какая структура описывает расположение простых чисел в данной арифметической прогрессии. Читатель предположит, что доказать эту гипотезу поможет теорема ван дер Вардена: она гарантирует существование арифметических прогрессий и применима к числовым последовательностям общего вида, имеющим положительную плотность. Но рассчитать плотность множества простых чисел очень сложно. Какой-либо точ¬ ной формулы для расчета не существует, хотя мы можем использовать довольно точную оценку, следующую из теоремы о распределении простых чисел. Для очень большого п (только для таких п выполняется теорема о распределении простых чи¬ сел) доля простых чисел в множестве натуральных чисел будет иметь порядок п ь(м) _ 1 п In (и) Так как с увеличением п натуральный логарифм возрастает, при п, стремящемся к бесконечности, доля простых чисел будет уменьшаться. В пределе их доля будет 126
КОМБИНАТОРИКА ЧИСЕЛ равна 0, так как для достаточно больших п значение функции, обратной логариф¬ мической, будет пренебрежимо малым. Таким образом, плотность множества целых чисел равна 0. Перед нами стоит серьезная задача: необходимые условия теоремы Семереди не выполняются, следовательно, мы не можем утверждать, что на множестве про¬ стых чисел существуют сколь угодно длинные арифметические прогрессии. Но су¬ ществуют ли арифметические прогрессии произвольной длины на множестве про¬ стых чисел? Отдельные частные случаи позволяют заявить, что это так: в 2008 году была найдена первая арифметическая прогрессия из 25 простых чисел, описываемая формулой 6171 054 912 832 631 + 366 384 • 223 092 870 • к, где k принимает значения от 0 до 24, а все члены прогрессии, вычисленные по ука¬ занной формуле, будут простыми числами. Двумя годами позже, в 2010 году, уда¬ лось найти арифметическую прогрессию из 26 чисел, описываемую следующей фор¬ мулой: 43 142 746 595 714 191 + 23 681 770 • 223 092 870 • к, где k принимает значения от 0 до 25. Эти результаты показывают: если мы хотим найти арифметические прогрессии среди простых чисел, следует начинать с очень больших чисел. Любопытно, что теорема Семереди верна для простых чисел, хотя они и не удов¬ летворяют ее условиям. Не так давно это доказали два великих математика — Бен Грин и Теренс Тао. Эти два исследователя, несомненно, наметили многие пути, кото¬ рыми проследуют математики XXI столетия. Теорема Грина — Тао гласит: «Последовательность простых чисел содержит арифметические прогрессии про¬ извольной длины». По словам авторов теоремы, они взяли за основу тот факт, что три известных доказательства теоремы Семереди совершенно различны (мы уже говорили, что ни одно из этих доказательств нельзя свести к другому). В результате всякий раз, когда Грин и Тао сталкивались с определенными трудностями при использовании од¬ ного метода, они просто выбирали другой метод и продолжали двигаться вперед. Та¬ ким образом, объединив три далекие друг от друга парадигмы, Бен Грин (род. 1977, 127
КОМБИНАТОРИКА ЧИСЕЛ Бристоль) и Теренс Тао (род. 1975, Аделаида) в 2003 году доказали эту великую теорему — несомненно, одну из важнейших теорем современной математики. В заключение нашей книги приведем краткую биографию одного из авторов те¬ оремы, Теренса Тао. Сегодня он преподает в Калифорнийском университете в Лос- Анджелесе (UCLA). Сфера работ Тао включает широкий спектр тем, начиная от дифференциальных уравнений и заканчивая теорией чисел, не говоря уже о ком¬ бинаторике, эргодической теории и темах более прикладного характера, в частности теории сигналов. Такая плодовитость и научный успех, возможно, объясняются тем, что Теренс Тао проявил выдающиеся способности к математике в очень раннем воз¬ расте. Он был зачислен в среднюю школу, когда ему было семь лет, а в девять уже посещал лекции в университете. В 1986 году, в 10 лет, он стал самым юным участником международной мате¬ матической олимпиады, более того, был удостоен бронзовой медали — и это в воз¬ расте, когда большинство детей только изучают элементарные правила арифметики! В двух последующих олимпиадах он завоевал серебряную и золотую медаль. Его достижение особенно ценно тем, что в международных математических олимпиадах участвуют старшеклассники, и средний возраст участников составляет 17—18 лет. После триумфа на олимпиаде Теренс Тао в 16 лет поступил в университет род¬ ного города, в 17 получил степень магистра, а потом уехал в США для работы над докторской диссертацией. В 21 год он защитил докторскую диссертацию в Прин¬ стонском университете под руководством Элиаса Штейна, а в 24 года стал самым юным профессором в истории Калифорнийского университета в Лос-Анджелесе. Несколько лет спустя, в 2006 году, когда Тао уже получил множество премий за свои открытия, на Международном математическом конгрессе в Мадриде он был удостоен Филдсовской премии — высшей награды для молодых математиков. О способностях ученого решать сложные задачи сегодня слагают легенды. Чарльз Луис Фефферман (род. 1949, Силвер-Спринг, штат Мэриленд), еще один математик-вундеркинд и лауреат Филдсовской премии, так отзывался о нем: 128
КОМБИНАТОРИКА ЧИСЕЛ «Репутация Тао такова, что математики борются за право привлечь его вни¬ мание к своим задачам. Он стал спасителем для всех математиков, зашедших в тупик. Если вы никак не можете справиться с какой-нибудь задачей, у вас есть выход — нужно привлечь внимание Теренса Тао». Теренс Тао и его коллеги (в том числе Бен Грин) заложили основы новых мате¬ матических теорий, в которых в равной степени сочетаются комбинаторика, теория чисел и математический анализ. Будущее покажет, каких результатов помогут до¬ стичь все эти теории. Теренс Тао в возрасте семи лет (вверху) и сегодня. 129
КОМБИНАТОРИКА ЧИСЕЛ САМЫЙ СКАНДАЛЬНЫЙ ПРОГУЛ МЕЖДУНАРОДНОГО МАТЕМАТИЧЕСКОГО КОНГРЕССА Когда конферансье объявил: «Гипотеза Пуанка¬ ре доказана!» - в амфитеатре раздались вос¬ торженные возгласы. Радость присутствующих была не напрасной - гипотезу Пуанкаре не уда¬ валось доказать больше 100 лет. Наконец, эта гипотеза, занимающая важнейшее место в ма¬ тематике XX столетия, была доказана, и свидете¬ лями тому стали сотни участников Международ¬ ного математического конгресса, прошедшего в Мадриде в 2006 году. Объемный план доказательства наметил американский математик Ричард Гамильтон. Однако этот план оказался слишком сложным, и сам Гамильтон полное доказательство найти не смог. Только через несколько лет российский математик Григорий Перельман смог преодо¬ леть все препятствия и решить задачу, неподвластную математике в течение 100 лет. За этот подвиг Перельман был удостоен Филдсовской премии - высшей награды для математика. Од¬ нако кресло Перельмана рядом с Теренсом Тао, Андреем Окуньковым и Венделином Вернером осталось пустым. Ученый не явился на церемонию вручения и отказался от денежной премии. По словам самого Перельмана, причиной отказа стал протест против тенденций, сложившихся в математическом сообществе. Одни посчитают его сумасшедшим, другие - революционером, но с уверенностью можно сказать одно: Григорий Перельман внес неизмеримый вклад в ма¬ тематику. Гоигорий Перельман. Заключение В этой книге мы постарались осветить различные разделы современной комбинато¬ рики. Нашим проводником стал в высшей степени незаурядный математик. Наде¬ емся, читатель понял, что комбинаторика — это не отдельная область математики, 130
КОМБИНАТОРИКА ЧИСЕЛ изолированная от остальных, и не собрание разрозненных задач. Напротив, комби¬ наторика — это полноправная дисциплина, тесно связанная с большинством других наук. Любая хорошая книга о комбинаторике должна содержать раздел «Открытые задачи», хотя бы затем, чтобы заинтересованный читатель посвятил несколько сво¬ бодных минут разгадке математических загадок. Вернемся к гипотезе Эрдёша, упомянутой в главе 3. Напомним, что ученый пред¬ ложил следующую гипотезу, сегодня известную как гипотеза Эрдёша — Турана: «Пусть А = {av av ау ...} — бесконечное множество натуральных чисел. Если ряд I1 |>о Я ■ расходится (иными словами, его сумма равна бесконечности), то А содержит сколь угодно большие арифметические прогрессии». За доказательство этой гипотезы Эрдёш предложил самую большую премию — ее размер составил 3000 долларов. Сам Эрдёш считал доказательство гипотезы очень сложным и оказался прав: она не доказана до сих пор. Более того, о гипотезе известно очень немногое, и можно со всей уверенностью сказать, что она, подобно 23 проблемам Гильберта, определит развитие математики XXI века. Ученые еще очень далеки от того, чтобы полностью познать хаос, сокрытый в сложных системах. Сегодня Бог играет в кости не только со Вселенной, но и с графами и числовыми по¬ следовательностями. Только Ему известно, «что день грядущий нам готовит». 131
Приложение Доказательство леммы Шпернера В этом приложении приводится подробное доказательство леммы Шпернера, упо¬ мянутой в главе 2. В нем мы будем использовать понятие двойственной карты, пред¬ ставленное в этой же главе, а также метод двойного подсчета. Напомним, какая карта называется двойственной данной. Чтобы построить карту, нужно определить множество вершин и множество ребер. Множество вершин — это множество треу¬ гольников триангуляции. Графически вершины можно представить в виде маленьких квадратов, каждый из которых будет располагаться внутри треугольников исходной карты. Внешней грани также поставим в соответствие вершину. После того как мы определили все вершины, соединим ребрами только те пары вершин, которым соот¬ ветствуют смежные треугольники на исходной карте (то есть треугольники, имею¬ щие общее ребро). Концы общего ребра этих треугольников должны быть отмечены разными метками. Получим три различных случая: вершину степени 3, степени 2 и степени 1. Каждому из этих случаев соответствует особая разновидность тре¬ угольников, что показано на рисунке. 1 1 Построение двойственной карты для каждого типа треугольников. 1 После того как мы построили новую карту, заметим, что она содержит четыре типа вершин: изолированные, инцидентные двум ребрам, инцидентные трем ребрам и внешнюю вершину, которая занимает особое место и заслуживает отдельного вни¬ мания. 133
ПРИЛОЖЕНИЕ Изолированные вершины образуются из треугольников, все вершины которых имеют одинаковую метку. Аналогично, вершины степени 2 и 3 соответствуют треу¬ гольникам, вершины которых имеют две или три разные метки соответственно. Это наглядно показано на следующем рисунке. 2#• Построение двойственного графа, соответствующего триангуляции, согласно приведенным выше правилам. Теперь обратим внимание на степень внешней вершины (обозначим ее через w). Покажем, что она всегда будет нечетной (на рисунке выше степень этой вершины равна 5). Для этого рассмотрим только те вершины, которые находятся на сторонах большого треугольника, в частности расположенные на ребре, соединяющем верши¬ ны 1 и 3. Напомним, что эти вершины, по построению, могут иметь только две мет¬ ки — 1 или 3. Обратите внимание: если мы начнем движение из вершины исходного треугольника, имеющей метку 1, и направимся к вершине исходного треугольника с меткой 3, мы пройдем через различные вершины, отмеченные метками 1 и 3. Сопо¬ ставим значение +1 переходу от метки 1 к метке 3 (то есть соответствующему ребру) и значение —1 — переходу от метки 3 к метке 1. Если метка не меняется, сопоставим такому ребру значение 0. Для наглядности рассмотрим пример. 134
ПРИЛОЖЕНИЕ ^ +1 -1 +1 "I 1 ф • • • 3 1 3 О +1 • 1 3 Пример построения для перехода из вершины 1 в вершину 3. Так как начальная вершина имеет метку 1, конечная вершина — метку 3, то зна¬ чению +1 будет соответствовать на одно ребро больше, чем значению —1. Число ребер с разными концами (то есть ребер, которым соответствует значение + 1 или —1) будет нечетным, так как оно определяется как сумма двух последовательных чисел. Именно эти ребра определяют степень вершины w. Проведя аналогичные рассуждения для двух других ребер исходного треугольника, получим: степень w равна сумме трех нечетных чисел, следовательно, она будет нечетной. Теперь у нас есть все необходимое для доказательства леммы. Используем фор¬ мулу двойного подсчета. Согласно ей, в любом графе G = (V, А) удвоенное число ребер равно сумме степеней всех его вершин. Как мы уже говорили, важно заметить, что удвоенное число ребер всегда будет четным числом. Следовательно, сумма сте¬ пеней всех вершин графа также будет четной! Рассмотрим сумму степеней вершин и вклад каждой вершины в эту сумму. Вна¬ чале исследуем приведенную выше сумму согласно нашей классификации: w)+ X d{v)+ Z ^{v) + 2 rf(i')- v степени 0 и степени 2 v степени 3 С одной стороны, если вершина имеет степень, равную 0, то d(v) = 0, поэтому в приведенном выше выражении можно не рассматривать сумму для изолированных вершин. Имеем следующее соотношение: d(w)+ X d{v)+ Z rf(t'). и степени 2 и степени 3 С другой стороны, сумма, соответствующая вершинам степени 2, всегда будет четной, так как каждое слагаемое будет кратно 2. Таким образом, сумма 135
ПРИЛОЖЕНИЕ d(u;}+ X v степени 3 должна быть четной. Мы уже показали, что d(w) — нечетное число, поэтому сумма X j(,) v степени 3 также должна быть нечетной, а значит — отличной от нуля. Следовательно, суще¬ ствует треугольник, все вершины которого имеют разные метки, что и требовалось доказать. 136
Библиография ALSINA, С., Mapas del metro у redes neuronales. La teoria de grafos. Biblioteca El mundo es matematico, Barcelona, RBA, 2010. ARNOLD, V., ATIYAH M. ET AL. (editores), Mathematics: Frontiers and Perspectives. International Mathematical Union, 2000. FEYNMAN, R., Surely You re Joking, Mr. Feynman!, Nueva York, W.W. Norton and Company, 1997. GOWERS, T. ET AL. (editores), The Princeton Companion to Mathematics, Nueva Jersey-Oxford, Princeton University Press, 2008. GRAClAN, E., Los numeros primos. Un largo camino al infinito, Biblioteca El mundo es matematico, Barcelona, RBA, 2010. HOFFMAN, P., The Man Who Loved Only Numbers. The story of Paul Erdos and the Search for Mathematical Truth, Nueva York, Hyperion Books, 1998. SCHECHTER, B., My Brain Is Open. The Mathematical Journeys of Paul Erdos, Oxford University Press, 1998. TUTTE, W., Graph Theory as I Have Known. Oxford Lecture Series in Mathematics and its Applications, 1998. 137
Алфавитный указатель Адамар, Жак 111 арифметическая прогрессия 76, 120— 127 Байес, Томас 28 байесовский вывод 28 бином 16—23, 54, 59, 68,102 ван дер Варден, Бартель Леендерт 107, 121 вероятность 10, 23—32, 79, 93,100, 106,122 вершина 35—42, 51—59, 90—92,101— 106,133-136 внутренняя 56—59 Витгенштейн, Людвиг 93—95 выпуклая оболочка 96—97 гамма-функция 16 Гаусс, Карл Фридрих 86, 110—112, 126 гипотеза Гольдбаха 118—119 Эрдёша — Секереша 99 Эрдёша — Турана 107, 118, 120, 131 Гомбо, Антуан 23 грань 37, 53, 55, 58,133 граф 33-60, 90-92,101-106,134 полный 42, 90—92,101—106 случайный 103 Грэм, Рональд 75 двойной подсчет 49—53, 133, 135 декартово произведение 12—14, 50—51 дерево 33—35, 55—60 Дирихле, Иоганн Петер Густав Лежён 86, 126 задача о четырех красках 35, 40 о комитете 17—19 задача со счастливым концом 96—100 карта 35—37, 40—41, 55 двойственная 58—59, 133 Кейнс, Джон Мейнард 93—94 Клейн, Эстер 67, 96—100 корень дерева 55, 57, 58 кортеж 15—17 Лежандр, Адриен Мари 110—112 лемма Шпернера 53—54, 133—136 лист дерева 56 Луллий, Раймунд 11 Люка, Эдуард 45, 47 математическое ожидание 30—32 метод биективный 17 вероятностный 100—106 Милгрэм, Стэнли 78—79 обхват графа 104, 106 объединение 13—14 Паскаль, Блез 10, 20, 24—26 перестановка 15—17, 21, 44 планарность 35, 42—43 плотность 123—127 Поса, Лайош 88 постулат Бертрана 67—68 правило Лапласа 10, 25—28, 101, 122-123 правило сложения 1—14, 18, 21, 22 правило умножения 13—15, 22, 26, 79 139
АЛФАВИТНЫЙ УКАЗАТЕЛЬ премия Вольфа 74 Коула 115 принцип Дирихле 85—89, 91, 92, 107 Пуч-и-Адам, Пер 85, 87 размещения без повторений 15—17 с повторениями 15, 18, 45 Рамсей, Фрэнк Пламптон 92—94, 99 ребро 35-37, 51-59, 90-92,101— 106,133-135 рекуррентное уравнение 45, 59 рекуррентность 46—47 Риман, Бернхард 111—112 Саган, Карл 78 Секереш, Дьёрдь 98—100 Сельберг, Атле 112—114, 126 семейство Шпернера 54 сочетание 9, 16, 17 статистические оценки 28 степень вершины 52, 56, 134, 135 Стэнли, Ричард 60 сумма бесконечного ряда 76—77 гармонического ряда 76—77 Тао, Теренс 107, 124, 126-129, 130 теорема ван дер Вардена 107, 121—122, 126 Виноградова 118 Грина — Тао 8, 107, 124, 127 Куратовского 42 о биноме 19, 22 Рамсея 92, 94-95,101,104 Робертсона — Сеймура 44 Семереди 123—124, 127 Чена 118 Шпернера 53—54, 133—136 Эрдёша — Секереша 99 треугольник Паскаля 19—22 триангуляция 57—59, 133—134 факториал 15—16, 45 Фейнман, Ричард 71 Ферма, Пьер 10, 23—24 Фефферман, Чарльз Луис 128 Филдсовская премия 107, 114, 128, 130 Ханойские башни 45 Харди, Годфри Харолд 70, 111 Холл, Монти 26—28 Хомский, Ноам 78 Хуэй, Ян 20 числа Фибоначчи 47—48 число золотое 48 Рамсея 105 хроматическое 104—106, 119 Эрдёша 78 Шевалье де Мере 10, 23, 25 Шпернер, Эммануэль 54 эксперимент «мир тесен» 78 Эрдёш, Пал 61—81, 98—100, 106, 112-120,131 140
ДЛЯ ЗАМЕТОК
Научно-популярное издание Выходит в свет отдельными томами с 2014 года Мир математики Том 34 Хуанхо Руэ Искусство подсчета. Комбинаторика и перечисление РОССИЯ Издатель, учредитель, редакция: ООО «Де Агостини», Россия Юридический адрес: Россия, 105066, г. Москва, ул. Александра Лукьянова, д. 3, стр. 1 Письма читателей по данному адресу не прини¬ маются. Генеральный директор: Николаос Скилакис Главный редактор: Анастасия Жаркова Выпускающий редактор: Людмила Виноградова Финансовый директор: Наталия Василенко Коммерческий директор: Александр Якутов Менеджер по маркетингу: Михаил Ткачук Менеджер по продукту: Яна Чухиль Для заказа пропущенных книг и по всем вопро¬ сам, касающимся информации о коллекции, за¬ ходите на сайт www.deagostini.ru, по остальным вопросам обращайтесь по телефону бесплатной горячей линии в России: в 8-800-200-02-01 Телефон горячей линии для читателей Москвы: © 8-495-660-02-02 Адрес для писем читателей: Россия, 600001, г. Владимир, а/я 30, «Де Агостини», «Мир математики» Пожалуйста, указывайте в письмах свои кон¬ тактные данные для обратной связи (телефон или e-mail). Распространение: ООО «Бурда Дистрибьюшен Сервисиз» УКРАИНА Издатель и учредитель: ООО «Де Агостини Паблишинг» Украина Юридический адрес: 01032, Украина, г. Киев, ул. Саксаганского, 119 Генеральный директор: Екатерина Клименко Для заказа пропущенных книг и по всем вопро¬ сам, касающимся информации о коллекции, за¬ ходите на сайт www.deagostini.ua, по остальным вопросам обращайтесь по телефону бесплатной горячей линии в Украине: © 0-800-500-8-40 Адрес для писем читателей: Украина, 01033, г. Киев, a/я «Де Агостини», «Мир математики» УкраТна, 01033, м. Киш, а/с «Де Агоспш» БЕЛАРУСЬ Импортер н дистрибьютор в РБ: ООО «Росчерк», 220037, г. Минск, ул. Авангардная, 48а, литер 8/к, тел./факс: (+375 17) 331-94-41 Телефон «горячей линии» в РБ: в + 375 17 279-87-87 (пн-пт, 9.00-21.00) Адрес для писем читателей: Республика Беларусь, 220040, г. Минск, а/я 224, ООО «Росчерк», «Де Агостини», «Мир математики» КАЗАХСТАН Распространение: ТОО «КГП «Бурда-Алатау Пресс» Издатель оставляет за собой право увеличить реко¬ мендуемую розничную цену книг. Издатель остав¬ ляет за собой право изменять последовательность заявленных тем томов издания и их содержание. Отпечатано в соответствии с предоставленными материалами в типографии: Grafica Veneta S.p.A Via Malcanton 2 35010 Trebaseleghe (PD) Italy Подписано в печать: 23.07.2014 Дата поступления в продажу на территории России: 09.09.2014 Формат 70 х 100 / 16. Гарнитура «Academy». Печать офсетная. Бумага офсетная. Печ. л. 4,5. Уел. печ. л. 5,832. Тираж: 28 900 экз. © Juanjo Rue, 2011 (текст) © RBA Collecionables S.A., 2011 © ООО «Де Агостини», 2014 ISBN 978-5-9774-0682-6 ISBN 978-5-9774-0729-8 (т. 34) Данный знак информационной про¬ дукции размещен в соответствии с требования¬ ми Федерального закона от 29 декабря 2010 г. № 436-ФЗ «О защите детей от информации, при¬ чиняющей вред их здоровью и развитию». Издание для взрослых, не подлежит обязатель¬ ному подтверждению соответствия единым требо¬ ваниям, установленным Техническим регламентом Таможенного союза «О безопасности продукции, предназначенной для детей и подростков» ТР ТС 007/2011 от 23 сентября 2011 г. № 797.
Комбинаторика и перечисление Книга, которую вы держите в руках, посвящена парадоксальной науке - комбинаторике. С одной стороны, она явно свидетельствует: для того чтобы прийти к неожиданным заключениям, достаточно лишь умения считать и рисовать. С другой стороны, комбинаторика не ограничивается простым счетом: она затрагивает сложнейшие области математики. На первый взгляд комбинаторные задачи кажутся элементарны¬ ми - их поймут даже дети, - однако на деле часто оказывается, что их невозможно решить. Но как бы то ни было, комбинаторика помогает нам лучше понять реальность. Это, безусловно, подтвердит гениальный математик Пал Эрдёш, который разделил историю комбинаторики на «до» и «после». Именно он станет нашим проводником в этот удивительный мир. ISBN 978-597740682-6 9 785977 406826 00034