Васильев Н. Б.

‍,

Гутенмахер В. Л.

Кривые драконаВасильев Н. Б., Гутенмахер В. Л. Кривые дракона // Квант. — 1970. — № 2. — С. 36‍—‍46.‍‍

Что такое кривая и ломаная дракона

Возьмите длинную полоску бумаги, сложите её пополам и ещё раз пополам. Сложенную полоску положите ребром на стол и разверните так, чтобы угол при каждом сгибе был равен $90^\circ$‍‍ (рис. 1). Если смотреть сверху, то видна ломаная линия, изображённая на рис. 2, а или б.

При трёх складываниях полоски пополам уже получаются существенно различные ломаные (рис. 2, в или г) в зависимости от того, как складывается полоска. Если полоску складывать четыре раза и больше, а затем разворачивать её сгибы до прямых углов, можно получить много различных ломаных. На рис. 3 показана одна из ломаных, получающихся при пяти складываниях пополам.

Практически вам не удастся сложить полоску бумаги больше семи раз — ведь уже при восьмом складывании получилось бы $2^8=256$‍‍ слоёв! Однако мы скоро научимся рисовать довольно длинные такие ломаные, обходясь без полоски. На странице 38 (внизу) уже нарисована одна из ломаных, которая получилась бы, если бы мы складывали полоску 12 раз. Она состоит из $2^{12}=4096$‍‍ звеньев.

Легко убедиться в том, что если складывать полоску более трёх раз, то после разворачивания некоторые её углы обязательно будут «касаться» друг друга (рис. 2, г и рис. 3). Из-за многочисленных таких касаний на длинных ломаных местами получается сетка. Чтобы разобраться, как идёт ломаная, можно закруглить у неё углы (так, как показано на рис. 3 цветной линией). Если проделать это для ломаной, изображённой под рисунком 3, то получится замысловатая линия, нарисованная на предыдущей странице. Этот рисунок и подсказал американскому физику Джону Хейвею (Heighway) название «кривые дракона». Тот, кто когда-нибудь видел дракона, мог бы подтвердить, что он выглядит именно так.

Такая ломаная («главная ломаная дракона») получается, если начиная с отрезка, каждый раз поворачивать предыдущую ломаную в одну и ту же сторону. (Это соответствует способу складывания пополам, показанному на рис. 2, а, в; здесь полоска каждый раз загибается «справа вверх налево».) На рис. 3 изображено начало этой ломаной (32 звена), на этом рисунке — 4096 звеньев. Если ломаную продолжать таким же образом дальше, то она будет медленно обходить вокруг своего начала, делая один полный оборот за 8 «удвоений». Красные точки лежат на логарифмической спирали (для тех, кто знаком с полярной системой координат, мы можем написать её уравнение: $\varphi=\log_ar$‍,‍ где $r$‍,‍ $\varphi$‍‍ — полярные координаты; $a=2^{\textstyle\frac2\pi}$‍).‍

Как рисовать длинные ломаные дракона?

Мы будем называть любую ломаную, полученную из бумажки, сложенной пополам $n$‍‍ раз, разворачиванием сгибов до $90^\circ$‍,‍ ломаной дракона ранга $n$‍.‍ Выясним, как устроены ломаные дракона и как их рисовать для достаточно больших $n$‍.‍

Первый способ

Ломаная дракона ранга $n$‍‍ состоит из $2^n$‍‍ звеньев и соответственно имеет $2^n-1$‍‍ вершин (не считая концов). Taким образом, у неё есть средняя вершина (при $n\gt0$‍),‍ поскольку число вершин нечётно. На рис. 2 и 3 у каждой ломаной средняя вершина отмечена зелёным кружочком. Можно подметить, что каждая из этих ломаных состоит из двух одинаковых кусков, получающихся друг из друга поворотом на $90^\circ$‍.‍ Оказывается, это общая закономерность.

Теорема 1. Если продолжить любую ломаную дракона ранга $n$‍‍ с концом в точке $O$‍‍ точно такой же ломаной, полученной из данной поворотом на $90^\circ$‍‍ вокруг точки $O$‍,‍ то получится ломаная дракона ранга $n+1$‍,‍ и обратно, любая ломаная дракона ранга $n+1$‍‍ получается из некоторой ломаной ранга $n$‍‍ этим способом.

В самом деле, допустим, мы хотим сложить полоску $n+1$‍‍ раз пополам. Сложим её сначала один раз пополам. Тогда две её половинки совпадут и при дальнейших складываниях будут сгибаться пополам совершенно одинаково (рис. 4). Теперь развернём на $90^\circ$‍‍ последние $n$‍‍ сгибов полоски. Получим две совпадающие ломаные дракона ранга $n$‍;‍ остаётся развести их на $90^\circ$‍‍ — и мы получим ломаную дракона ранга $n+1$‍‍ (рис. 5). Подумайте, как из этих соображений вывести оба утверждения теоремы 1.

Пользуясь теоремой 1, легко рисовать длинные ломаные дракона.

Поскольку любая ломаная дракона идёт по линиям квадратной сетки, её удобно рисовать на клетчатой бумаге.

Возьмём любую короткую ломаную дракона (например, просто отрезок). Условимся, что одна из её крайних точек — начало, а другая — конец. Продолжим её такой же ломаной, повёрнутой относительно её конца на $90^\circ$‍‍ по (или против) часовой стрелке. Полученную новую ломаную таким же способом продолжаем от конца; так проделываем столько раз, сколько захочется и сколько сможем. Это автоматически и быстро можно делать, если под рукой есть калька или, ещё лучше, слегка прозрачная клетчатая бумага. (Подумайте, как!)

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

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

Из теоремы 1 сразу не видно, как доказать, что ломаные дракона не проходят дважды по одному и тому же отрезку — наоборот, чем более длинные и запутанные ломаные или кривые рисуешь, тем более удивительно, как удачно их «выступы» и «впадины» подходят друг к другу (см. кривую дракона «паровоз» на стр. 43).

Однако нетрудно это доказать‍, используя другую теорему об «удвоении» ломаных дракона, которая, кстати, даёт ещё один способ рисовать длинные ломаные.

Второй способ

На рис. 6 вершины чёрных ломаных дракона соединены красными отрезками через одну. Мы видим, что красные отрезки снова составляют ломаные дракона. Оказывается, это тоже общая закономерность.

Чтобы точно её сформулировать, заметим ещё, что каждый красный отрезок является гипотенузой равнобедренного прямоугольного треугольника, катеты которого — звенья исходной ломаной (на рисунке треугольники слегка закрашены), причём каждые два соседних таких треугольника получаются друг из друга поворотом на $90^\circ$‍‍ вокруг их общей вершины; другими словами, если идти вдоль красной ломаной дракона, то эти треугольники будут встречаться поочерёдно то справа, то слева.

Теорема 2. Если на каждом звене ломаной дракона ранга $n$‍,‍ как на гипотенузе, построить прямоугольный равнобедренный треугольник, причём так, чтобы для двух соседних звеньев эти треугольники получались один из другого поворотом на $90^\circ$‍‍ относительно общей вершины, то катеты построенных треугольников составляют ломаную дракона ранга $n+1$‍.‍ И наоборот, каждую ломаную ранга $n+1$‍‍ можно получить этим способом из некоторой ломаной ранга $n$‍.‍

С помощью теоремы 2 из каждой ломаной дракона ранга $n$‍‍ можно получить две разные ломаные ранга $n+1$‍:‍ всё зависит от того, по какую сторону от первого звена достроить треугольник.

Обратите внимание на то, что когда мы переходим от ломаной ранга $n$‍‍ к ломаной ранга $n+1$‍‍ по теореме 1, то ломаная получается вдвое длиннее, а длина каждого звена не меняется; если же мы пользуемся для «удвоения» теоремой 2, то длина ломаной увеличивается в $\sqrt2$‍‍ раз, а длина звена уменьшается в у $\sqrt2$‍‍ раз.

Потренируйтесь теперь в рисовании ломаных дракона с помощью теоремы 2.

Слова

Свойство, о котором идёт речь в теореме 2, можно объяснить совсем просто, если посмотреть на ломаные дракона (или, если угодно, на способы складывания бумажки) несколько с иной точки зрения.

Пусть по ломаной дракона ползёт черепаха (рис. 9). Каждый раз, когда она доползает до вершины, ей приходится поворачивать на $90^\circ$‍‍ налево или направо. С точки зрения черепахи, её путь будет определяться последовательностью поворотов. Например, для ломаной на рис. 2, а (начало в красной точке) эта последовательность будет выглядеть так: налево, налево, направо.

Будем поворот направо обозначать буквой $R$‍,‍ поворот налево — буквой $L$‍‍‍. Тогда вся ломаная запишется таким «словом»: $$ LLR $$ («словом» во многих разделах математики и логики называют просто любую последовательность букв). Точно так же можно записать словом из букв $L$‍‍ и $R$‍‍ любую ломаную дракона.

Эта кривая получается, если, начиная с отрезка, повторять процесс «удвоения» 12 раз, причём чередовать повороты по и против часовой стрелки. Чтобы лучше показать, как идёт эта кривая, мы поворачиваем каждый раз не на $90^\circ$‍,‍ а на $95^\circ$‍‍ (чёрная линия); если уменьшить углы до $90^\circ$‍,‍ то получится кривая дракона, которая изображена на том же рисунке цветной линией; она заполняет равномерным узором равнобедренный прямоугольный треугольник.

Эта кривая дракона ранга 12 имеет специальное название «Папа, мама и сын». Найдите её середину. Можете ли вы себе представить, что кривая разбивается этой точкой на два совершенно одинаковых куска, получаюшихся друг из друга поворотом на $90^\circ$‍?‍ Чтобы поверить в это, вам придётся вероятно, пройтись по кривой цветным карандашом от начала до середины.

Здесь одна из двух половин кривой (она называется «паровоз») нарисована на цветном фоне, чтобы показать, как эти две кривые «сцепляются» между собой. Одна половина после поворота её вокруг средней точки на $90^\circ$‍,‍ совпадёт с другой.

Чтобы получить из ломаной а ломаную б (рис. 2), нужно бумажку сложить ещё один раз «налево» (см. рис. 2, б и 10). При этом между каждыми двумя вершинами ломаной а возникнет ещё по одному повороту, причём на рис. 10 хорошо видно, что эти новые повороты будут чередоваться; таким образом, получим $$ \colsep{0pt}{\begin{array}{ccccccc} &L&&L&&R&\\ \color{#a0a}L&&\color{#a0a}R&&\color{#a0a}L&&\color{#a0a}R\end{array}}\to LLRLLRR, $$ т. е. слово, являющееся записью ломаной б. При ещё одном сгибе налево мы получили бы ломаную, характеризуемую словом $$ \colsep{0pt}{\begin{array}{ccccccccccccccc} &L&&L&&R&&L&&L&&R&&R&\\ \color{#a0a}L&&\color{#a0a}R&&\color{#a0a}L&&\color{#a0a}R&&\color{#a0a}L&& \color{#a0a}R&&\color{#a0a}L&&\color{#a0a}R\end{array}}\to LLRLLRRLLLRRLRR. $$ Начертите эту ломаную. Это — главная ломаная дракона ранга 4. Если хотите, закруглите у неё углы, как это предложил Хейвей.

Если вы проделаете над последним полученным словом ту же операцию ещё раз (снова начав последовательность чередующихся букв с $L$‍),‍ то получите слово из 31 буквы — запись главной ломаной дракона ранга 5, изображённой на рис. 3.

Разумеется, последовательность чередующихся букв можно начинать не с $L$‍,‍ а с $R$‍‍ — при этом получатся другие ломаные.

Легко видеть, что наш способ изготовления слова для ломаной ранга $n+1$‍‍ из слова для ломаной ранга $n$‍‍ в точности соответствует геометрическому способу удвоения, о котором идёт речь в теореме 2 (новым буквам соответствуют достраиваемые треугольники). Вообще всю «теорию» ломаных дракона можно было бы строить не геометрически — с помощью поворотов, достраивания треугольников и т. п., а «алгебраически» — с помощью операций над словами из двух букв $L$‍‍ и $R$‍,‍ «записями» ломаных дракона‍.

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

Задачи

1. Какой длины надо взять полоску, чтобы, сложив её пополам 30 раз, получить расстояние между соседними сгибами равным 1 см? Больше или меньше расстояния от Земли до Луны?
2. Как изменится ломаная дракона, если полоску бумаги положить на стол другим ребром? Как изменится при этом слово, записывающее ломаную?
3. 1. Сколько существует различных (не подобных друг другу) ломаных дракона ранга 4? Нарисуйте их все. Напишите соответствующие им слова из букв $L$‍‍ и $R$‍.‍
   2. Сколько существует различных ломаных ранга $n$‍?‍
4. Допустим, что черепаха проползла по ломаной дракона и прочла слово из букв $L$‍‍ и $R$‍.‍ Какое слово она прочтёт, если проползёт по этой ломаной в обратном направлении?

5. Пусть $s$‍‍ — некоторое слово из букв $L$‍‍ и $R$‍.‍ Обозначим через $\overline{s}$‍‍ слово, которое получится из $s$‍,‍ если переставить в нём буквы в обратном порядке и потом поменять $L$‍‍ на $R$‍‍ и $R$‍‍ на $L$‍.‍ (Например, если $s=LLR$‍,‍ то $\overline{s}=LRR$‍).‍

   Пусть $s$‍‍ и $t$‍‍ — некоторые слова из букв $L$‍‍ и $R$‍.‍ Будем обозначать через $st$‍‍ слово, получающееся, если слова $s$‍‍ и $t$‍‍ написать рядом. (Например, если $s=LLR$‍,‍ $t=RL$‍,‍ то $st=LLRRL$‍.)‍

   Докажите, что:

   1. Для любых слов $s$‍‍ и $t$‍‍ $$ \overline{st}=\overline{t}\,\overline{s\vphantom{t}}. $$
   2. Если $s_{n+1}$‍‍ — слово, соответствующее ломаной дракона ранга $n+1$‍,‍ то $$ s_{n+1}=s_nx\overline{s_n}, $$ где $s_n$‍‍ — некоторое слово, соответствующее ломаной дракона ранга $n$‍,‍ а $x$‍‍ — слово, состоящее из одной буквы.
   3. Если $s_n$‍‍ — слово, соответствующее ломаной дракона, то $s_n$‍‍ отличается от $\overline{s_n}$‍‍ только одной средней буквой.
   4. Слово, записывающее ломаную дракона ранга $n$‍,‍ можно и притом единственным образом построить, если задать произвольно $n$‍‍ букв, которые должны стоять в этом слове на местах с номерами $2^k$‍,‍ где $k=0$‍,‍ 1, 2, $\ldots$‍,‍ $n-1$‍‍ (т. е. на первом, втором, четвёртом, восьмом, $\ldots$‍,‍ $2^{n-1}$‍‍-м местах); после этого, чтобы найти, какая буква стоит на $m$‍‍-м месте, нужно представить $m$‍‍ в виде $m=2^k(2l+1)$‍,‍ где $k$‍‍ и $l$‍‍ целые; если $l$‍‍ чётно, то на $m$‍‍-м месте стоит та же буква, что и на $2^k$‍‍-м, если $l$‍‍ нечётно — противоположная.
   5. Два слова $s_n'$‍‍ и $s_n''$‍‍ задают одинаковые по форме (подобные) ломаные дракона в том и только в том случае, если после вычёркивания средней буквы эти слова либо совпадают, либо одно получается из другого заменой $L$‍‍ на $R$‍‍ и $R$‍‍ на $L$‍.‍ (Например, слова $LLRLLRR$‍,‍ $LLRRLRR$‍,‍ $RRLRRLL$‍,‍ $RRLLRLL$‍‍ задают одинаковые ломаные.)

6. Пусть мы имеем ломаную дракона ранга $n$‍.‍ Из неё можно получить две ломаные дракона ранга $n+1$‍,‍ пользуясь либо теоремой 1 (принимая за точку $O$‍‍ тот или другой конец ломаной), либо теоремой 2 (достраивая треугольники в ту или другую сторону). Будут ли в обоих случаях получаться те же самые две ломаные дракона ранга $n+1$‍‍ или, вообще говоря, другие? Как получать их слова́ из сло́ва данной ломаной ранга $n$‍?‍
7. На плоскости даны две точки $A$‍‍ и $B$‍.‍ Начертим квадрат с центром в середине отрезка $AB$‍,‍ одна из сторон которого равна $2AB$‍‍ и параллельна отрезку $AB$‍.‍ Докажите, что любая ломаная дракона с концами в точках $A$‍‍ и $B$‍‍ лежит внутри этого квадрата. Докажите, что для любой точки $M$‍‍ внутри этого квадрата и любого положительного числа $\varepsilon$‍‍ можно найти такую ломаную дракона с концами $A$‍‍ и $B$‍,‍ которая проходит от точки $M$‍‍ на расстоянии меньше $\varepsilon$‍‍ (говоря математическим языком, «объединение всех ломаных дракона с концами в точках $A$‍‍ и $B$‍‍ всюду плотно в этом квадрате»).
8. Пусть черепаха ползёт по плоскости из точки $A$‍‍ с постоянной скоростью — вначале по направлению $AB$‍,‍ а затем через каждые 15 минут поворачивает на $90^\circ$‍.‍ Доказать, что вернуться в $A$‍‍ черепаха может лишь через целое число часов и лишь по направлению, перпендикулярному к $AB$‍.‍
9. Докажите, что ломаная дракона никогда не проходит по одному и тому же отрезку более одного раза.
10. Докажите, что если ломаную дракона повернуть вокруг её начала $O$‍‍ на $90^\circ$‍,‍ $180^\circ$‍,‍ $270^\circ$‍,‍ то из полученных четырёх ломаных (включая исходную) никакие две не имеют общего отрезка.
11. Рассмотрим множество ломаных $\lambda$‍,‍ обладающих такими свойствами: «$\lambda$‍‍ имеет $2^n$‍‍ звеньев равной длины, и если её разбить на $2^k$‍‍ кусков по $2^{n-k}$‍‍ звеньев в каждом куске, то два соседних куска получаются один из другого поворотом вокруг общей вершины на $90^\circ$‍‍ (для любого $k$‍)‍». Доказать, что это множество ломаных в точности совпадает со множеством ломаных дракона ранга $n$‍.‍

12. Введём на клетчатой бумаге систему координат, направив оси по линиям сетки и взяв за единицу масштаба сторону клетки. Будем рисовать главную ломаную дракона так, чтобы первыми тремя её вершинами были точки $(0,0)$‍,‍ $(0,1)$‍,‍ $(1,1)$‍‍ (см. рисунок на стр. 38).

    Пользуясь теоремой 1, можно продолжать эту ломаную сколько угодно раз: мы будем получать последовательно ломаные ранга 1, 2, 3, 4, 5, $\ldots$‍‍ Можно представить себе, что мы нарисовали их все и получили бесконечную ломаную дракона («главную ломаную дракона ранга $\infty$‍‍»). Её первые $2^n$‍‍ звеньев образуют ломаную ранга $n$‍.‍

    Докажите, что:

    1. Конец такой ломаной ранга $n$‍‍ будет находиться в точке $$ \left(2^{\textstyle\frac n2}\cos\dfrac{\pi n}4,~ 2^{\textstyle\frac n2}\sin\dfrac{\pi n}4\right) $$ (красные точки на рисунке на стр. 38).
    2. Слово, являющееся записью этой ломаной, можно быстро написать так. Сначала записываем чередующиеся буквы $L$‍‍ и $R$‍,‍ оставляя между ними промежутки для пропущенных букв: $$ L\_R\_L\_R\_L\_R\_L\_R\_L\_R\ldots, $$ а затем поступаем следующим образом. Пальцем левой руки укажем на первую букву, а правой рукой запишем её в первый промежуток, затем левой рукой укажем на вторую букву, а правой вставим её во второй промежуток, левой на третью... и так последовательно по всем буквам (не пропуская вновь вставленных), а правой вносим каждую указанную букву в первый свободный промежуток:

       

    3. Если, как в задаче 10, выпустить из одной точки четыре главных ломаных дракона ранга $\infty$‍,‍ то по каждому отрезку сетки пройдёт ровно одно звено одной из этих ломаных (рис. 11).

       (Это — трудная теорема; её впервые доказал D. Е. Knuth.)

Литература

Gardner М. Mathematical games // Scientific American. — 1967. — V. 216. — Март, с. 124‍—‍125; Апрель, с. 118‍—‍120; Июль, с. 115.