Восемь этюдов о бесконечности. Математическое приключение

Хаим Шапира

Восемь этюдов о бесконечности. Математическое приключение

Haim Shapira

EIGHT LESSONS ON INFINITY

A Mathematical Adventure

© Haim Shapira, 2019

© Прокофьев Д. А., перевод на русский язык, 2021

© Издание на русском языке, оформление. ООО «Издательская группа «Азбука-Аттикус», 2021 КоЛибри®

⁂

Посвящается вам, Даниела, Таль и Инбаль

Предисловие

Если бы мне пришлось начать вновь свое обучение, то я последовал бы совету Платона и принялся бы сперва за математику[1].

Галилео Галилей

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

Это, разумеется, истинная правда. Никто не станет хвалиться, что никогда не читал книг, не видел ни одного произведения искусства, никогда – ни разу в жизни – не был растроган музыкой. Если провести опрос, я совершенно уверен, что не найдется ни одного образованного взрослого человека, никогда не слыхавшего о Шекспире, Рембрандте или Бахе. По всей вероятности, участники такого опроса знали бы и имена великих математиков Пифагора, Исаака Ньютона и Альберта Эйнштейна. Но многие ли слышали о Леонарде Эйлере, Сринивасе Рамануджане или Георге Канторе?

Возможно, в этот самый момент вы тоже спрашиваете себя: «Что? Кто это такие? Их имена ни о чем мне не говорят».

Это великие математики. Величайшие математики!

Я всерьез увлекаюсь музыкой, литературой и изобразительным искусством, но искренне считаю, что математические формулы Рамануджана – такое же чудо, как музыкальные построения Баха, а открытия Кантора, касающиеся бесконечности, кажутся мне не менее поразительными, чем произведения Шекспира.

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

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

В чем тут дело? Почему столь многие люди, какими бы образованными они ни были, чураются замысловатости и красоты, которые можно найти в мире чисел и их связях друг с другом?

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

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

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

2. Математические книги, написанные для математиков. В этой категории тоже есть множество превосходных работ, но прочесть (и понять) их могут только математики.

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

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

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

Комментарии к книге, ответы на вопросы и вопросы о вопросах можно присылать по адресу [e-mail]. Желаю вам увлекательного путешествия!

Разминка

Краткое введение в размышления

Размышления: разговор души с самой собой.

Платон

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

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

Великое маленькое исследование – открытая проблема

Много лет назад я прочитал удостоенную Пулитцеровской премии книгу Дугласа Р. Хофштадтера «Гёдель, Эшер, Бах». Сам автор называет ее «метафорической фугой о разумах и машинах в духе Льюиса Кэрролла». Она рассказывает о самых разнообразных предметах из царств математики, музыки, симметрии, искусственного интеллекта и логики и содержит множество математических загадок. Я хотел бы познакомить вас с одной из них.

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

Теперь сделаем вот что: если это число четное, разделим его на 2. Если оно нечетное, умножим его на 3 и прибавим 1. Будем повторять эту процедуру снова и снова, пока не получим (если получим) число 1. Посмотрим, как это работает:

Поскольку 15 – число нечетное, умножим его на 3 и прибавим 1.

15 × 3 + 1 дает 46.

46 – число четное: разделим его на 2 и получим 23. Поскольку это число нечетное, умножим его на 3 и прибавим 1.

23 × 3 + 1 = 70

Продолжим этот процесс:

70/2 = 35;

35 × 3 + 1 = 106;

106/2 = 53;

53 × 3 + 1 = 160;

160/2 = 80;

80/2 = 40;

40/2 = 20;

20/2 = 10;

10/2 = 5;

5 × 3 + 1 = 16;

16/2 = 8;

8/2 = 4;

4/2 = 2, и наконец 2/2 = 1.

Процесс дошел до конца.

Спрашивается, правда ли, что эта процедура рано или поздно приводит к 1 для любого исходного числа?

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

Хофштадтер предложил Ахиллесу попробовать число 27. Вы можете последовать его примеру. Я дам вам пару минут… или, может быть, часов.

Сдаетесь? Если начать с 27, кажется, что процесс все продолжается и продолжается и дает нескончаемую цепочку вычислений. В какой-то момент вы можете решить, что она и впрямь никогда не закончится. На самом деле требуемое в этом случае число шагов равно 111.

В своей книге Хофштадтер предостерегает Ахиллеса относительно попыток найти ответ на заданный выше вопрос (действительно ли из любого числа можно получить 1?) и рассказывает, что эта задача известна под названием «гипотеза Коллатца» (напомню на всякий случай, что «гипотеза» значит «догадка» или, точнее, «предложение возможной новой теоремы, которую еще нужно доказать»). Она утверждает, что, с какого бы числа мы ни начали описанный выше процесс, он рано или поздно приведет к 1. Эта гипотеза названа в честь немецкого математика Лотара Коллатца (1910–1990), впервые описавшего ее в 1937 г. Тем не менее у нее есть и другие названия: в частности, ее называют гипотезой Улама (по имени польского математика Станислава Улама) или задачей Какутани (по имени японского математика Сидзуо Какутани). Иногда говорят просто о гипотезе 3n + 1, что вполне логично.

Когда я впервые узнал о гипотезе 3n + 1, я был слишком молод, чтобы осознать, насколько сложна и глубока эта задача. Я предполагал, что мне понадобится всего несколько дней, чтобы придумать критерий, определяющий, для каких чисел эта процедура дает на последнем шаге 1. Мне казалось даже, что я сумею доказать истинность гипотезы – что любое число в конце концов приводит к 1. Возможно, занимаясь этим, я даже смогу открыть распределение числа шагов, необходимого для каждого конкретного числа (например, когда мы подставили число 15, количество шагов оказалось равным 17). Я не мог понять только одного: как так получилось, что никто до сих пор не сумел решить эту задачу.

Во всяком случае, так я думал…

По-видимому, существует веская причина, по которой эта задача все еще считается «открытой проблемой».

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

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

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

Если рассмотреть достаточное количество примеров задачи Коллатца, можно заметить одно обстоятельство: последние числа, появляющиеся в этом процессе представляют собой последовательно уменьшающиеся степени 2. Например, если начать с 15, то последние пять чисел последовательности – это 16, 8, 4, 2 и, наконец, 1.

Это явление можно сформулировать в виде правила, сказав, что если процесс доходит до числа вида 2n, то он гарантированно сойдется к 1 в точности через n делений на 2. Это наблюдение позволяет перефразировать гипотезу 3n + 1 следующим образом: приходит ли на каком-то этапе процесс, начатый с любого произвольного числа, к степени 2?

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

Венгерский математик Пал Эрдёш (1913–1996) любил предлагать денежные призы за успешное решение интересовавших его открытых математических проблем. Призы эти начинались с 25 долларов, а доказательство гипотезы Коллатца стоило в его прейскуранте целых 500 долларов – то есть попадало в категорию весьма дорогих задач, хотя сам Эрдёш говорил, что мир математики, возможно, не готов к таким сложным и запутанным задачам, как гипотеза 3n + 1. Эрдёша уже нет с нами, но можно не беспокоиться: выплату призов взял на себя его коллега Рон Грэм. Если вам удастся решить эту задачу, вы можете получить приз одним из двух способов: либо в виде чека, который сам Эрдёш выписал перед смертью (его можно только вставить в рамку: срок действия этого чека давно истек), либо реальными деньгами (выбор между грехом гордыни и грехом сребролюбия).

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

Мудрость – это знать, что не знаешь того, чего не знаешь, и знаешь то, что знаешь. Глупость – это думать, что знаешь то, чего не знаешь, или не знаешь того, что знаешь.

Китайская пословица

ЧИСЛО ЭРДЁША

Пал Эрдёш был математиком исключительно плодовитым. Его превосходную биографию можно найти в книге Пола Хофмана «Человек, который любил только числа» (The Man Who Loved Only Numbers, 1998). Он написал более 1400 научных статей. Эрдёш был страстным поборником командной работы и сотрудничества, и за годы его научной деятельности вместе с ним над его статьями работали целых 511 математиков. Любому математику, который когда-либо писал статью в соавторстве с самим Эрдёшем, присваивается престижное число Эрдёша, равное 1. Те, кто сотрудничал с его соавторами, но не с самим Эрдёшем, получают число Эрдёша, равное 2. Аналогичным образом по мере все большего удаления присваиваются числа Эрдёша, равные 3, 4 и так далее. Общее правило таково: если вы сотрудничаете с человеком, наименьшее число Эрдёша которого равно k, то ваше число Эрдёша равно k + 1. Сам Эрдёш был единственным человеком с числом Эрдёша, равным 0. На противоположном конце спектра находятся те, кто никогда не писал статей с Эрдёшем и никогда не писал статей ни с кем из имеющих конечное число Эрдёша: их число Эрдёша равно бесконечности (∞). «Бесконечное число Эрдёша» звучит весьма престижно – может быть, даже престижнее, чем, скажем, «число Эрдёша 7», – но многие из вас, наверное, удивятся, узнав, что ваше собственное число Эрдёша (как и у большей части человечества) как раз и равно бесконечности. Я сам не пишу статей, но однажды принимал участие в совместной работе над статьей с математиком, число Эрдёша которого равнялось 3, так что я, даже не стремясь к тому, стал гордым обладателем числа Эрдёша, равного 4.

Это напоминает популярную салонную игру «Шесть шагов до Кевина Бейкона». Знаменитый голливудский актер Кевин Бейкон заявил однажды, что все до единого актеры в Голливуде либо снимались с ним вместе (Бейкон‐1), либо снимались с кем-нибудь, с кем снимался и он (Бейкон‐2), либо с кем-нибудь, кто снимался с кем-нибудь, кто… (Бейкон‐3, 4 и т. д.). В целом, утверждал он, «число Бейкона» почти всех актеров и актрис Голливуда не превышает 6. Например, у Элвиса Пресли оно равно 2. Связь между ними вы можете восстановить самостоятельно{1}. Кажется, что мир действительно тесен: в нем есть люди, у которых есть и число Эрдёша, и число Бейкона. Например, у Рона Грэма число Эрдёша равно 1, а число Бейкона – 2. А у знаменитой израильской актрисы Натали Портман число Эрдёша равно 5, а число Бейкона – 1 (этого вы не ожидали, правда?).

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

Загадка шахматной доски

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

Рассмотрим сетку размером 8 × 8 ячеек.

Очевидно, всю эту сетку легко покрыть 32 костяшками домино размером 1 × 2 ячейки. А теперь уберем две клетки, расположенные в противоположных углах.

Можно ли покрыть получившуюся сетку всего 31 костяшкой?

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

Но правильный ответ на этот вопрос – «нет». Что бы мы ни делали, 31 костяшка домино не может покрыть сетку с удаленными противоположными угловыми клетками.

Почему это так, немедленно становится ясно, если взять вместо такой незакрашенной сетки черно-белую шахматную доску.

Как видно на рисунке, каждая костяшка домино может закрыть одну черную клетку и одну белую; поэтому 31 костяшка может закрыть в точности 31 белую клетку и 31 черную. Поскольку две клетки, удаленные с доски, одного и того же цвета – белые, – в обрезанной доске осталось 30 белых клеток и 32 черные. Много лет назад, когда я учился на математическом факультете в Тель-Авиве, я вел для «интересующейся наукой молодежи» курс под названием «Парадоксы, загадки и числа». Я давал эту задачу молодым слушателям своего курса. Каждый раз происходила одна любопытная вещь. Многие ученики решительно не соглашались с доказательством, которое показывает, что 31 костяшка домино не может покрыть доску с удаленными противоположными угловыми клетками. Интересно отметить, что в их число входили и ученики, казалось бы, вполне понимавшие объяснение этого доказательства; тем не менее они упорно раскладывали костяшки домино так и эдак, стараясь покрыть эту самую доску с обрезанными углами. Я даже не пытался убедить их в бессмысленности этого занятия – каждый должен учиться на собственных ошибках.

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

Абба Эвен

Головоломка

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