Кривые дракона

36

---

running_head:
folio:

КРИВЫЕ
ДРАКОНА

Из этой статьи
вы узнаете об интересном
семействе личный,
одна из которых
нарисована здесь,
а несколько других —
на стр. 42 и 43.

Н. Б. ВАСИЛЬЕВ, В. Л. ГУТЕНМАХЕР

37

ЧТО ТАКОЕ КРИВАЯ И ЛОМАНАЯ
ДРАКОНА

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

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

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

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

38

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

39

КАК РИСОВАТЬ ДЛИННЫЕ
ЛОМАНЫЕ ДРАКОНА?

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

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

Ломаная дракона рана $n$ состоит из $2^n$ звеньев и соответственно имеет $2^n-1$ вершин (не считая концов). Таким образом, у нее есть средняя вершина и на $(n>0)$, поскольку число вершин нечетно. На рис. 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$ по (или против) часовой стрелке. Полученную новую ломаную таким же способом продолжем от конца; так продельваем столько раз, сколько захочется и сколько сможем. Это автоматически и быстро можно делать, если под рукой есть калька или, еще лучше, слегка произрачная клетчатая бумага. (Подумайте, как!)

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

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

40

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

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

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

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

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

*) См. задачу 9 в конце статьи.

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

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

В самом деле, проследим за последним и складыванием полоски пополам. Для удобства мы будем ссылаться на условный рис. 7. Мы хотим сложить полоску пополам n+1 раз. Сложим ее сначала n раз и построим на нее в профиль (красная линия на рис. 7). Затем сложим ее еще раз пополам и развернем этот последний сгиб на 90° (черная линия на том же рисунке*). Телербумажка идет от грибов A к грибам B и обратно не по гипотенузе, а по катетам равноведренного прямогоугольного треугольника ABC. Развернем телерь все остальные сгибы

Рис. 6

отрезок является гипотенузой равноведренного прямогоугольного треугольника, катеты которого — звенья исходной ломаной (на рисунке треугольники слегка закрашены), причем каждые два соседних таких треугольника получаются друг из друга поворотом на 90° вокруг точки вершины; другими словами, если идти вдоль красной ломаной дракона, то эти

до 90° (на рис. 8 показано, как разворчиется отдельный сгиб). Тогда каметы прямогоугольников образуют ломаную дракона рана n+1, а гипотенузь — рана n.

Пользоваться этим сообщениями, легко доказать оба утверждения теоремы 2. Вы можете попробовать дать другое доказательство: вывести теорему 2 из теоремы 1.

*) На нашем рисунке черная линия в $\sqrt{2}$ раз длиннее красной, но это не имеет значения, поскольку нас интересует форму ломаной, а не ее размеры.

41

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

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

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

СЛОВА

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

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

Будем поворот направо обозначать буквой $R$, поворот налево — буквой $L^*$). Тогда все ломаная запишется таким «словом»:

LLR

(«словом» во многих разделах математики и логики называют просто любую последовательность букв). Точно так же можно записать словом из букв $L$ и $R$ любую ломаную дракона.

Чтобы получить из ломаной $a$ ломаную $\delta$ (рис. 2), нужно бумажку сложить еще один раз «налево» (см. рис. 2, $\delta$ и 10). При этом между каждой двумя вершинами ломаной $a$ возникнет еще по одному повороту, причем на рис. 10 хорошо видно, что эти новые повороты будут через

*) Мы выбрали первые буквы английских слов right (правый) и left (левый), потому что русские буквы П и Л слишком похожи друг на друга (кстати, немецкие Rechts и links начинаются с тех же буквы).

42

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

43

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

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

44

доваться; таким образом, получим
$$L L R \rightarrow L L R L R R,$$

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

$$L L R L L R R \rightarrow L L R L R L R R,$$

Начертите эту ломаную. Это — Главная ломаная дракона ранга 4. Если хотите, закрутите у нее углы, как это предложил Хейвей.

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

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

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

Рис. 10

букв $L$ и $R$, «записьми» ломаных дракона *).

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

ЗАДАЧИ

1. Какой длины надо взять полоску, чтобы, сложив ее пополам 30 раз, получить расстояние между соседними сгибами равным 1 см? Большие или меньше расстояния от Земли до Луны?

2. Как изменится ломаная дракона, если полоску бумаги положить на стол другим ребром? Как изменится при этом слова, записьющее ломаную?

3. a) Сколько существует различных (не подобных друг друга) ломаных дракона ранга 4? Нарисуйте их все. Напишите соответствующие им слова из букв $L$ и $R$.

6. Сколько существует различных ломаных ранга $n$?

4. Допустим, что черпаха прополза по ломаной дракона и прочаза слова из букв $L$ и $R$. Какое слово она прочитет, если проползет по этой ломаной в обратном направлении?

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

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

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

a) Для любых слов $s$ и $t$

$$\overline{st} = \overline{t} \overline{s}.$$

6. Если $s_{n+1}$ — слова, соответствующие ломаной дракона ранга $n+1$, то

$$s_{n+1} = s_n x \overline{s}_n,$$

где $s_n$ — неокоторее слова, соответствующие ломаной дракона ранга $n$, а $x$ — слова, соответствующие одной буквы.

*) Именно такой способ изложения избрали канадские математики Кнут и Дэвис, по рукописи которых «Number representations and dragon curves» (Ch. Davis, D. E. Knuth) авторы статьи впервые познакомились с кривыми драконами. Из этой рукописи занимаются и ряд рисунков длиных кривых дракона.

45

в) Если $s_n$ — слово, соответствующое ломаной дракона, то $s_n$ отличается от $s_n$ только одной средней буквой.

г) Слово, записывающее ломаную дракона ранга $n$, можно и притом единственным образом построить, если задать произвольно $n$ букв, которые должны стать в этом слове на местах с номерами $2^k$, где $k=0,1,2,...,n-1$ (т. е. на первом, втором, четвертом, восемом,…, $2n^{-1}-m$ местах); после этого, чтобы найти, какая буква стоит на $m$-м месте, нужно представить $m$ в виде $m=2^k(2l+1)$, где $k$ и $l$ целые; если $l$ четно, то на $m$-м месте стоит та же буква, что и на $2^k$-м, если $l$ нечетно — противоположная.

д) Два слова $s_n'$ и $s_n''$ задают одинаковые по форме (подобные) ломаные дракона в том и только в том случае, если после вычеркивания средней буквы эти слова либо совпадают, либо одно получается из другого заменой $L$ на $R$ и $R$ на $L$. (Например, слова LLRLLRR, LLRRLRR, RRLRRLL задают одинаковые ломаные.)

6. Пусть мы имеем ломанную дракона ранга $n$. Из нее можно получить две ломаные дракона ранга $n+1$, пользовать либо теоремой 1 (принимая за точку $O$ тот или другой конец ломаной), либо теоремой 2 (достранивая треугольник в ту или другую сторону). Будут ли в обих случаях получаться те же самые две ломаные дракона ранга $n+1$ или, вообще говоря, другие? Как получать их слова из слова данного ломаной ранга $n$?

7. На плоскости даны две точки $A$ и $B$. Начертим квадрат с центром в середине отрезка $AB$, одна из сторон которого равна $2AB$ и параллельна отрезку $AB$. Докажите, что любая ломаная дракона с концами в точках $A$ и $B$ лежит внутри этого квадрата. Докажите, что для любой точки $M$ внутри этого квадрата и любого положительного числа $e$ можно найти такую ломаную дракона с концами $A$ и $B$, которая проходит от точки $M$ на расстоянии меньше $e$ (говора математическим языком, «объединение всех ломаных дракона с концами в точках $A$ и $B$»). Ее первый $2^n$ звеньев образуют ломанную ранга $n$.

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

a) Конец такой ломаной ранга $n$ будет находиться в точке

$$\left( \frac{n}{2} \cos \frac{\pi n}{4}, \frac{n}{2} \sin \frac{\pi n}{4} \right)$$

(красные точки на рисунке на стр. 38).

46

---

running_head:
folio:

6. Слово, являющееся записью этой ломаной, можно быстро написать так. Сначала записьаем через цифры буквы $L$ и $R$, оставляя между ними промежутки для пропущенных букв:

L_R_L_R_L_R_L_R_L_R...

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

$$LLRLLRLLLRRLRLLLRL$$

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

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

Рис. 11.

ЛИТЕРАТУРА

M. Gardner, Mathematical games, Scientific American 216, 1967 г., марта (124—125), аппель (118—120), июль (115).