ГНОМОН. От фараонов до фракталов - Газале М.
ISBN 5-93972-171-0
Скачать (прямая ссылка):
причиной феноменального успеха телеграфа Бодо. Преобразование из двоичного кода в код Грея осуществляется простой заменой в двоичном числе
Ш-АДИЧЕСКИЕ ЧИСЛА
39
I
s - ч ?*ч ^ -«в
1111
1101
0110
Рис. 1.7. Багеиодье. Из статьи Мартина Гарднера «Любопытные свойства кода Грея и его применение в решении головоломок» (Martin Gardner, «The Curious Properties of the Gray Code and How It Can Be Used to Solve Puzzles», Scientific American (August 1972), p. 66).
бита ранга i на сумму битов ранга i и i + 1 по модулю 2. Преобразование из кода Грея в двоичный код ничуть не сложнее: бит ранга i в числе Грея следует заменить на сумму этого бита и всех битов слева от него по модулю 2.
Рассмотрим теперь две знаменитые игрушки: «багенодъё»6, известная в Англии под названием «китайские кольца», и «ханойскую башню», изобретенную французским математиком Эдуаром Люка, плодовитым автором как всевозможных математических развлечений, так и серьезных исследований. Обе эти игры можно проанализировать с учетом кода Грея.
Головоломка из проволоки и колец, называемая багенодье, изображена на рис. 1.7. Цель игры заключается в снятии цепочки колец с проволочной петли. Структура головоломки такова, что кольцо можно снять только в том случае, если его ближайший правый (как показано на рисунке) сосед все еще находится на петле, а все остальные следующие за ним кольца уже сняты. Согласно Мартину Гарднеру эту головоломку рассматривал еще Джироламо Кардано в своем труде «De Subtilitate Rerum»7 (1550), а также Джон Валлис в своей «Алгебре» (1693). В 1872 году Луи Гро в «Theorie du Baguenodier»8
6Baguenaudier — французское слово, произведенное от названия растения, плод которого наполнен воздухом и с громким шумом лопается, будучи сдавлен между пальцами. Соответствующий глагол имеет смысл «праздно, бесцельно бродить, слоняться».
7«О тонкости вещей» (лат.) — Прим. перев.
8«Теория багенодье» (фр.) — Прим. перев.
40
Глава I
использовал для решения головоломки двоичную систему счисления. На рис. 1.7 приведена таблица, описывающая решение головоломки, в которой число колец для простоты сокращено до четырех; 1 означает кольцо на петле, а 0 — уже снятое кольцо. Процесс начинается с конфигурации колец 1111, что соответствует десятичному числу 10, последующие конфигурации составляются так, чтобы соответствовать числам 9, 8, 7 и т. д., пока все кольца не окажутся снятыми с петли (конфигурация 0000).
Ханойская башня была изобретена Эдуаром Люка и продана как игрушка в 1883 году (рис. 1.8). Цель игры заключается в переносе башни с одного колышка на другой, перемещая по одному диску за ход, при этом запрещается класть диск на диск меньшего диаметра.
Рис. 1.8. Ханойская башня.
Д. У. Кроу (Университет Британской Колумбии) обнаружил, что решение n-дисковой «ханойской» задачи можно найти с помощью гамильтонова пути на п-мерном диадическом гиперкубе. Для того чтобы понять, как это делается, рассмотрим четырехдисковый случай; на цветной вклейке 19 буквами А, В, С и D обозначены оси, образующие измерения гиперкуба с вклейки 17. Если начальная вершина имеет индекс 0000, конечная — индекс 1000, а гамильтонов путь мы сведем к простому перечислению осей, вдоль которых будет происходить наша прогулка, не учитывая при этом направления пути относительно этих осей, то результирующий путь можно записать как ABACABADABACABA. Обозначим четыре диска ханойской башни через А, В, С и D, начиная сверху. Головоломка решается посредством перемещения дисков в соответствии с только что описанной пятнадцатибуквенной последовательностью, соблюдая, разумеется, правило «неположения» большего диска на меньший.
Таким образом, для решения необходимо 2п — 1 шагов; из кажущейся простоты этого решения родилась легенда о «британской башне», составленной из 64 золотых дисков. Дерзнувшие переместить башню на другой колышек, следуя правилам игры, должно быть, и не подозревали о том,
Ш-АДИЧЕСКИЕ ЧИСЛА
41
что для завершения работы им потребуется несколько миллионов лет. Эта легенда напоминает о другой — об одном арабском математике, который в награду за какую-то услугу попросил у халифа некоторое количество рисовых зерен, для определения которого следовало положить одно зернышко на одну клетку шахматной доски, два на другую, четыре на третью и т.д., с каждой клеткой удваивая количество зерен.
Степени триадических чисел
Геометрическая фигура, соответствующая диадическому числу (п + 1), одномерна. В случае триадического (п2 + п + 1) мы имеем дело уже с двухмерной фигурой, которую вы видите на цветной вклейке 20; здесь также показан один из вариантов индексирования вершин получаемого графа. На вклейке 21а обнаруживается наличие у триадического гиперкуба шести треугольных и шести параллелепипедных граней, а на вклейке 2lb показано, как можно построить такую фигуру на поверхности тора. Кроме того, приведена пара дополняющих друг друга гамильтоновых путей. На вклейке 22Ь изображен шестимерный триадический гиперкуб, соответствующий выражению
