Ханойские башни
Согласно легенде, в одном из храмов индийского города Бенареса установлена бронзовая плита с тремя алмазными стержнями. При сотворении мира верховный индуистский бог Брахма поместил на первый стержень 64 диска из чистого золота, в порядке уменьшения их размеров, и велел монахам переместить их на третий стержень, запретив при этом за один раз переносить более одного диска и помещать больший диск на меньший. С тех пор монахи день и ночь, сменяя друг друга, трудятся над этой задачей. Как только они закончат, храм рассыплется в прах и завершится жизнь Брахмы. (Примерный понятный нам аналог— «конец света».) Затем родится новый Брахма и все циклически повторится с начала.
Согласитесь: красивая история. . . блеск золота и алмазов, неожиданная развязка. . . А придумал ее французский математик Эдуард Люка. Как сказал однажды Карл Вейерштрасс, «нельзя быть настоящим математиком, не будучи немного поэтом».
Легенда Люка была своего рода рекламным трюком для его изящной, но более прозаичной головоломки, выполненной из дерева и состоящей из восьми дисков. В 1883 г. ее продавали в Европе как забавную игрушку: первоначально — под названием «Профессор Клаус (Claus)», но вскоре обнаружилось, что таинственный профессор — не более чем анаграмма фамилии изобретателя игры — профессора Люка (Lucas). Позже вместе с названием головоломки («Башни Брахмы»,«Головоломка о Конце света», «Пагода-головоломка») неоднократно менялось и место действия легенды (Индия, Бенарес;Вьетнам, Ханой; Китай, Тибет). А сейчас головоломка более известна как Ханойские башни (те самые).
Франсуа Эдуард Анатоль Люка (1842-1891)
Скажем несколько слов и об изобретателе нестареющих «башен». Франсуа Эдуард Анатоль Люка (1842–1891) родился в Амьене, во Франции. По окончании учебы работал в Парижской обсерватории. В качестве артиллерийского офицера участвовал во франко-прусской войне(1870–1871). После поражения французов стал профессором математики в Париже. Важнейшие его работы относятся к теории чисел и неопределенному анализу.
Ханойские башни — это лишь одна из многих идей, с которыми связывают имя Люка, — и некоторые из этих идей имеют не менее успешную судьбу. Например, Люка предложил тест для определения, простым или составным является число Мерсенна Mp = 2^p ? 1. Применяя свой метод, в 1876 г. Люка установил, что M127 = 2^127 ? 1 — простое число, и это огромное 39-значное число, по всей видимости, останется наибольшим простым числом, когда-либо найденным«с карандашом в руках». (Пять новых простых чисел были обнаружены только в 1952 г., но уже с помощью компьютера. Последний рекорд был поставлен в 2006 г. тоже благодаря тесту Люка. Число
M32582 657 = 2^32 582 657 ? 1
является 44-м простым числом Мерсенна и содержит 9808358 цифр. В его поиске принимали участие тысячи людей по всему миру в рамках масштабного проекта распределенных вычислений — Great Internet Mersenne Prime Search(GIMPS): любой желающий мог скачать себе программу, которая периодически связывалась с основным сервером, получала от него задание, выполняла и передавала результаты обратно. Кстати, этот проект продолжает свою работу, а за нахождение простого числа из более чем 10^7 цифр назначена награда в 100000 долларов. Но важно другое: исследования простых чисел, в том числе и исследования Люка, казавшиеся ранее практически бесполезными, нашли широкое применение в криптографии.
Далее, именно Люка привлек внимание математиков (и не только!) к замечательной числовой последовательности:
1, 1, 2, 3, 5, 8, 13, 21, 35, . . . ,
назвал ее «числами Фибоначчи» и открыл многие их свойства. (Это такие числа, у которых каждый член последовательности равен сумме двух предыдущих. Они обладают множеством закономерностей и возникают в самых неожиданных ситуациях в природе, науке и искусстве. Числам Фибоначчи посвящены многие книги, а в 1963 г. математики даже организовали «Фибоначчи-Ассоциацию».)
Еще одна перспективная идея Люка — уже в XIX столетии, задолго до возникновения компьютеров, он отмечал технические преимущества двоичной системы счисления. Тем самым он предвосхитил Джона фон Неймана, который отдал решительное предпочтение двоичной системе счисления при реализации компьютеров («принципы Джона фон Неймана», 1945 г.).
Эдуард Люка был не только профессиональным математиком, но и талантливым изобретателем игр и головоломок. Его четырехтомный труд «Математические развлечения» (1882–1894) наряду с книгами Сэма Ллойда, Генри Дьюдени, Джона Конуэя, Мартина Гарднера, Раймонда Смаллиана и др. стал классикой жанра занимательной математики.
Вот уже более ста лет Ханойские башни Люка — предмет интереса математиков и программистов. И, как ни странно, они в них до сих пор не наигрались! Многим из нас известна лишь рекурсивная программа решения, буквально «в три строчки». Казалось бы, о чем тут еще рассказывать? А между тем — это только верхушка айсберга! Задача о Ханойских башнях удивительно богата на математические закономерности и программистские решения, допускает многочисленные, не менее интересные вариации. Один только список «околобашенных» статей насчитывает примерно 400 наименований, не считая «дежурных» упоминаний о них почти в каждом учебнике программирования или сборнике головоломок. Проводятся международные семинары, посвященные исключительно Ханойским башням и смежным с ними вопросам. И более того, один из вариантов «классических» башен (а именно головоломка с четырьмя стержнями) еще и сегодня остается нерешенной задачей. Изящество и глубина этой «игрушки» стали «виной» ее известности и долгожительства. Хотя решать, конечно, вам. . .
