Восемь этюдов о бесконечности. Математическое приключение - [2]
В этом разделе я представлю скромный набор математических задач из числа моих любимых, от довольно простых до весьма глубоких и даже предположительно неразрешимых (а если вы их все-таки решите, вас ждет премия). Я хочу познакомить вас, мой уважаемый читатель, хотя бы с немногими образцами интереснейших размышлений, которые вы можете найти в поразительном мире математики.
Великое маленькое исследование – открытая проблема
Много лет назад я прочитал удостоенную Пулитцеровской премии книгу Дугласа Р. Хофштадтера «Гёдель, Эшер, Бах». Сам автор называет ее «метафорической фугой о разумах и машинах в духе Льюиса Кэрролла». Она рассказывает о самых разнообразных предметах из царств математики, музыки, симметрии, искусственного интеллекта и логики и содержит множество математических загадок. Я хотел бы познакомить вас с одной из них.
Возьмем любое число – точнее, любое целое или натуральное число. Ахилл (он же Ахиллес – тот самый, у которого были проблемы с пяткой), также ставший одним из персонажей книги Хофштадтера, задумал число 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). Я не мог понять только одного: как так получилось, что никто до сих пор не сумел решить эту задачу.
Во всяком случае, так я думал…
По-видимому, существует веская причина, по которой эта задача все еще считается «открытой проблемой».
Хотя успеха я не добился, это меня не слишком расстроило. Я нахожу трудные вопросы очень привлекательными. Они заставляют размышлять. На самом деле я даже больше люблю задачи, которые не могу решить (или по меньшей мере не могу решить без труда), чем те, которые решаются в момент и без особых интеллектуальных усилий. Разумеется, это не значит, что я оказываюсь на вершине блаженства, когда не могу справиться с какой-нибудь проблемой – несомненно, решение непростой задачи, доставшееся ценой большого труда, доставляет гораздо больше удовольствия.
