Ссылку на дополнительную информацию см. в главе «Загадки разгаданные».
Сделка с дьяволом
Один математик, потративший десять бесплодных лет на попытки доказать гипотезу Римана, решил продать душу дьяволу в обмен на вожделенное доказательство. Дьявол обещал представить ему доказательство не позже чем через неделю, но неделя прошла, и ничего не произошло.
Через год дьявол вновь явился математику с мрачным видом.
– Извини, я тоже не смог это доказать, – сказал он, возвращая математику его душу. Он немного помолчал и вдруг просиял: – Но мне кажется, что я нашел по-настоящему интересную лемму!
Рискуя испортить шутку, я поясню, что в математике лемма – это не слишком важное утверждение, основной интерес которого заключается в том, что оно может стать шагом на пути к доказательству другого, более важного утверждения, достойного звания теоремы. Между теоремой и леммой нет никакой логической разницы, но психологически слово «лемма» означает, что кому-то удалось пройти только часть пути к желанной цели…
Ну, я пошел…
Непериодическая мостовая
Замостить плоскость без промежутков и перекрытий можно множеством различных фигур. Единственными правильными многоугольниками, с помощью которых можно это проделать, являются равносторонний треугольник, квадрат и шестиугольник.
Кроме них плоскость можно замостить громадным количеством менее правильных фигур, таких как семисторонний многоугольник на следующем рисунке. Он получен из правильного семиугольника путем зеркального отображения трех его сторон относительно линии, соединяющей их концы.
Мощение правильными многоугольниками периодично, то есть его элементы повторяются бесконечно в двух различных направлениях, как узор на обоях. Спиральное мощение не периодично. Однако описанным здесь семиугольником можно замостить плоскость и периодически.
Как именно? Ответ см. в главе «Загадки разгаданные».
Существуют ли фигуры, которыми можно замостить плоскость, но нельзя сделать это периодически? Вопрос этот глубоко связан с математической логикой. В 1931 г. Курт Гёдель доказал, что в арифметике существуют неразрешимые задачи, то есть утверждения, для которых никакой алгоритм не в состоянии определить, истинны они или ложны. (Алгоритм – это систематический процесс, который гарантированно прекращается при получении верного ответа.) Из этой теоремы следует другая, более драматичная: в арифметике существуют утверждения, которые невозможно ни доказать, ни опровергнуть.
Приведенный Гёделем пример такого утверждения был несколько надуманным, и специалисты по математической логике долго гадали, существуют ли более естественные нерешаемые проблемы. В 1961 г. Хао Ван работал над проблемой домино: если имеется конечное число фигур для мощения, то существует ли алгоритм, который был бы способен определить, можно ли этими фигурами замостить плоскость? Ван показал, что если существует подходящий набор, которыми можно замостить плоскость, но нельзя замостить ее периодически, то такого алгоритма не существует. Его идея состояла в том, чтобы перевести правила логики в формы плиток и использовать результаты вроде гёделевых. И она сработала: в 1966 г. Роберт Бергер нашел набор из 20 426 таких плиток, доказав тем самым, что проблема домино действительно неразрешима.
20 000 различных фигур – это много. Бергеру удалось снизить их число до 104; затем Ганс Лейхли снизил его до 40. Рафаэль Робинсон довел число форм до шести. Роджер Пенроуз, открыв в 1973 г. так называемые плитки Пенроуза (см. «Кабинет…» с. 149), еще уменьшил их число, всего до двух. Получилась интригующая математическая загадка: существует ли единственная фигура, с помощью которой можно замостить плоскость, но нельзя замостить ее периодически? (При этом можно использовать также зеркальное отражение той же фигуры.) Ответ был найден в 2010 г. Джошуа Соколаром и Джоан Тейлор[31], и ответ этот – «да».
Предложенная ими фигура показана на рисунке. Это «разрисованный шестиугольник» с дополнительными «правилами стыковки», и он отличается от собственного зеркального отражения. Рисунки на плитке должны стыковаться вполне определенным образом – так, как показано на рисунке.
На следующем рисунке показана центральная область замощенной такими фигурами плоскости. Можно заметить, что узор на ней не выглядит периодическим. В статье объясняется, почему такое мощение можно распространить на всю площадь и почему результат не может быть периодическим. Подробности можно узнать непосредственно из статьи.
Теорема о двух красках
Из мемуаров доктора Ватсапа
– Ну, Сомс, эта забавная небольшая головоломка сможет поднять вам настроение, – я перебросил Daily Reporter другу и компаньону, почти знаменитому детективу, страдавшему в настоящее время от приступа депрессии потому только, что его конкурент из дома напротив явно достиг большей известности и имел все шансы это преимущество сохранить.
Он, издевательски рассмеявшись, отбросил газету в сторону.
– Ватсап, у меня не хватит энергии на чтение.
– Тогда я сам вам прочту, – ответил я. – Кажется, знаменитый математик Артур Кейли опубликовал статью в «Записках Королевского географического общества», в которой задал вопрос…
– Вопрос о том, можно ли раскрасить произвольную карту не более чем четырьмя красками так, чтобы соседние области оказались окрашенными в разные цвета, – прервал меня Сомс. – Это давняя проблема, Ватсап, и я боюсь, что ответ на этот вопрос не будет получен при нашей жизни. – Я ничего не сказал, надеясь вытащить его на дальнейший разговор, поскольку это была самая длинная фраза, которую он произнес почти за неделю. Мой план сработал, и после минуты неловкого молчания он продолжил: – Молодой человек по имени Фрэнсис Гутри сформулировал эту задачу за два года до моего рождения. Будучи не в состоянии решить ее самостоятельно, он обратился к своему брату Фредерику, ученику профессора Огастеса де Моргана.
– Ах да, Гусси, – вставил я, поскольку был знаком с семьей этого достойного восхищения чудака, автора книги «Бюджет парадоксов» и бича всех свихнувшихся на математике.
– Де Морган, – продолжал Сомс, – ничего не добился, поэтому попросил заняться ею великого ирландского математика сэра Уильяма Роуэна Гамильтона, который, однако, ответил ему отказом. На том все и застопорилось до тех пор, пока Кейли вновь не взялся за эту задачу. Хотя я не представляю, почему он решил опубликоваться именно в этом журнале.
– Возможно, потому, – предположил я, – что географы интересуются картами? – но Сомс только презрительно хмыкнул.
– Не в таком аспекте, – раздраженно отмахнулся он. – Географ раскрасит области на карте в соответствии с политической обстановкой, не обращая внимания на соседство. Смотрите, Кения, Уганда и Танганьика расположены рядом, но на всех картах Британской империи все они окрашены в одинаковый розовый цвет.
Я признал справедливость этого утверждения. Нашей дорогой королеве не понравилось бы, если бы их раскрасили иначе.
– Но, Сомс, – я продолжал настаивать, – вопрос от этого не становится менее интересным. Даже более, поскольку никто, похоже, не в состоянии на него ответить.
Сомс что-то проворчал.
– Давайте все же попробуем, – сказал я и быстро нарисовал условную карту.
– Забавно, – заметил Сомс. – А почему вы сделали все области круглыми?
– Потому что любая область без дырок топологически эквивалентна кругу.
Сомс поджал губы.
– Тем не менее это плохой выбор, Ватсап.
– Почему? Мне кажется…
– Ватсап, вам много что кажется, но мало что на самом деле имеет место быть. Хотя любая отдельная область топологически равноценна кругу, две или большее число областей могут перекрываться способом, невозможным для двух или нескольких кругов. Об этом свидетельствует тот факт, что для вашей карты достаточно всего двух красок, – и он заштриховал примерно половину областей.
– Ну да, но я уверен, что более сложная карта того же рода…
Сомс покачал головой.
– Нет-нет, Ватсап. Любая карта, состоящая исключительно из круглых областей, даже если эти области разных размеров и перекрываются разными, сколь угодно сложными способами, может быть раскрашена в две краски. Считая, как обычно и делается в подобных вопросах, что «соседние» области должны иметь общие участки границы, а не отдельные изолированные общие точки.
– Ну да, но я уверен, что более сложная карта того же рода…
Сомс покачал головой.
– Нет-нет, Ватсап. Любая карта, состоящая исключительно из круглых областей, даже если эти области разных размеров и перекрываются разными, сколь угодно сложными способами, может быть раскрашена в две краски. Считая, как обычно и делается в подобных вопросах, что «соседние» области должны иметь общие участки границы, а не отдельные изолированные общие точки.
У меня отвалилась челюсть.
– Теорема о двух красках! Поразительно! – Сомс соизволил пожать плечами. – Но как такую теорему можно доказать?
Сомс откинулся в кресле.
– Вы знаете мои методы.
Ответ см. в главе «Загадки разгаданные».
Теорема о четырех красках в пространстве
Сомс говорил о знаменитой теореме о четырех красках, которая гласит, что для любой заданной карты на плоскости ее области можно раскрасить не более чем четырьмя разными красками так, чтобы области, имеющие общую границу, были окрашены в разные цвета. (Здесь «иметь общую границу» означает, что общая граница должна быть ненулевой длины; то есть если области сходятся в одной общей точке, это не считается.) Такое предположение высказал в 1852 г. Фрэнсис Гутри и доказали в 1976 г. Кеннет Аппель и Вольфганг Хакен при активном использовании компьютера[32]. За прошедшее с того момента время их доказательство удалось серьезно упростить, но компьютер по-прежнему является существенной его частью; он необходим, чтобы проводить большое количество рутинных, сложных вычислений.
Могут ли существовать аналогичные теоремы для «карт» в пространстве, а не на плоскости? Области в пространстве будут представлять собой что-то вроде заполненных пузырей. Немного подумав, несложно догадаться, что для раскрашивания такой карты может потребоваться сколько угодно красок. Представьте, к примеру, что вы хотите нарисовать карту, для которой нужно шесть красок. Для начала возьмите шесть отдельных шаров. Пусть шар 1 выпустит пять тонких щупалец и коснется ими шаров 2, 3, 4, 5 и 6. Затем пусть шар 2 выпустит пять щупалец и коснется шаров 3, 4, 5 и 6. Затем перейдите к шару 3 и т. д. Получится, что каждая обросшая щупальцами область касается всех остальных областей и, следовательно, все шесть должны быть окрашены в разные цвета. Если проделать такую процедуру со 100 шарами, то потребуется 100 красок; если шаров будет миллион, красок тоже потребуется миллион. Короче говоря, числу необходимых красок нет предела.
В 2013 г. Баскар Багчи и Басудеб Дата[33] поняли, что это не конец истории. Представьте себе «карты», сформированные из конечного числа кругов на плоскости, которые либо вообще не перекрывают друг друга, либо пересекаются в одной общей точке. Предположим, вы хотите раскрасить эти круги так, чтобы даже соприкасающиеся круги были окрашены в разные цвета. Сколько красок вам потребуется? Оказывается, ответ здесь такой же: не больше четырех.
На самом деле эта проблема по существу эквивалентна теореме о четырех красках. Эту теорему можно переформулировать в задачу раскрашивания узлов сети на плоскости с непересекающимися ребрами, так что если два узла этой сети соединены ребром, то эти узлы должны быть окрашены в разные цвета. Для этого достаточно просто создать по узлу для каждой области карты и соединить ребрами попарно те из них, области которых имеют общую границу. Можно доказать, что любая сеть на плоскости может быть собрана из подходящего набора кругов путем соединения центров тех кругов, которые касаются друг друга. К примеру, вот набор кругов, для окрашивания которых необходимы четыре цвета, связанная с ними сеть и карта с топологически эквивалентным искажением этой сети, для раскрашивания которой также требуется четыре краски.
Формулировку с кругами мы можем естественным образом распространить на три измерения, если используем шары вместо кругов. Опять же, эти шары либо вообще не перекрываются, либо касаются друг друга в общей точке. Предположим, вы хотите раскрасить шары так, чтобы те, которые касаются друг друга, были окрашены в разные цвета. Сколько красок вам понадобится? Багчи и Дата объяснили, почему это число не может быть меньше 5 и больше 13. Его точное значение до сих пор остается математической загадкой. Но вы, возможно, сумеете доказать, что нужно по крайней мере пять красок. Из их результата следует, что некоторые трехмерные карты не эквивалентны картам, построенным на базе шаров.
Ответ см. в главе «Загадки разгаданные».
Комическое исчисление
Чтобы понять эту историю, вы должны быть немного знакомы с интегральным исчислением. Если ∫ – знак интеграла, то экспоненциальная функция ex – сама себе интеграл:
Эта формула кажется какой-то чепухой; даже первая строка должна была бы выглядеть как ex = ∫ exdx, а 1 + y + y² + y³ + y4 +… = (1 – y)–1.
На следующем шаге в формуле для суммы бесконечной геометрической прогрессии переменная y заменяется на знак интеграла. Эта формула справедлива, если y – число, меньшее 1. Но ∫ – это даже не число, просто символ. Какой абсурд!
Несмотря на это, конечный результат – корректный степенной ряд для ex.
Это не совпадение. При правильных определениях (к примеру, ∫ – это оператор, превращающий функцию в ее интеграл, а формула для «суммы геометрической прогрессии» работает для операторов при подходящих технических условиях) все может выглядеть совершенно логичным. Но смотрится все равно странно.
Задача Эрдёша о расходимости
Пал Эрдёш был весьма эксцентричным, блестящим венгерским математиком. Он никогда не имел дома, он никогда не занимал никакого ученого поста, предпочитая путешествовать по миру с небольшим чемоданом и ночевать в домах понимающих коллег. Он опубликовал 1525 математических статей и сотрудничал с 511 математиками – число, к которому никто другой в мире не смог даже приблизиться. Он предпочитал изобретательность глубоким систематическим занятиям теорией и с особенным удовольствием разгадывал загадки, которые выглядели очень просто, но на самом деле оказывались совсем не простыми. Его основные достижения относятся к области комбинаторики, но он мог бы приложить свою руку и ко многим другим областям математики. Он нашел новое доказательство постулата Бертрана (между n и 2n всегда найдется хотя бы одно простое число), гораздо более простое, чем оригинальное аналитическое доказательство Пафнутия Чебышёва. Вершиной карьеры Эрдёша стало доказательство теоремы о числе простых (число простых чисел, меньших x, приблизительно равно x/lnx), которая не поддавалась комплексному анализу, считавшемуся до того момента единственным способом доказательства.
Эрдёш любил предлагать денежные призы за решение задач, которые придумал, но не смог сам решить. Он мог предложить $25 за решение чего-то, что, как он подозревал, решается относительно просто, и несколько тысяч долларов за что-то, что он считал по-настоящему сложным. Типичный пример его математики – задача Эрдёша о расходимости, оцененная им в $500. Она была поставлена в 1932 г. и решена в начале 2014 г. Замечательный пример того, как сегодняшняя математика подходит к разрешению давних загадок.
Задача начинается с бесконечной последовательности чисел, равных или +1, или –1. Это может быть регулярная последовательность, к примеру
+1–1 +1–1 +1–1 +1–1 +1–1…,
или нерегулярная («случайная)
+1–1 –1–1 +1–1 +1 +1–1 +1…,
которую я получил путем бросания монетки. Она не обязана содержать равную долю плюсов и минусов. Подойдет любая последовательность.
Один из способов убедиться в том, что первая из этих последовательностей регулярна, – это взглянуть на каждый второй ее член:
– 1–1 – 1–1 – 1…
Сумма первых n членов такой последовательности выглядит так:
– 1–2 – 3–4 – 5…
и убывает до бесконечности. Если посмотреть те же параметры для второй последовательности, получим:
+1–1 – 1 + 1–1…
с суммами
+1 0–1 0 +1…,
которые скачут вверх и вниз.
Предположим, что мы возьмем конкретную, но произвольную последовательность из ±1 и выберем произвольное положительное число С, которое мы хотим получить. Это число может быть сколь угодно большим, например миллиардом. Эрдёш задал вопрос, всегда ли существует такое число d, что суммы членов последовательности, разделенных d шагами, то есть стоящих на позициях d, 2d, 3d и т. д., на каком-то этапе станут либо больше C, либо меньше – C. После того как эта цель достигнута, та же последовательность может давать дальнейшие суммы, лежащие между C и – C: достаточно хотя бы раз дойти до цели. Однако подходящий шаг d должен существовать для любого целевого C. Разумеется, d зависит от C. То есть, если последовательность имеет вид x1, x2, x3,…, вопрос состоит в том, можем ли мы найти d и k такие, что |xd + x2d + x3d + … + xkd| >C.