Читать книгу Восемь этюдов о бесконечности. Математическое приключение - Хаим Шапира - Страница 5

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

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

Это явление можно сформулировать в виде правила, сказав, что если процесс доходит до числа вида 2ⁿ, то он гарантированно сойдется к 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 долларов, гораздо более простых, чем возня с этой задачей.