Математические головоломки профессора Стюарта Стюарт Иэн

В настоящее время мы можем пойти значительно дальше. Миллион – это 1 000 000, так, мелочь. Мы можем получить намного более крупные числа, просто подставив в конце еще нуликов и наблюдая, как возрастает число стандартных групп по три цифры (математики нередко разделяют их тонким пробелом для наглядности). В западном мире существуют стандартные наименования для больших чисел, отражающие эту традицию: миллион, биллион, триллион, … и далее до сентиллиона. Но человек так устроен, что у него не может быть все просто, особенно в математике, поэтому эти слова имеют (или, по крайней мере, имели раньше) разные значения по разные стороны Атлантики. В США биллион равен 1 000 000 000, но в Великобритании этим словом называют 1 000 000 000 000 – то есть то, что американцы назвали бы триллионом. Однако в нынешнем взаимосвязанном мире победил американский вариант – возможно, потому, что «миллиард» (британское название для тысячи миллионов), во-первых, устаревает и, во вторых, его слишком легко спутать с «миллионом». А биллион[24] – чудесное круглое число для международных финансов, по крайней мере до тех пор, пока мировые банки не выбросят на ветер финансового кризиса так много, что нам придется привыкать думать в триллионах.

Эти же числа можно записать и проще, если использовать степени 10. В этом случае 10⁶ обозначает 1 с шестью нулями, то есть миллион. Число 6 здесь называют показателем экспоненты. Биллион – это 10⁹ (миллиард), или 10¹² (триллион) в старомодном британском варианте. Сентиллион превращается в 10³⁰³ (10⁶⁰⁰ в британском варианте). Признанные расширения к стандартным названиям существуют вплоть до миллиниллиона, 10³⁰⁰³. Существует несколько систем таких расширений, но жизнь слишком коротка, чтобы описывать их все или хотя бы подробно описывать разницу между ними.

Еще два названия для больших чисел, которые также можно найти в большинстве словарей, – это гуголь и гугольплекс. Гуголь – это 10100 (1 со ста нулями); название придумал в свое время девятилетний племянник Джеймса Ньюмена Милтон Сиротта. Сиротта предложил и еще большее число – гуголплекс, которое определил так: «Я писал нули, пока ты не устал». Некоторая неопределенность количества нулей потребовала уточнения: «Я поставил еще гугол нулей».

Это более интересно, поскольку здесь мы сталкиваемся с той же проблемой, с какой столкнулись когда-то римляне, с той разницей, что они занялись ею намного раньше. Если вы попытаетесь записать гуголплекс в десятичном виде, как 1 000 000 000 …, то вам не хватит жизни, чтобы добраться до его конца. Строго говоря, вам не хватит для этого времени жизни всей Вселенной. Считая, что современные космологические представления верны, Вселенная, вероятно, закончит свое существование раньше, чем вы закончите писать это число. Во всяком случае, места для всех этих нулей вам не хватит даже в том случае, если каждый из них размером будет не больше кварка.

Однако существует и компактный способ записи гуголплекса: итерационная экспонента, или экспонента экспоненты. А именно:

10¹⁰.

И раз уж вы начали думать о подобных вещах, то добавим, что этот метод позволяет добраться до по-настоящему очень больших чисел. В 1976 г. ученый-компьютерщик Дональд Кнут придумал способ записи очень больших чисел, которые, помимо всего прочего, фигурируют в некоторых областях теоретической информатики. Когда я говорю «очень больших», я подразумеваю очень большие числа – настолько большие, что способа даже начать их записывать в традиционной нотации просто не существует. Гуголплекс, то есть единица с 10¹⁰⁰ нулей, меркнет по сравнению с большинством чисел, которые можно записать при помощи нотации со стрелочкой Кнута.

Кнут начинает с записи

ab = ab.

К примеру, 1102 = 100, 103 = 1000, 10100 – гугол, а 10(10100) – гуголплекс. Традиционная договоренность о том, в каком порядке вычисляются экспоненты (справа налево), позволяет нам записать это проще – как 1010100. Не нужно обладать особенно развитым воображением, чтобы записать, скажем, 10101010101010.

Но это только начало. Пусть

a4 = a(a(aa)).

К примеру,

24 = 2(2(22)) = 2(24) = 216 = 65 536

33 = 333 = 327 = 7 625 597 484 987.

Числа растут настолько стремительно, что записать их цифра за цифрой очень скоро становится попросту невозможно. К примеру, в числе 44 насчитывается 155 десятичных знаков. Но в этом-то и смысл: стрелочная нотация обеспечивает компактный способ обозначения гигантских чисел. Однако мы едва начали. Пусть

ab = aa…a,

где a в правой части равенства фигурирует b раз. Здесь опять же вычисляются справа налево. Ну, вы понимаете: далее мы можем ввести

ab = aa…a,

и т. д., где, как обычно, a присутствует b раз, а оценка производится справа налево.

Р. Гудштейн развил нотацию Кнута и упростил ее, введя выражения, названные им гипероператорами. Джон Конвей разработал собственную стрелочную нотацию с горизонтальными стрелочками и скобками.

В теории струн – области теоретической физики, целью которой является объединении теории гравитации с квантовой механикой, число 1010500 имеет вполне определенный смысл: это число потенциально различных структур пространства – времени. Согласно Дону Пейджу, самое длинное конечное время, в явном виде рассчитанное физиками, составляет всего лишь

10101010101,1 лет.

Это время возвращения Пуанкаре для квантового состояния черной дыры с массой, равной массе всей Вселенной, то есть время, чеез которое эта система вернется в свое первоначальное состояние и, по существу, история повторится.

Число Грэма

Иногда математикам требуются более крупные числа, чем физикам. Не только, надо заметить, для развлечения: дело в том, что такие числа на самом деле иногда всплывают в разумных актуальных задачах. Число Грэма, названное в честь американца Рона Грэма, возникает в комбинаторике – математике подсчета различных способов перестановки объектов или выполнения каких-то условий.

В 1978 г. Грэм и Брюс Ротшильд работали над задачей о гиперкубах – многомерных аналогах куба. У квадрата 4 угла, у куба – 8, у четырехмерного гиперкуба – 16, а у n-мерного гиперкуба – 2ⁿ углов. Они соответствуют всем возможным последовательностям из n нулей и единиц в системе n координат.

Возьмем n-мерный гиперкуб и проведем линии, соединяющие все пары углов. Покрасим каждую линию либо в красный цвет, либо в синий. Для какого наименьшего n в любой схеме такой раскраски найдется по крайней мере один набор из четырех углов, лежащих на одной плоскости, таких, что все соединяющие их отрезки окрашены в один и тот же цвет?

Два упомянутых математика доказали, что такое число n существует, что далеко не очевидно. Ранее Грэм нашел более простое доказательство, но с использованием большего числа: в стрелочной нотации Кнута n, о котором идет речь, не превосходит

Здесь числа под горизонтальными фигурными скобками указывают, сколько стрелок стоит над соответствующей скобкой. Смотреть нужно снизу вверх, начиная с самой нижней строки: в предпоследнем (63-м) слое стоит 33 стрелки. Далее, число с таким количеством стрелочек дает нам число стрелочек в следующем, 62-м слое. А число с таким количеством стрелочек – число стрелочек в 61-м слое!.. Извините, ни одно из этих чисел нельзя записать в стандартной десятичной нотации. В этом отношении они намного хуже гуголплекса. Но в этом и заключается их прелесть…

Это и есть число Грэма, и оно поистине громадно. Более чем. Величина, найденная Грэмом и Ротшильдом, меньше, но по-прежнему до безобразия велика, и объяснять ее сложнее, так что я не буду этим заниматься.

Как ни смешно, специалисты, работающие в этой области, считают, что это число можно сделать намного меньше. А именно, что годится даже n = 13. Но это пока не доказано. Грэм и Ротшильд доказали, что n не может быть меньше 6; Джефф Эксоо поднял эту величину до 11 в 2003 г.; наилучший результат на сегодняшний день гласит, что n не должно быть меньше 13, что доказал Джером Баркли в 2008 г.

Дополнительную информацию см. в главе «Загадки разгаданные».

В моей голове это не укладывается

Когда ученые говорят о больших числах, таких как возраст Вселенной (13,798 млрд лет, или около 4,35 секстиллиона секунд) или расстояние до ближайшей звезды (0,237 светового года, или около 2,24 трлн км), мы, как правило, произносим что-нибудь вроде «в голове не укладывается». То же можно сказать об издержках глобального финансового кризиса, составивших, по одной из верхних оценок, для экономики Великобритании 1,162 трлн[25] фунтов стерлингов. Или, скажем, круглым счетом триллион, 10 фунтов стерлингов.

Миллионы, миллиарды, триллионы – для многих несведущих людей эти слова очень похожи, да и означают примерно одно и то же: они слишком велики и просто в голове не укладываются.

Неспособность человека осознать и «прочувствовать» большие числа сказывается на наших взглядах во многих областях, в первую очередь в политике. Когда Эйяфьятлайокудль в Исландии начал плеваться вулканическим пеплом и вынудил отстаиваться на земле большую часть британских самолетов, было много протестов, особенно со стороны авиалиний. (Мне и самому не повезло: вместо того чтобы полететь в Эдинбург, мне пришлось срочно менять планы и ехать на автомобиле.) Было подсчитано, что простои обходились индустрии авиаперевозок в 100 млн фунтов в день: 10⁸ фунтов.

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

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

цена банковского кризиса: 10 фунтов;

цена одного вулканического дня: 10⁸ фунтов;

10¹²/10⁸ = 10⁴ дней = 27 лет.

Этот период представляется мне в высшей степени наглядной величиной: очевидно, что 27 лет – это намного дольше, чем один день. Поэтому я вполне могу осознать, что запрет на полеты должен был бы продолжаться 27 лет, чтобы потери от него сравнялись с экономическим ущербом от банковского кризиса, не обращая внимания на то, что большие числа, участвующие в расчете, не укладываются у меня в голове.

Именно для этого и нужна математика. Не нужно, чтобы вещи укладывалисьу вас в голове: лучше их посчитать.

Дело водителя с уровнем выше среднего
Из мемуаров доктора Ватсапа

Я с отвращением бросил газету на стол.

– Послушайте, Сомс… Вы только взгляните на эту нелепую статистику!

Хемлок Сомс хмыкнул и сосредоточился на раскуривании трубки.

– Семьдесят пять процентов кэбменов уверены, что их способности к управлению кэбом выше средних!

Сомс поднял голову.

– Что же в этом нелепого, Ватсап?

– Ну, я… Сомс, но это же просто невозможно! Все они, должно быть, имеют о себе завышенное мнение!

– Почему?

– Потому что среднее должно быть в середине.

Детектив вздохнул.

– Обычное заблуждение, Ватсап.

– Заблуж… что здесь не так?

– Да почти все, Ватсап. Представьте, что 100 человек оценили по шкале от 0 до 10. Если 99 из них получили оценку 10, а один – оценку 0, какое будет среднее?

– Э-э… 990/100… это будет 9,9, Сомс.

– И сколько из них окажется выше среднего?

– Э-э… 99.

– Я же говорю, заблуждение.

Но меня непросто было отвлечь.

– Но все они лишь чуть-чуть превосходят среднее, Сомс, да и данные не слишком типичны.

– Я намеренно выпятил этот эффект, чтобы сделать его более заметным, Ватсап. Любые сдвинутые – асимметричные – данные, как правило, ведут себя сходным образом. Предположим, к примеру, что большинство кэбменов достаточно компетентны, значительное меньшинство ужасны, а несколько человек – очень немного – превосходны в своем деле. Кто из кэбменов в таком случае окажется выше среднего?

– Ну… дурные утянут среднее значение вниз, и превосходных не хватит, чтобы их уравновесить… Господи! Все компетентные и превосходные кэбмены окажутся выше среднего!

– В самом деле, – отозвался Сомс. Он быстро набросал на каком-то случайном листе диаграмму. – С этими данными, которые более реалистичны, среднее значение равно 6,25, и 60 % кэбменов оказываются выше него.

– Так что статья в Manchester Mirrograph ошибочна? – поинтересовался я.

– Вас это удивляет, Ватсап? Откровенно говоря, у них редко попадаются полностью правдивые статьи. Но здесь журналист угодил в обычную ловушку. Он спутал среднее значение с медианным, которое определяется как значение, для которого половина оценок находится выше, а половина – ниже. Эти две величины часто не совпадают.

– Получается, что 75 % кэбменов ни при каких обстоятельствах не могут иметь уровень выше медианного?

Только если число кэбменов равно нулю.

– Но при этом 75 % кэбменов в принципе может иметь уровень выше среднего?

– Да.

– И это не означало бы, что у них всех завышенное самомнение?

Сомс снова вздохнул.

– А вот это, мой дорогой Ватсап, совсем другой коленкор, и даже другого цвета. Существует распространенная форма когнитивной ошибки, которую называют иллюзорным превосходством. Многие воображают себя выше других, даже если это на самом деле не так. Почти все мы страдаем этим заблуждением, за исключением, естественно, меня. В прошлом месяце журнал Quantitative Phrenology and Cognition[26] написал, что 69 % шведских кэбменов считают свои способности выше медианных. Это точно иллюзия, даже не сомневайтесь.

Реальные современные данные см. в главе «Загадки разгаданные».

Куб «Мышеловка»

Джереми Фаррелл придумал магический словарный куб, который подчиняется тем же правилам, что и его магические квадраты. В кубе задействовано слово MOUSETRAP (мышеловка), а буквам присвоены следующие магические значения: M = 0, O = 0, U = 2, S = 6, E = 9, T = 18, R = 3, A = 1, P = 0. Некоторые из слов куба представляют собой личные имена, а некоторые используются очень редко. К примеру, OSE – это имя какого-то демона, а также название мест в Японии, Нигерии, Польше, Норвегии и на острове Скай. Тем не менее поразительно уже то, что такую вещь в принципе можно сделать.

Числа Серпинского

Специалисты по теории чисел, занятые поисками больших простых чисел, часто рассматривают числа вида k2ⁿ + 1 для какого-то выбранного k при разных n. Пробные расчеты позволяют предположить, что для большинства значений k среди этих чисел встречается по крайней мере одно простое число, часто больше. К примеру, если k = 1, то 1 2ⁿ + 1 является простым для n = 2, 4, 8. Если k = 3, то 3 2ⁿ + 1 простое при n = 1, 2, 5, 6, 8, 12. Если k = 5, то 5 2ⁿ + 1 простое при n = 1, 3, 7. (В общем случае мы можем разделить k на 2 столько раз, сколько нужно, чтобы получить нечетное число, а все двойки включить в 2n. Поэтому можно смело считать k нечетным, не теряя общности. К примеру, 24 2ⁿ = 3 23 2ⁿ = 3 2ⁿ⁺³.)

Соблазнительно предположить, что для любого k2 существует по крайней мере одно простое число вида k2ⁿ + 1. Однако в 1960 г. Вацлав Серпинский доказал, что существует бесконечно много нечетных k, для которых все числа вида k2ⁿ + 1 являются составными. Эти числа получили название чисел Серпинского.

В 1992 г. Джон Селфридж доказал, что 78 557 – число Серпинского; он показал, что все числа вида 78 557 2ⁿ + 1 делятся по крайней мере на одно из чисел 3, 5, 7, 13, 19, 37, 73. Говорят, что эти числа образуют покрывающее множество. Приведем первые десять известных чисел Серпинского:

78 557 271 129 271 577 322 523 327 739

482 719 575 041 603 713 903 983 934 909

Считается, что 78 557 – наименьшее число Серпинского, но пока этот факт никем не доказан и не опровергнут. В 2002 г. на сайте www.seventeenorbust.com был организован поиск простых чисел вида k2ⁿ + 1, существование которых доказывало бы, что k не является числом Серпинского. Когда поиск только начинался, у математиков было 17 кандидатов на роль чисел Серпинского, не превышающих 78 557, но постепенно они были ликвидированы, так что осталось только шесть: 10 223, 21 181, 22 699, 24 737, 55 459 и 67 607. Попутно в рамках проекта было найдено несколько очень больших простых чисел.

Джеймс Джозеф кто?

Джеймс Джозеф Силвестер – английский математик, работавший с Артуром Кейли, в частности в области теории матриц и теории инвариант. Всю жизнь он очень интересовался поэзией и часто вставлял стихотворные цитаты в свои математические научные статьи. В 1841 г. он переехал в США, но вскоре вернулся обратно. В 1877 г. он вновь пересек Атлантику, занял место первого профессора математики в Университете Джона Хопкинса и основал American Journal of Mathematics, издающийся с немалым успехом и сегодня. Он вернулся в Англию в 1883 г.

Изначально его звали просто Джеймс Джозеф. Когда его старший брат эмигрировал в США, в офисе иммиграционной службы ему сказали, что у каждого должно быть по три имени: два имени и фамилия. По какой-то причине брат взял себе новую фамилию – Силвестер, сделав прежнюю вторым именем. Джеймс Джозеф последовал примеру брата.

Ограбление в Баффлхэме
Из мемуаров доктора Ватсапа

При ограблении величественного особняка лорда Баффлхэма из сейфа похитили несколько изумрудов и рубинов. Сомс, которого пригласили расследовать дело, быстро заподозрил двух гостей – леди Изабеллу Никетт и баронессу Руби Робхэм. Та и другая испытывали серьезные материальные трудности и, без сомнения, не устояли перед искушением. Но где доказательства?

Обе дамы признались, что у них есть кое-какие драгоценности, но утверждали, что это их собственность. Сомсу пока не удалось убедить инспектора Роулейда получить ордер на обыск в аристократических домах, хотя это могло бы разрешить все проблемы; пока же он не мог заглянуть в шкатулки с драгоценностями означенных дам.

– Дело, – сказал Сомс, – определяется тем, сколько драгоценностей имеют наши две дамы. Если их число совпадает с числом похищенных вещей, мы получаем последнее необходимое доказательство. Роулейд готов запросить ордер на обыск, но только если мы сможем снабдить его этими двумя числами.

– Изабелла заявила, что у нее имеются только изумруды, – пробормотал я вполголоса. – А Руби говорит, что у нее только рубины.

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

– Кухарка не настроена болтать о хозяйках, – заметил я. – Но мне удалось убедить ее открыть произведение этих двух чисел.

– А дворецкий, тоже неболтливый, но убежденный аргументом в виде десяти золотых соверенов, назвал мне их сумму, – отозвался Сомс.

– Значит, мы можем, решив квадратное уравнение, найти оба числа! – возбужденно воскликнул я.

– Разумеется, хотя мы не будем знать, какое из чисел относится к изумрудам, а какое – к рубинам, – протянул Сомс. – Данные симметричны. Но любого совпадения будет достаточно, чтобы инспектор Роулейд получил ордер на обыск, а там все, я не сомневаюсь, найдется.

– Если вы назовете мне произведение, – сказал я, – то я смогу решить уравнение.

– Ах, мой дорогой Ватсап, вам не достает утонченности, – критически заметил Сомс. – Дайте посмотреть, нельзя ли вывести числа без этого… Так, знаете, чему они равны?

– Нет.

– Я так и знал, – заявил Сомс, к моему раздражению. Если знал, зачем спрашивать? Неожиданно меня осенило.

– Теперь я тоже знаю эти числа, – объявил я.

– В таком случае я тоже их знаю, Ватсап.

Какие это два числа? Ответ см. в главе «Загадки разгаданные».

Квадриллион знаков числа

В настоящее время нам известно десятичное значение с точностью до 12 100 000 000 050 знаков; соответствующий расчет провел в 2013 г. Сигеру Кондо, и потребовалось ему на это 94 дня. На самом деле никому нет дела до того, какой получен ответ, но известно, что замечательные рекордные усилия такого рода нередко приводят к новым озарениям, а также являются хорошим способом проверки новых сперкомпьютеров. Одно из самых забавных открытий состоит в том, что можно вычислять отдельные цифры десятичной записи без нахождения всех предыдущих цифр. Однако в настоящее время мы можем это делать только в шестнадцатеричной нотации, то есть в системе счисления с основанием 16, из которой можно без труда получить цифры в системах счисления с основаниями 8, 4 и 2 (двоичной). Эта идея работает и для других констант, не только для , а также для троичной системы счисления, но систематической теории на этот счет пока нет. Для десятичной нотации, то есть для системы счисления с основанием 10, ничего подобного не известно.

Первоначальное открытие, формула ББП (Бейли – Боруэйна – Плаффа), изложена ниже; вы найдете ее также в «Кабинете…» на с. 264. Это бесконечный ряд, при помощи которого можно вычислить конкретный шестнадцатеричный знак числа , не вычисляя при этом предыдущих его знаков. Так что мы можем быть уверены, что квадриллионный двоичный знак числа – нуль, благодаря проекту PiHex; пройдя еще дальше, скажем, что двухквадриллионный двоичный знак также равен 0, благодаря расчету, проведенному одним из сотрудников компании Yahoo! и занявшему 23 дня. Несмотря на все наши познания, для того чтобы найти предыдущий знак, потребовался бы еще один столь же длительный расчет.

В 2011 г. Дэвид Бейли, Джонатан Боруэйн, Эндрю Маттинли и Гленн Уайтвик составили обзорное исследование этого вопроса[27]. Авторы описали способ нахождения знаков числа в системе счисления с основанием 64, знаков числа в системе счисления с основанием 729 и знаков числа, известного как постоянная Каталана, в системе счисления с основанием 4096, начиная с 10-триллионной позиции.

История начинается с последовательности, известной еще Эйлеру:

Благодаря степеням двойки, которые здесь фигурируют, этот ряд можно преобразовать в метод вычисления конкретных двоичных знаков ln 2. По мере роста номера знака вычисления остаются реализуемыми, хотя и занимают гораздо больше времени.

Формула ББП выглядит так:

и степени 16 делают возможным вычисление конкретных шестнадцатеричных знаков числа . Поскольку 16 = 2⁴, ряд можно использовать также для вычисления двоичных знаков.

Ограничивается ли такой подход только этими двумя константами? С 1997 г. математики ведут непрекращающийся поиск аналогичных бесконечных рядов для других постоянных величин, и им уже удалось найти их немалое количество. В том числе для , ln 2, ln 2, (3), , ln 2, ln 2, ⁴, (5),

где

есть Риманова дзета-функция. Удалось сделать то же для постоянной Каталана

Некоторые из этих рядов дают знаки в троичной системе счисления или системе с основанием, равным какой-нибудь степени 3. К примеру, при помощи поразительной формулы Дэвида Броудхерста

можно вычислять знаки в системе счисления с основанием 729 = 3⁶.

Нормально ли число ?

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

Можно доказать, что это свойство, известное как нормальность, выполняется для «почти всех» чисел: в любом достаточно большом наборе чисел доля нормальных подходит сколь угодно близко к 100 %. Но это правило оставляет и лазейку, поскольку любое конкретное число, скажем , может оказаться исключением. Но является ли оно исключением? Мы не знаем. До недавнего времени этот вопрос казался безнадежным, но формулы, подобные приведенным выше, открыли новую линию атаки, которая в принципе может решить вопрос в отношении двоичных (или шестнадцатеричных) чисел.

Связь между этими задачами возникает через другую математическую процедуру, итерационную. Здесь мы начинаем с какого-то числа, применяем к нему некое правило, чтобы получить другое число, и последовательно применяем то же правило к полученным числам, чтобы получить некую последовательность чисел. К примеру, если мы начнем с 2 и применим правило «возвести в квадрат», получим последовательность

2 4 16 256 65 636 4 294 967 296 …

Двоичные знаки числа, к примеру ln 2, можно получить при помощи итерационной формулы

начиная с x0 = 0. Пояснение (mod 1) означает «вычесть целую часть», так что (mod 1) = 0,14159… Эта формула привела бы к доказательству того, что ln 2 нормален по основанию 2, если бы удалось показать, что полученные в результате числа равномерно распределены по интервалу от 0 до 1. Подобная «равнораспределенность» встречается довольно часто. К несчастью, никто не знает, как доказать, что она распространяется на приведенную итеративную формулу, но сама по себе эта идея перспективна и, вполне возможно, со временем даст результат.

Для тоже существует похожая, но более сложная итеративная формула:

Если эта формула дает равномерное распределение, то нормально в двоичной системе.

Все вышеизложенное приводит нас наконец к очень странному открытию. Растянем интервал от 0 до 1 в 16 раз, так что yn = 16xn будут распределены на интервале от 0 до 16. Тогда целая часть последовательных y_n будет лежать в интервале от 0 до 15. Эксперимент показывает, что эти числа в точности соответствуют последовательным шестнадцатеричным знакам числа – 3. Этот факт проверен на компьютере для первых 10 млн знаков. Получается, по существу, что это дает нам формулу для n-го шестнадцатеричного знака . Чем дальше вы заходите, тем сложнее становятся вычисления, и на упомянутую проверку ушло 120 часов.

Есть веские причины ожидать, что это утверждение подтвердится, но пока оно недотягивает до строгого доказательства. Известно, что ошибок, если они есть, очень мало. Поскольку на первых 10 млн шагов их не обнаружено, вероятность того, что они встретятся позже, составляет около одной миллиардной. Однако это не доказательство – всего лишь отличная причина надеяться, что доказательство существует и его можно найти.

Последняя гипотеза, также основанная на убедительных данных, показывает, насколько необычна эта область математики. А именно: ничего подобного нельзя сделать с другой известной константой – числом e, основанием натуральных логарифмов, приблизительно равным 2,71828. Похоже, в числе есть что-то особенное в сравнении с числом e.

Математик, статистик и инженер…

…отправились на скачки. После забегов они встретились в баре. Инженер топил в пиве свои печали.

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

– Это все очень хорошо, – сказал статистик, – но вы забыли, что индивидуальное состояние изменчиво. Я провел статистический анализ их предыдущих забегов и нашел при помощи байесовских методов и оценки максимального правдоподобия, какой конь выиграет с наибольшей вероятностью.

– И он выиграл?

– Нет.

– Позвольте мне угостить вас всех, парни, – сказал математик, вытаскивая из кармана распухший бумажник. – У меня сегодня дела шли неплохо.

Остальные посмотрели на него с интересом. Вот человек, который понимает кое-что в лошадях. Математика с трудом уговорили поделиться секретом, и он неохотно начал:

– Рассмотрим бесконечное число одинаковых сферических коней…

Озера Вады

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

Две области на плоскости могут иметь общую границу; представьте себе, к примеру, англо-шотландскую или американо-канадскую границу. Три и больше областей могут иметь общую граничную точку: в американских «Четырех углах» сходятся штаты Аризона, Колорадо, Нью-Мексико и Юта.

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

Однако это возможно.

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

Поняли? По существу это то, что лежит на краю, но не внутри.

Для области в виде многоугольника, ограниченной набором отрезков прямых, граница состоит из этих отрезков, так что данное нами определение в этом случае вполне соответствует обычным представлениям. Можно доказать, что три и более многоугольных областей не могут иметь одну и ту же границу. Но для более сложных областей это неверно. В 1917 г. японский математик Кунидзё Ёнеяма опубликовал пример трех областей, имеющих одну и ту же границу. Он сказал, что идею таких областей предложил его учитель Такео Вада. Соответственно, сами области (или аналогичные им) были названы «озерами Вады».

Эти три области строятся шаг за шагом в ходе бесконечного процесса. Начинаем с трех квадратных областей.

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

Затем расширяем вторую область, добавляя к ней более узкую тропку, которая обходит вокруг всех трех областей, построенных до сих пор.

Продолжаем в том же духе, прокладывая еще более узкую тропинку от третьей области. Затем возвращаемся к первой, добавляем к ней еще более узкую тропинку и т. д.

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

Первоначально озера Вады были придуманы с целью показать, что топология плоскости не так проста, как можно вообразить. Много лет спустя выяснилось, что такие области возникают сами собой в численных методах решения алгебраических уравнений. К примеру, кубическое уравнение x = 1 имеет лишь одно действительное решение x = 1; кроме того, у него есть два комплексных решения где =. Комплексные числа можно представить как точки на плоскости, где число x + iy соответствует точке с координатами (x, y).

Стандартный метод нахождения численных аппроксимаций начинается со случайно выбранного комплексного числа; затем особым образом вычисляется второе число, а затем процесс повторяется, пока числа не сблизятся. Результат, полученный таким образом, близок к решению. К какому именно из трех решений он близок, зависит от того, где вы начинаете, и происходит это весьма хитроумным образом. Предположим, мы окрасим точки на комплексной плоскости в соответствии с тем, к какому решению они ведут: пусть, к примеру, это будет серый цвет, если решение x = 1, светло-серый, если решение и темно-серый, если решение Тогда точки, окрашенные в заданный оттенок серого, обозначат область, и можно доказать, что все три области имеют одну и ту же границу.

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

Последний лимерик Ферма[28]

И стар и млад в науке шаткой
Лет триста бились над загадкой.
Наконец-то решенье:
Прав Ферма, прочь сомненья…
Толстый том плюс к той записи краткой.

Ошибка Малфатти
Из мемуаров доктора Ватсапа

– Необычайно! – воскликнул я.

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

– Ответ кажется очевидным, но тем не менее, судя по всему, неверен! – воскликнул я.

– С очевидным это бывает, – заметил Сомс. – В смысле, оказывается неверным, – добавил он тоном пояснения.

– Слышали когда-нибудь о Джан-Франческо Малфатти? – спросил я.

– Убийца с топором?

– Нет, Сомс, это был Фрэнк Макавити по прозвищу Хакер.

– Ах. Мои извинения, Ватсап, вы, разумеется, правы. Я отвлекся. Мой образец следов Ratufa macroura разрушается. Большехвостая гигантская белка.

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

– Наивное, но, вероятно, верное предположение, – отозвался Сомс. – Хотя колонну, конечно, можно высечь и наискось.

– О-о, я не имел в виду… Но допустим, что его предположение было верным, поскольку вопрос всегда можно нужным образом переформулировать. Малфатти считал очевидным, что решение должно состоять из трех кругов, касающихся друг друга и двух внешних сторон треугольника.

– Понятно, в чем тут промах, – сказал Сомс тем раздражающе небрежным тоном, которым он часто пользуется, когда ему удается мгновенно схватить суть дела, не доступную большинству прочих смертных.

– А я, откровенно говоря, не понимаю, – сказал я. – Ведь если круг лежит внутри треугольника, не перекрывается другими кругами и не касается сторон и соседей так, как описано, то его можно увеличить.

– Верно, – отозвался Сомс. – Но это лишь доказывает достаточность, но не необходимость условий касания.

– Это я понимаю, Сомс. Но… как еще могли бы располагаться круги?

– Ну, касание может быть организовано и другими способами, конечно. К примеру, Ватсап: вы рассматривали простейший случай, с равносторонним внешним треугольником?

– Во-первых, – сказал Сомс, – есть вариант Малфатти, на рисунке слева. Но как насчет варианта справа? Здесь опять же ни один круг не может быть увеличен, но схема касаний иная. Маленькие круги касаются большого, но не касаются друг друга. Вместо этого есть большой круг, который касается всех трех сторон треугольника.

Я вгляделся в рисунки.

Он рассмеялся.

– Что показывает лишь, насколько легко наш глаз обмануть, Ватсап. Предположим, что стороны треугольника имеют единичную длину. Тогда вариант Малфатти имеет площадь 0,31567, но площадь второго варианта составляет 0,31997, то есть немного больше.

Бывают моменты, когда от эрудиции Сомса буквально перехватывает дыхание.

– Может быть, разница и невелика, Сомс, но вывод ясен. Малфатти ошибся.

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

Он сделал паузу, чтобы швырнуть раскрошившийся гипсовый отпечаток следов Ratufa macroura через всю комнату в камин.

– Ирония в том, – добавил он наконец, – что вариант Малфатти никогда не бывает лучшим. «Жадный» алгоритм – вписать в треугольник наибольший возможный круг, затем найти наибольший круг, который вписывается в оставшиеся промежутки, и напоследок проделать то же самое в третий раз – всегда лучше и всегда приводит к верному ответу.

Дополнительную информацию см. в главе «Загадки разгаданные».

Квадратные остатки

Полные квадраты заканчиваются на одну из цифр 0, 1, 4, 5, 6 или 9. Они не могут заканчиваться на 2, 3, 7 или 8. Более того, последняя цифра квадрата числа зависит только от последней цифры этого числа.

Если число заканчивается на 0, то его квадрат тоже заканчивается на 0.

Если число заканчивается на 1 или 9, то его квадрат заканчивается на 1.

Если число заканчивается на 2 или 8, то его квадрат заканчивается на 4.

Если число заканчивается на 5, то его квадрат тоже заканчивается на 5.

Если число заканчивается на 4 или 6, то его квадрат заканчивается на 6.

Если число заканчивается на 3 или 7, то его квадрат заканчивается на 9.

Специалисты по теории чисел предпочитают описывать подобные эффекты с помощью целых чисел по некоторому модулю. Если взять модуль 10, то достаточно рассмотреть только числа 0–9: возможные остатки от деления любого числа на 10. Их квадраты (по модулю 10) равны

0 1 4 9 6 5 6 9 4 1