Математические головоломки профессора Стюарта Стюарт Иэн
и приведенный выше список правил для определения последней цифры квадрата по последней цифре числа – это всего лишь другой способ сказать то же самое.
За исключением начального 0, список квадратов (по модулю 10) симметричен: числа 1, 4, 9, 6 после 5 повторяются в обратном порядке: 6, 9, 4, 1. Симметрия возникает благодаря тому, что квадраты n и 10 – n по модулю 10 равны. В самом деле, 10 – n – то же, что – n (mod 10), а n = (n). Поэтому данные четыре числа в списке фигурируют дважды; 0 и 5 встречаются там только по одному разу, а 2, 3, 7, 8 не встречаются вовсе. Это не слишком демократично, но это так.
Что происходит, если мы берем другой модуль? Величины квадратов по этому модулю называются квадратичными вычетами. (Здесь под «вычетом» подразумевается остаток от деления на модуль.) Остальные цифры при этом становятся квадратичными невычетами.
Предположим, к примеру, что модуль равен 11. Тогда возможные полные квадраты (чисел, меньших 11) равны
0 1 4 9 16 25 36 49 64 81 100.
По модулю 11 это дает
0 1 4 9 5 3 3 5 9 4 1.
Таким образом, квадратичные вычеты (по модулю 11) – это
0 1 3 4 5 9.
А невычеты – это
2 6 7 8.
Приведем небольшую таблицу.
На первый взгляд, никаких особенных закономерностей, кроме уже упомянутых, не заметно. На самом деле этим отчасти и интересна данная область математики: хотя шаблоны существуют, отыскать их непросто. Многие величайшие математики, в том числе Эйлер и Карл Фридрих Гаусс, уделяли внимание этой области.
Возводя число в квадрат, мы умножаем его на самого себя, а там, где речь заходит об умножении, в теории чисел главную роль всегда играют простые числа. Поэтому стоит начать с простых модулей – 2, 3, 5, 7, 11 – в приведенном списке. Модуль 2 уникален: единственные возможные вычеты по модулю 2 – это 0 и 1, и оба они являются полными квадратами. Для всех остальных простых чисел примерно половина вычетов являются квадратами, а остальные – не являются. Точнее, если p – простое число, то существует (p + 1)/2 различных квадратичных вычетов и (p 1)/2 невычетов. Квадратичные вычеты обычно являются квадратами двух различных чисел, n и (– n) для подходящего n. Однако 0 встречается в списке лишь однажды, потому что –0 = 0.
Составные модули усложняют ситуацию. Теперь одни и те же вычеты иногда могут быть квадратами больше чем двух чисел. К примеру, 1 по модулю 8 встречается четыре раза, как квадрат 1, 3, 5 и 7. Лучший способ разобраться во всем этом – воспользоваться современной абстрактной алгеброй, но имеет смысл взглянуть и на модуль 15. У него два простых множителя: 3 5. А вот список квадратов:
Таким образом, квадратичные вычеты по модулю 15 равны
0 = 0
1 = 1, 4, 11, 14
4 = 2, 7, 8, 13
6 = 6, 9
9 = 3, 12
10 = 5, 10
Некоторые вычеты возникают один раз, некоторые дважды, некоторые четырежды. Те, которые встречаются в списке меньше четырех раз, являются квадратами чисел, кратных либо 3, либо 5, то есть простым множителям 15. Все остальные числа возникают группами по четыре, где квадраты всех четырех равны.
Это общая закономерность для любого модуля вида pq, где p и q – различные нечетные простые числа. Числа от 0 до pq – 1, не кратные ни p, ни q, разделяются на четверки с равными квадратами. (Это не работает, если одно из простых чисел равно 2: к примеру, 10 = 2 5, но мы уже видели, что в этом случае квадраты либо одиноки, либо стоят парами.)
В алгебре мы привыкаем к мысли, что у каждого положительного числа имеется два квадратных корня: один положительный, другой отрицательный. Но в арифметике по модулю pq большая часть чисел (те, что не делятся ни на p, ни на q) имеет по четыре различных квадратных корня.
Этот любопытный факт имеет замечательное приложение, к которому мы и перейдем.
Бросание монетки по телефону
Предположим, что Алиса и Боб хотят сыграть в бросание монетки с вероятностью того или иного результата 50:50. Как мы уже знаем, Алиса находится в Алис-Спрингс, а Боб – в Боббингтоне. Могут ли они бросать монетку по телефону? Главная загвоздка – та же, что при игре в покер. Если бросает монетку (или проделывает любую другую операцию с равновероятным исходом) Алиса и она же сообщает результат Бобу, то тот никак не может быть уверен, что она говорит правду. Конечно, в наше время они могли бы делать это во время общения по скайпу и наблюдать за бросанием монетки, но даже в этом случае результат можно подделать, сняв заранее несколько бросков и показав собеседнику запись вместо онлайн-трансляции.
Бросание монетки – то же, что игра в покер колодой из двух карт, так что игроки вполне могут воспользоваться методикой, описанной выше. Однако существует и другой элегантный способ достичь того же результата с использованием квадратичных вычетов. Вот как это можно сделать.
Алиса выбирает два больших простых числа p и q. Она держит их в секрете, но отправляет Бобу их произведение n = pq. Вы скажете, что Боб мог бы найти p и q путем разложения n на простые множители, но на сегодняшний день, насколько известно, не существует практичного способа сделать это, если числа p и q достаточно велики – скажем, по 100 знаков в каждом. Даже самым быстрым компьютерам, использующим самые быстрые алгоритмы, понадобилос бы на это время, превышающее время жизни Вселенной. Так что Боб останется в неведении.
Однако существуют очень быстрые способы проверить 100-значное число и узнать, является ли оно простым. Так что Алиса сможет подобрать себе p и q методом проб и ошибок.
Боб выбирает произвольное целое x (mod n), которое держит в секрете.
Если он необычайно педантичен, то может быстро проверить, не является ли x произведением p и q: он не будет делить его на эти числа, поскольку их не знает, но найдет наибольший общий делитель (НОД) чисел x и n через алгоритм Евклида. Если результат окажется не равным 1, то получится, что он знает либо p, либо q, и процесс нужно будет начинать заново с новым x. Но на практике можно особо не беспокоиться, поскольку при p и q, содержащих по 100 знаков каждое, вероятность того, что одно из этих чисел окажется делителем произвольно выбранного x, составит 2 10–100.
Далее Боб вычисляет x (mod n), что тоже можно сделать быстро, и отправляет результат Алисе. Они договорились, что если Алиса сможет правильно назвать x или – x, то она выиграет (это будет «орел»). В противном случае – проиграет («решка»).
Из предыдущей главы Алиса знает, что целые числа по модулю pq, не кратные ни p, ни q, имеют ровно по четыре квадратных корня. Поскольку x и – x при возведении в квадрат дают одно и то же, квадратные корни имеют вид a, – a, b, – b для подходящих a и b. Алиса знает p, q и x, из чего следует, что она может быстро вычислить четыре нужных корня. Два из них должны быть равны x и – x; два других – не равны. Так что вероятность угадать ± x верно у Алисы на 50 % – что эквивалентно честному бросанию монетки. Она выбирает одно из четырех чисел, скажем b, и отправляет его Бобу.
Боб сообщает Алисе, действительно b = ± x или нет; то есть права она или нет.
Ах, но как сделать так, чтобы Боб тоже не мог смошенничать? И откуда Бобу знать, что Алиса сделала все так, как должна была сделать?
В любом случае (верно b = ± x или нет) Боб может легко убедиться, что Алиса играла честно, если вычислит b (mod n). Результат должен совпасть с x.
Если Алиса проигрывает, то она может убедиться в честности Боба, попросив его прислать ей простые множители n, то есть p и q. В обычных условиях это невозможно, но если Алиса проиграла, то Боб знает все четыре квадратных корня из x, а в теории чисел имеется хитрый прием, позволяющий быстро вычислить p и q по этим данным. Наибольшим общим делителем a + b и n является одно из наших двух простых чисел, а НОД опять же можно найти при помощи алгоритма Евклида. После этого второе число можно найти путем деления.
Как устранить нежелательное эхо
Квадратичные вычеты могут показаться типичным примером мудреных умствований, которые так любят математики-теоретики: интеллектуальной игрой, не имеющей никакого практического применения. Но было бы ошибкой думать, что математическая идея бесполезна, только потому, что она не проистекает очевидным образом из практических задач повседневной жизни. Ошибка также считать, что повседневная жизнь настолько прямолинейна, как кажется на поверхностный взгляд. Для изготовления даже такой простой вещи, как банка джема из супермаркета, нужно сварить стекло, вырастить сахарный тростник или сахарную свеклу, очистить сахар… и очень скоро вы обнаружите, что с головой погрузились в статистический анализ испытаний сортов растений на сопротивляемость болезням и в конструирование судов, используемых для перевозки различных компонентов готового продукта по всему земному шару. В мире, где живет 7 млрд человек, массовое производство продуктов питания не сводится к тому, чтобы просто собрать ягоды и сварить их.
Действительно, математики, которые первыми выдвинули эти идеи, не думали ни о каких конкретных практических приложениях для них; просто квадратичные вычеты показались им интересными. Но они также были убеждены, что их понимание станет новым мощным дополнением к математическому инструментарию. Практики не в состоянии пользоваться инструментом, пока его не существует. И хотя на первый взгляд может показаться, что разумнее подождать появления конкретной задачи, прежде чем придумывать инструменты, подходящие для ее решения, при таком подходе мы до сих пор жили бы в пещерах. «Зачем ты теряешь время, стуча камнем по камню, а, Уг? Тебе следовало бы стучать палкой по голове мамонта, как делают остальные мальчики».
У квадратичных вычетов множество самых разных применений. Один из моих любимых примеров – проектирование концертных залов. Музыка, отражаясь от плоского потолка, дает явственное эхо, которое искажает звук и вообще мешает слушать. С другой стороны, звукопоглощающий потолок делает звучание мертвым и смазанным. Для хорошей акустики звук должен отражаться, но в виде рассеянного отзвука, а не резкого эха. Поэтому архитекторы встраивают в потолок специальные рассеиватели. Вопрос в том, какой они должны быть формы.
В 1975 г. Манфред Шрёдер изобрел рассеиватель, состоящий из серии параллельных борозд, глубина которых выводится из последовательности квадратичных вычетов для некоего простого модуля. Возьмем, к примеру, простое число 11. Мы только что видели, что квадраты чисел от 0 до 10 по модулю 11 равны:
0 1 4 9 5 3 3 5 9 4 1,
и далее, для более крупных чисел, эта последовательность повторяется периодически. Она симметрична относительно середины, промежутка между двумя тройками, потому что x = (–x) по любому простому модулю. Сравним рисунок ниже – на нем эти числа показаны в виде прямоугольников – с формой рассеивателя на предыдущем рисунке. Обратите внимание: в данном случае глубина выемок получается путем вычитания вычетов из какой-то постоянной величины. Это не оказывает серьезного влияния на основной математический смысл.
Что такого особого в квадратичных вычетах? Одна из характеристик звуковой волны – ее частота: сколько волн приходит в ухо каждую секунду. Высокие частоты дают высокие звуки, низкие частоты – низкие звуки. Еще одна характеристика, связанная с частотой, – длина волны: расстояние между последовательными пиками. Высокочастотные волны короче, низкочастотные – длиннее. Колебания с заданной длиной волны резонируют с пустотами в поверхности, размеры которых близки к длине их волны. Так что волны разных частот по-разному реагируют на столкновение с поверхностью.
Рассеиватель на основе квадратичных вычетов обладает восхитительным математическим свойством: волны различных частот взаимодействуют с ним одинаково. Технически это означает, что преобразование Фурье постоянно на некотором диапазоне частот. Шрёдер указал на одно важное следствие: такая форма рассеивает звуковые волны многих разных частот одинаково. На практике ширина бороздок выбирается так, чтобы избежать диапазона волн, доступных для человеческого уха, а их длина кратна с определенным коэффициентом последовательности квадратичных вычетов, связанных с шириной.
Когда бороздки параллельны, как на рисунке, звук рассеивается в стороны, под прямым углом к бороздкам. Существует двумерный аналог этой системы – квадратное поле со стержнями, тоже рассчитанными на основе квадратичных вычетов, – который рассеивает звук равномерно во всех направлениях. Такие рассеиватели часто можно найти в звукозаписывающих студиях, где они помогают улучшить звуковой баланс и избавиться от лишних шумов.
Так что хотя Эйлер и Гаусс понятия не имели, для чего когда-нибудь будет использовано их изобретение и будет ли оно использовано хоть для чего-то, оно нередко играет принципиально важную роль (неявно, где-то за сценой), кога вы слушаете записанную музыку, будь то классика, джаз, кантри, рок, хип-хоп, кроссовер-трэш металлика – все что угодно.
Дополнительную информацию см. в главе «Загадки разгаданные».
Тайна универсальной плитки
Из мемуаров доктора Ватсапа
– Расследование преступления часто сравнивают со складыванием пазла, – заметил Сомс неожиданно, без всякого повода. Если, конечно, не считать поводом голубоватую струйку дыма из его трубки, за которую так и хотелось потянуть. Дым окутывал его голову настоящим облаком.
– Уместное сравнение! – отозвался я, поднимая голову от газеты.
Он хитро улыбнулся.
– Вовсе нет, Ватсап. Напротив, очень неудачное. Расследуя преступление, мы не знаем, какими могут быть эти кусочки, и не можем даже сказать, все ли они находятся в нашем распоряжении. Не зная, что за головоломка у нас в руках, как можем мы быть уверены в ответе?
– Право, Сомс, ведь это становится очевидным, когда достаточное число известных элементов складывается в единый элегантный узор.
Он вздохнул.
– Ах, но кусочков может быть так много, Ватсап! И разных узоров, которые они могут образовать, тоже. Чтобы решить, который из них правильный, нужно обладать определенным… je ne sais quoi[29]. Но я не знаю, чем именно.
В этот момент раздался стук в дверь, и в гостиную буквально ворвалась какая-то женщина.
– Беатрис! – воскликнул я.
– О, Джон! Ее украли! – и она, рыдая, бросилась в мои объятия. Я постарался утешить ее как мог, хотя мое сердце, признаюсь, пустилось вскачь.
Через некоторое время она успокоилась.
– Пожалуйста, помогите мне, мистер Сомс! Это рубиновая подвеска, она досталась мне от матери. Я везде искала ее сегодня утром, но она исчезла!
– Не расстраивайтесь, дорогая, – сказал я, похлопывая Беатрис по плечу. – Мы с Сомсом поймаем вора и вернем вашу драгоценность.
– Вы приехали в кэбе? – поинтересовался Сомс.
– Да. Он ждет снаружи.
– Тогда не будем терять времени и обследуем место преступления.
Через полчаса ползания по полу, взятия образцов пыли из углов в нескольких комнатах и внимательного осмотра порога и клумб под окнами Сомс покачал головой.
– Никаких следов взлома и проникновения, мисс Шипшер. А вот на вашей шкатулке с украшениями есть маленькие царапины. Свежие и не ваши, поскольку сделаны левшой, – он поставил шкатулку на место. – Бывали ли в доме в последнее время посторонние? Может быть, торговцы?
– Нет… Ох! Плиточники!
Два человека, назвавшиеся плиточниками, стучались с черного хода и предлагали обновить ванную комнату в доме.
– Это новая мода, мистер Сомс. Белые квадратные плитки, среди которых из плиток более сложной формы выложен синий узор. У Димвортов ванную отделали таким образом в прошлом месяце, и отец… – ее голос сорвался, Беатрис расстроенно замолчала, чуть не плача. Я взял ее за руку.
– Часто вы нанимаете незнакомых рабочих, которые стучатся к вам с черного хода? – поинтересовался Сомс.
– Что вы, нет, мистер Сомс. Обычно мы стали бы разговаривать только с солидной фирмой. Но у них у всех полно заказов и все расписано на несколько месяцев вперед. А эти рабочие казались честными, достойными людьми.
– Так всегда бывает. Оставляли ли вы кого-нибудь из них без присмотра?
Она мгновение подумала.
– Да. Помощник остался измерять ванную комнату, пока мастер показывал мне образцы плитки и орнамента.
– У него было вполне достаточно времени, чтобы украсть небольшую, но ценную вещицу. Они умны: не стали жадничать и тем самым обеспечили себе запас времени. Кражу заметили не сразу. Оставили они какие-нибудь документы?
– Нет.
– Приходили ли они еще раз?
– Нет, я жду от них письменной оценки стоимости работы.
– Рискну предположить, что вы ее не получите, мадам. Такой modus operandi[30] мы, детективы, называем «кражей с отвлечением».
Всю следующую неделю к Сомсу шел постоянный поток дам с аналогичными рассказами. Описание внешности «рабочих» менялось, но Сомса это нисколько не удивляло.
– Маскировка, – говорил он.
Перелом произошел на тринадцатом деле, краже из дома миссис Амелии Фотервелл. Сомс заметил катышек грязи, прилипший к двери в ванную, и маленький осколок кости в нем. Состав грязи и природа кости привели нас на грязный задний двор рядом с фабрикой по консервированию сардин в лабиринте узеньких улочек позади портовых доков.
– Итак, сейчас мы вломимся сюда и поищем доказательства? – сказал я, потянувшись за револьвером.
– Нет, это может спугнуть вора. Мы вернемся на Бейкер-стрит и соберем дело.
– Скажите мне, Ватсап, – начал он, когда мы распили бутылочку портвейна. – Какие общие черты объединяют все эти кражи?
Я назвал все черты, какие пришли мне в голову.
– Очень хорошо. Но вы упустили самую важную черту. Узоры. У вас, несомненно, есть их список?
Я вытащил блокнот и прочел:
• Миссис Уоттон: три плитки, образующие равносторонний треугольник.
• Беатрис: четыре плитки, образующие квадрат.
• Мисс Мейкпис: четыре плитки, образующие квадрат с квадратным отверстием.
• Близнецы из Кранфорда: четыре плитки, образующие прямоугольник с прямоугольным отверстием.
• Миссис Броудсайд: четыре плитки, образующие выпуклый шестиугольник.
• Миссис Проберт: четыре плитки, образующие выпуклый пятиугольник.
• Леди Каннигем: четыре плитки, образующие равнобедренную трапецию.
• Мисс Уилберфорс: четыре плитки, образующие параллелограмм.
• Миссис МакЭндрю: четыре плитки, образующие крылья ветряной мельницы.
• Миссис Тушингем: шесть плиток, образующие шестиугольник с шестиугольным отверстием.
• Мисс Браун: шесть плиток, образующие равносторонний треугольник со срезанными углами.
• Дама Дженки-Глейзуорси: 12 плиток, образующие правильный двенадцатиугольник с отверстием в виде правильной двенадцатиконечной звезды.
• Миссис Фозервелл: 12 плиток, образующие правильный двенадцатиугольник с отверстием в виде двенадцатиконечной звезды, формой напоминающей циркулярную пилу.
– Замечательная коллекция, – сказал Сомс. – Мне кажется, пора послать кого-нибудь из Нерушимых сил Бейкер-стрит к инспектору Роулейду с просьбой проверить владение у доков.
– И что, вы думаете, полиция там найдет?
– Вспомните, Ватсап: все дамы говорили нам, что их узор состоял из некоторого количества одинаковых плиток.
– Да.
– Но узоры очень разные, и это наталкивает на мысль, что, хотя каждый из узоров складывался из одинаковых плиток, для разных узоров нужны были плитки разной формы. Дамы не могут описать форму плиток кроме как словом «неправильная», так что у нас нет никаких данных в пользу того, что во всех узорах использовались плитки одинаковой формы. Поэтому я ожидаю, что полиция найдет 13 ящиков с плитками необычной формы: по одному на каждый узор.
Через пару часов в гостиную заглянула миссис Сопсудс.
– Инспектор Роулейд, мистер Сомс.
Инспектор вошел в сопровождении констебля с каким-то ящиком в руках.
– Я поместил под арест двух подозреваемых, – объявил он.
– Роланд «Крыса» Ратценберг и «Мордоворот» МакГинти.
– Да, но как, бога ради… о, неважно. Я могу держать их 24 часа. Но доказательства слабые.
Сомс взглянул на него пораженно.
– Но вы, конечно, нашли у них ящики с плиткой? Разве этот ящик – не образец того, что там было?
Инспектор покачал головой.
– Нет, это все, что там было.
Сомс подошел к ящику и открыл его. В нем лежало 12 одинаковых плиток.
– Вот это да, – сказал он.
– Кажется, дело развалилось, – рискнул вставить я. – Не могу поверить, что все узоры из такого разнообразного списка можно выложить одними и теми же плитками.
Но Сомс внезапно оживился.
– Может быть, вы и правы, – сказал он. – Если только… – он вытащил линейку и угломер и начал измерять одну из плиток.
Через несколько мгновений его лицо расплылось в улыбке.
– Умно! – сказал он. – Очень умно, – он обернулся ко мне. – Я поступил чрезвычайно глупо и сделал скоропалительные выводы, тогда как нужно было сохранять трезвый ум. Помните, о чем мы говорили непосредственно перед тем, как появилась расстроенная Беатрис?
– Э-э… о пазлах, которые складывают из кусочков.
– Точно. А это дело основано на одной из самых замечательных головоломок, какие мне только приходилось встречать. Взгляните на эту плитку.
– Мне она кажется весьма обычным четырехугольником, – сказал я.
– Нет, Ватсап. Это очень необычный четырехугольник. Позвольте мне продемонстрировать вам, – и он нарисовал схему.
– Стороны AB и BC равны, а угол ABC прямой, так что углы BAC и BCD составляют по 45°, – объяснил Сомс. – Угол ACD равен 15°, так что BCD равен 60°. Угол ADC опять же прямой, что делает угол CAD равным 75°.
Инспектор и я ничего не поняли. Сомс вручил мне четыре плитки.
– Ватсап, попробуйте сложить из этих плиток какую-нибудь элегантную фигуру. Примерно как детектив складывает вместе улики и делает элегантные выводы, если вспомнить вашу аналогию.
– Могу я их переворачивать?
– Прекрасный вопрос! Да, любую плитку можно перевернуть.
Я немного поэкспериментировал. Внезапно ответ встал перед глазами.
– Сомс! Из них получается квадрат – узор Беатрис! Как красиво!
Сомс взглянул на мою небольшую головоломку.
– В самом деле. Вы по-прежнему утверждаете, что элегантное объяснение нескольких улик может служить определяющим доказательством того, что виновный найден?
– Как иначе все улики могут так сойтись, Сомс?
– В самом деле, как? – я понял, что вопрос был риторическим. – В ваших рассуждениях есть прореха, Ватсап, – продолжал он, когда я отказался отвечать. – Нужно ее устранить, – он наклонился и переложил плитки так, что получился заполненный квадрат.
– Ох, – пристыженно произнес я. – Значит, это – узор Беатрис.
– Предполагаю, что да. Но не расстраивайтесь: ваш узор принадлежит мисс Мейкпис.
Меня осенило.
– Вы думаете, что из копий одной этой плитки можно сложить все 13 узоров?
– Я в этом уверен. Смотрите: вот так из трех плиток складывается узор миссис Уоттон, равносторонний треугольник с треугольным отверстием.
– Господи, Сомс!
– Это замечательно универсальная… э-э… плитка, – ответил он. – Благодарить за это нужно ее хитрую геометрию.
– Итак, все, что нам нужно сделать… – начал я.
– …это найти варианты раскладки, соответствующие остальным десяти узорам! – закончил за меня Роулейд.
Сомс начал прочищать трубку.
– Я уверен, что смело могу оставить эту задачу вам, джентльмены.
В тот вечер я взял кэб и поехал в дом отца Беатрис, остановившись только у ювелира, чтобы кое-что забрать. Беатрис приняла меня в гостиной.
Я поставил на стол длинную коробочку.
– Дорогая, откройте.
Она несмело протянула руку, и на милом лице ее отразилась надежда.
– О! Джон, вы нашли мою подвеску! – она взяла меня за руку. – Как я могу отблагодарить вас? – внезапно она замолчала. – Но… Это не мое, – она вынула из коробки сверкающую драгоценность. – Это обручальное кольцо.
– Да, это так. И оно может стать вашим, – произнес я, опускаясь на одно колено.
Можете ли вы найти оставшиеся десять вариантов узора? Ответы см. в главе «Загадки разгаданные».
Гипотеза о трекле
Граф – это набор точек (узлов), соединенных линиями (ребрами). Если граф рисуют на плоскости, ребра часто пересекаются между собой. В 1972 г. Джон Конвей определил трекл как граф, нарисованный на плоскости, у которого любые два ребра либо встречаются в узле и больше не пересекаются, либо не встречаются в узле, но при этом пересекаются ровно один раз. Говорят, что идею названия подал автору один шотландский рыболов, постоянно жаловавшийся на то, что у него запуталась (thrackled) леска.
На рисунке показаны два трекла. Левый имеет в своем составе 5 узлов и 5 ребер, тогда как правый – 6 узлов и 6 ребер. Конвей предположил, что у любого трекла число ребер меньше или равно числу узлов. Он предложил бутылку пива в награду тому, кто сможет это доказать или опровергнуть, но с годами, поскольку решение не появлялось, приз вырос до тысячи долларов.
Оба приведенных трекла представляют собой замкнутые петли (их узлы располагаются на кольцевом маршруте), нарисованные с наложением. Известно, что любая замкнутая петля с n 5 узлов может быть нарисована так, что образует трекл. Если это правда, то число E ребер может быть равно числу n узлов при любом n 5. Пал Эрдёш доказал, что гипотеза о трекле верна для любого графа с прямыми ребрами. Наилучшее на данный момент ограничение на размер E доказали Радослав Фулек и Янош Пач в 2011 г.:
Ссылку на дополнительную информацию см. в главе «Загадки разгаданные».
Сделка с дьяволом
Один математик, потративший десять бесплодных лет на попытки доказать гипотезу Римана, решил продать душу дьяволу в обмен на вожделенное доказательство. Дьявол обещал представить ему доказательство не позже чем через неделю, но неделя прошла, и ничего не произошло.
Через год дьявол вновь явился математику с мрачным видом.
– Извини, я тоже не смог это доказать, – сказал он, возвращая математику его душу. Он немного помолчал и вдруг просиял: – Но мне кажется, что я нашел по-настоящему интересную лемму!
Рискуя испортить шутку, я поясню, что в математике лемма – это не слишком важное утверждение, основной интерес которого заключается в том, что оно может стать шагом на пути к доказательству другого, более важного утверждения, достойного звания теоремы. Между теоремой и леммой нет никакой логической разницы, но психологически слово «лемма» означает, что кому-то удалось пройти только часть пути к желанной цели…
Ну, я пошел…
Непериодическая мостовая
Замостить плоскость без промежутков и перекрытий можно множеством различных фигур. Единственными правильными многоугольниками, с помощью которых можно это проделать, являются равносторонний треугольник, квадрат и шестиугольник.
Кроме них плоскость можно замостить громадным количеством менее правильных фигур, таких как семисторонний многоугольник на следующем рисунке. Он получен из правильного семиугольника путем зеркального отображения трех его сторон относительно линии, соединяющей их концы.
Мощение правильными многоугольниками периодично, то есть его элементы повторяются бесконечно в двух различных направлениях, как узор на обоях. Спиральное мощение не периодично. Однако описанным здесь семиугольником можно замостить плоскость и периодически.
Как именно? Ответ см. в главе «Загадки разгаданные».
Существуют ли фигуры, которыми можно замостить плоскость, но нельзя сделать это периодически? Вопрос этот глубоко связан с математической логикой. В 1931 г. Курт Гёдель доказал, что в арифметике существуют неразрешимые задачи, то есть утверждения, для которых никакой алгоритм не в состоянии определить, истинны они или ложны. (Алгоритм – это систематический процесс, который гарантированно прекращается при получении верного ответа.) Из этой теоремы следует другая, более драматичная: в арифметике существуют утверждения, которые невозможно ни доказать, ни опровергнуть.
Приведенный Гёделем пример такого утверждения был несколько надуманным, и специалисты по математической логике долго гадали, существуют ли более естественные нерешаемые проблемы. В 1961 г. Хао Ван работал над проблемой домино: если имеется конечное число фигур для мощения, то существует ли алгоритм,который был бы способен определить, можно ли этими фигурами замостить плоскость? Ван показал, что если существует подходящий набор, которыми можно замостить плоскость, но нельзя замостить ее периодически, то такого алгоритма не существует. Его идея состояла в том, чтобы перевести правила логики в формы плиток и использовать результаты вроде гёделевых. И она сработала: в 1966 г. Роберт Бергер нашел набор из 20 426 таких плиток, доказав тем самым, что проблема домино действительно неразрешима.
20 000 различных фигур – это много. Бергеру удалось снизить их число до 104; затем Ганс Лейхли снизил его до 40. Рафаэль Робинсон довел число форм до шести. Роджер Пенроуз, открыв в 1973 г. так называемые плитки Пенроуза (см. «Кабинет…» с. 149), еще уменьшил их число, всего до двух. Получилась интригующая математическая загадка: существует ли единственная фигура, с помощью которой можно замостить плоскость, но нельзя замостить ее периодически? (При этом можно использовать также зеркальное отражение той же фигуры.) Ответ был найден в 2010 г. Джошуа Соколаром и Джоан Тейлор[31], и ответ этот – «да».
Предложенная ими фигура показана на рисунке. Это «разрисованный шестиугольник» с дополнительными «правилами стыковки», и он отличается от собственного зеркального отражения. Рисунки на плитке должны стыковаться вполне определенным образом – так, как показано на рисунке.
На следующем рисунке показана центральная область замощенной такими фигурами плоскости. Можно заметить, что узор на ней не выглядит периодическим. В статье объясняется, почему такое мощение можно распространить на всю площадь и почему результат не может быть периодическим. Подробности можно узнать непосредственно из статьи.
Теорема о двух красках
Из мемуаров доктора Ватсапа
– Ну, Сомс, эта забавная небольшая головоломка сможет поднять вам настроение, – я перебросил Daily Reporter другу и компаньону, почти знаменитому детективу, страдавшему в настоящее время от приступа депрессии потому только, что его конкурент из дома напротив явно достиг большей известности и имел все шансы это преимущество сохранить.
Он, издевательски рассмеявшись, отбросил газету в сторону.
– Ватсап, у меня не хватит энергии на чтение.
– Тогда я сам вам прочту, – ответил я. – Кажется, знаменитый математик Артур Кейли опубликовал статью в «Записках Королевского географического общества», в которой задал вопрос…
– Вопрос о том, можно ли раскрасить произвольную карту не более чем четырьмя красками так, чтобы соседние области оказались окрашенными в разные цвета, – прервал меня Сомс. – Это давняя проблема, Ватсап, и я боюсь, что ответ на этот вопрос не будет получен при нашей жизни. – Я ничего не сказал, надеясь вытащить его на дальнейший разговор, поскольку это была самая длинная фраза, которую он произнес почти за неделю. Мой план сработал, и после минуты неловкого молчания он продолжил: – Молодой человек по имени Фрэнсис Гутри сформулировал эту задачу за два года до моего рождения. Будучи не в состоянии решить ее самостоятельно, он обратился к своему брату Фредерику, ученику профессора Огастеса де Моргана.
– Ах да, Гусси, – вставил я, поскольку был знаком с семьей этого достойного восхищения чудака, автора книги «Бюджет парадоксов» и бича всех свихнувшихся на математике.
– Де Морган, – продолжал Сомс, – ничего не добился, поэтому попросил заняться ею великого ирландского математика сэра Уильяма Роуэна Гамильтона, который, однако, ответил ему отказом. На том все и застопорилось до тех пор, пока Кейли вновь не взялся за эту задачу. Хотя я не представляю, почему он решил опубликоваться именно в этом журнале.
– Возможно, потому, – предположил я, – что географы интересуются картами? – но Сомс только презрительно хмыкнул.
– Не в таком аспекте, – раздраженно отмахнулся он. – Географ раскрасит области на карте в соответствии с политической обстановкой, не обращая внимания на соседство. Смотрите, Кения, Уганда и Танганьика расположены рядом, но на всех картах Британской империи все они окрашены в одинаковый розовый цвет.
Я признал справедливость этого утверждения. Нашей дорогой королеве не понравилось бы, если бы их раскрасили иначе.
– Но, Сомс, – я продолжал настаивать, – вопрос от этого не становится менее интересным. Даже более, поскольку никто, похоже, не в состоянии на него ответить.
Сомс что-то проворчал.
– Давайте все же попробуем, – сказал я и быстро нарисовал условную карту.
– Забавно, – заметил Сомс. – А почему вы сделали все области круглыми?
– Потому что любая область без дырок топологически эквивалентна кругу.
Сомс поджал губы.