Школа-лицей №8

Математическое моделирование социальных и экономических процессов

Прикладная математика

Иерархические мозаики

Выполнил: Зверев Никита

Руководитель:

Павлодар, 2002 год

План.

I.  Введение.

II.  Основные понятия.

1

III.  О мозаиках вообще.

1.  Периодические мозаики.

2.  Квазипериодические мозаики.

3.  Самоподобные мозаики.

4.  Задача Конвея.

2

IV. Разрешение задачи Конвея.

I.Введение.

С древних времён люди использовали всевозможные методы замощения плоскости для облицовки стен, составления паркетов, однако это им не всегда удавалось (так замостить плоскость правильными семиугольниками никогда не удастся). Эти неудачи, по-видимому, заставили выяснять, какие математические факты обеспечивают успех или неуспех их работы. Вообще, замостить плоскость можно по-разному: правильными многоугольниками, произвольными четырёхугольниками, мостить так, чтобы получить орнамент с наложенными на него условиями.

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

В «Кванте» №2 за 1998 год была предложена задача Конвея об « апериодической» плитке. Цель моего проекта – решить эту задачу.

НЕ нашли? Не то? Что вы ищете?

В первом параграфе будет рассказано о мозаиках, во втором будут приведены некоторые теоремы, а также моё решение задачи Конвея.

II. Основные понятия.

Преобразование подобия – такое преобразование h плоскости (или пространства),при котором расстояние d(x, y) между любыми двумя точками x и y изменяется в некоторое, одно и то же, k число раз.

Движение – преобразование подобия при k равном 1.

Параллельный перенос – преобразование плоской фигуры F, при котором произвольная её точка (в Декартовых координатах x, y) переходит в точку (x+a, y+b), где a и b – постоянные.

Поворот (около данной точки) – движение, при котором каждый луч, исходящий из данной точки, поворачивается на один и тот же угол в одном и том же направлении.

Отражение (симметрия) – преобразование фигуры F в F1, при котором каждая точка Х переходит в точку Х1, симметричную относительно прямой l.

Инверсия – преобразование, переводящее каждую точку А плоскости в такую точку А’, лежащую на луче ОА, что ОА’·ОА=k, где k – некоторое постоянное действительное число. Точка О называется центром или полюсом инверсии, k – степенью или коэфициентом.

Самоподобная фигура – такая фигура F, что её можно разрезать на несколько фигур F1, F2,…, Fn, каждая из которых подобна исходной.

Мозаика – замощение всей плоскости плитками без перекрытий.

Моноэдральная мозаика – мозаика, в которой все плитки попарно равны.

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

Квазипериодическая мозаика – мозаика не являющаяся периодической, но любая её конечная часть встречается во всём замощении бесчисленное множество раз.

Инфляция – процесс «склеивания» крупной фигуры из более мелких.

Дефляция – процесс «разрезания» фигуры на более мелкие.

Ди-процесс – процесс инфляции-дефляции.

1

III.О мозаиках вообще.

Мозаики – это важный раздел математики, научный подход к которому появился сравнительно недавно. До этого всевозможные покрытия плоскости рассматривались только как красивые безделушки и поэтому многие вопросы связанные с ними вовсе не привлекали к себе интерес. Но открытые английским физиком Роджером Пенроузом в 1984 году квазикристаллы, являющиеся примером мозаик заставили учёных обратить внимание на эту тему.

Математики Джон Конвей и Билл Терстон обнаружили новые неожиданные связи самоподобных разбиений плоскости (о которых будет сказано ниже) с некоторыми другими разделами математики.

Благодаря этому в современной математике стали появляться новые проблемы, связанные с построением и свойствами мозаик. Одну из этих проблем, называемой задачей Конвея я попытаюсь решить, но для начала рассмотрим периодические мозаики.

1.Периодические мозаики

Именно периодические мозаики являются самыми древними замощениями плоскости, известными ещё со времён древнего Египта. Они широко использовались при выкладке паркетов и изобразительном искусстве вплоть до наших дней. Одним из ярких примеров периодического замощения является мозаика голландского художника М. Эшера «Всадники», чертёж которой приводить не буду по причине сложности, но не уходя далеко можно показать одно из простейших замощений плоскости – параллелограммами (рис.1). Любой параллелограмм этого замощения можно получить из заштрихованного сдвигом на вектор nu+mv (|u| и |v| - рёбра параллелограмма, n и m принадлежат целым числам).Следует отметить, что так же эта мозаика переходит сама в себя при сдвиге на вектор u или v, поэтому назовём его замощением с периодами u и v.

2.Квазипериодические мозаики.

Но такими периодами не обладают квазипериодические заполнения плоскости о которых сейчас и пойдёт речь. Основным свойством этих замощений является то, что отдельные элементы их встречаются бесконечное число раз, но обладая даже этим свойством они всё равно остаются непериодическими. Как мной было сказано ранее, эти мозаики были открыты физиком Пенроузом в 1984 году, а сами они являются двумерными аналогами квазикристаллических структур – материалов нового типа, которые сейчас стремительно развиваются. Сейчас по квазипериодическим мозаикам опубликовано несколько сот статей (а ведь эти замощения абсолютно элементарны) по физике и математике. Далее рассмотрим несколько примеров таких заполнений плоскости.

Мозаика, приведённая на рис.2, была открыта Пенроузом ещё за десять лет до самих квазикристаллов.

Она состоит из ромбов двух типов: узкого ( с углами 36˚ и 144˚) и широкого ( с углами 72˚ и 108˚) с одинаковыми сторонами. Любопытно заметить, что это замощение обладает осью пятого порядка, т. е. переходит в себя при повороте на угол 72˚ вокруг некоторой точки, в то время, как таких осей у периодических замощений не существует.

Также здесь приведено другое заполнение плоскости (рис.3), построенное Пенроузом. В данном случае используются многоугольники четырёх типов: правильный пятиугольник, пятиконечная звезда, пятиконечная звезда с «отрезанными» двумя лучами («бумажный кораблик») и ромб. Но как позже станет ясно замостить плоскость большим числом многоугольников - не проблема, проблема покрыть её как можно меньшим числом различных фигур.

Каждое из показанных выше квазипериодических замощений – это покрытие плоскости с помощью сдвигов и поворотов конечного числа фигур. Эти покрытия не переходят в себя ни при каких параллельных переносах, любая конечная часть их встречается во всём покрытии бесчисленное множество раз.

Эти замощения обладают некоторым свойством, которое Пенроуз называл инфляцией. Изучение этого свойства позволяет разобраться в структуре этих покрытий, кроме того Инфляцию можно использовать для построения узоров Пенроуза. Наиболее наглядный пример инфляции – это треугольники Робинсона. Треугольники Робинсона – это два равнобедренных треугольника Р, Q с углами (36˚,72˚,72˚) и (108˚,36˚,36˚) соответственно ( ниже приведены эти треугольники, где λ – золотое сечение: λ = (1+√5)/2).

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

На рис.4: прямая ac – биссектриса угла dab, а отрезки ae, ab и ac равны. Легко видеть, что треугольник acb равен треугольнику ace и они оба подобны треугольнику P, а треугольник cde подобен треугольнику Q. Далее в треугольнике Q: длина отрезка gh равна длине отрезка ih (и равна 1). Треугольник igh подобен треугольнику P, а треугольник igf подобен треугольнику Q. Линейные размеры новых треугольников в λ раз меньше, чем у исходных ( Позже будем называть их треугольниками предыдущего уровня).

Такое разрезание называется дефляцией. Обратное преобразование называется инфляцией.

Рис.4 показывает, что из двух P-треугольников и одного Q-треугольника можно склеить P-треугольник, а из P и Q треугольников можно склеить Q-треугольник. Соответственно у новых треугольников линейные размеры будут в λ раз больше, чем у исходных.

Разумеется, мы можем повторить наши преобразования, так, например после двух инфляций мы получим пару треугольников, линейные размеры которых в λ² раз больше исходных. Последовательно применяя инфляцию можно получить пару треугольников сколь угодно большого размера. Так мы сможем замостить всю плоскость.

Таким образом мы подошли к новому типу мозаик – самоподобным мозаикам.

Но для начал стоит вспомнить о преобразованиях подобия. Обозначая расстояние между точками x и y, как d(x, y), преобразование подобия, как h, а коэффициент преобразования, как k получаем: d(x, y)= k·d(h(x),h(y)) (*)

В частном случае, когда k =1 преобразование подобия называется движением. Параллельный перенос – перемещает каждую точку в другую (разумеется, при этом неподвижных точек нет), поворот (вокруг точки О на некоторый угол) – имеет только одну неподвижную точку (точку О ), отражение (симметрия), относительно прямой l – имеет бесконечно много бесконечно много неподвижных точек, которые составляют прямую l. Из чего делаем вывод: одни движения могут не иметь неподвижных точек, другие имеют только одну, а третьи – бесконечно много.

По-другому обстоит дело, когда k не равно 1, т. е. h не является движением: тогда преобразование h имеет единственную неподвижную точку.

Благодаря этой теореме о неподвижной точке (она является известным фактом, поэтому её доказательство опустим) любое преобразование подобия (центром О и коэффициентом k) сводится к двум операциям: гомотетии и повороту. Действительно, после гомотетии с коэффициентом k и центром О выполняется равенство (*) и остаётся только повернуть нашу фигуру, а в частном случае наше преобразование может и не содержать этого поворота.

Возвращаясь к самоподобным фигурам приведём несколько примеров, как треугольник, «домино», «стул» (триомино), «сфинкс» (гексамино). На рис.5 приведены некоторые варианты их дефляции.

3. Самоподобные мозаики и принцип их составления.

Возьмём на плоскости какую-нибудь «хорошую самоподобную фигуру без дыр, как, например, треугольник, параллелограмм или какой-нибудь другой самоподобный многоугольник. Рассмотрим способ замощения плоскости с помощью этой фигуры. Возьмём, например «стул», метод разрезания которого показан выше и по известному методу будем прибавлять ещё по 3 такие же разрезанные фигуры, постепенно увеличивая количество плиток, таким образом мы получим возрастающую по размерам последовательность кусков плоскости, уложенных плитками и в итоге этими фигурами окажется покрыта вся плоскость.

Теперь мы можем сформулировать свойства самоподобной мозаики:

1.  Плитки этой мозаики (будем говорить, что это плитки 1-го уровня) могут быть объединены в более крупные плитки (плитки второго уровня), которые подобны плиткам 1-го уровня, причём так, что плитки 2-го уровня опять составляют мозаику (иначе говоря, плитка является самоподобной фигурой).

2.  Такое последовательное укрупнение возможно для любого k-го уровня. (Благодаря этому самоподобные мозаики называются также иерархическими)

Такая иерархия в мозаиках может быть строгой ( когда мозаика каждого следующего уровня получается из плиток мозаики предыдущего уровня единственным способом ), и слабой ( плитки мозаики могут объединяться в плитки следующего уровня несколькими разными способами): квадрат – пример слабой иерархии, а «стул» - строгой.

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

Теперь об ещё одной особенности мозаик со строгой иерархией. С первого взгляда кажется, что построение мозаики каждого следующего уровня происходит по единственному алгоритму и, следовательно, единственным способом. Но оказывается, что их количество бесконечно много (напомню, что две бесконечные мозаики на плоскости считаются одинаковыми, если одну из них можно совместить с другой некоторым движением плоскости) и этому есть такое объяснение (на примере «стула»).

Разобьём «стул» на четыре «стульчика» (рис.6) и каждый из них подпишем одним из четырёх чисел: 1,2,3 или 4. Пусть «стул» на первом этапе ди-процесса входит в большой «стул» под номером a1. В свою очередь, на втором этапе он будет входить под номером а2 и. т.д. Таким образом мозаика, вырастающая из данного «стула» определяет некоторую последовательность: а1,а2,а3,…,аn, состоящую из чисел 1,2,3,4. Та же мозаика может вырасти из любой другой плитки, но тогда получится другая последовательность.

Так как число плиток в данной мозаике счётно, а различных последовательностей бесконечно много, то и различных самоподобных мозаик из «стульев несчётно много.

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

В предложенных нами выше мозаиках все плитки были расположены под конечным числом различных углов с точностью до параллельного переноса. До 1992 года стоял вопрос: а существует ли такая моноэдральная мозаика, что её плитки ориентированы бесконечным числом способов. И именно тогда Конвей предложил самоподобную мозаику со строгой иерархией, в которой все плитки – равные прямоугольные треугольники с катетами 1 и 2 и гипотенузой √5, они допускают самоподобное разбиение на 5 равных треугольников

Острый угол α треугольника равен α=arctg(1/2). Указанное разбиение треугольника индуцирует самоподобные мозаики – мозаики Конвея.

Очевидно, что в этом заполнении (рис.7) плоскости для любой плитки и любого целого m всегда найдётся плитка, повёрнутая относительно первой на угол m·α. Однако, как можно показать, угол α несоизмерим с 2π. Тогда любые два треугольника, повёрнутые относительно друг друга на m·α (m не равно нулю) не параллельны друг другу. Поэтому в мозаике Конвея треугольные плитки встречаются в бесконечно многих ориентациях.

На самом деле, все мозаики Конвея – самоподобные мозаики со строгой иерархией, поэтому их бесконечно много.

Иначе говоря, основным свойством мозаики Конвея является то, что для любого возможного положения треугольника Конвея ∆ и любого маленького положительного значения ε в мозаике Конвея найдётся плитка ∆ε, которая параллельна треугольнику ∆ с точностью до ε, т. е. углы между соответствующими сторонами треугольников ∆ и ∆ε меньше ε. Другими словами, ориентации плиток в мозаике Конвея распределены всюду плотно во множестве всех возможных ориентаций вообще.

Несколько позже Конвей вместе с математиком Ч. Радином предложил вариант пространственной мозаики, состоящей из равных призм, чьи ориентации распределены всюду плотно среди всех возможных ориентаций в пространстве. Ориентацию многогранника в пространстве можно определить при помощи трёх взаимно перпендикулярных векторов, связанных с перемещаемым многогранником. Всюду плотность ориентаций ячеек означает, что для любого положения многогранника Р в пространстве и любого заданного наперёд сколь угодно маленького ε>0 найдётся такая ячейка Рε мозаики, что те наши три вектора составляют с соответствующими векторами из тройки многогранника Р углы меньше ε.

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

Этот треугольник разбивается, как указано на рисунке 8б, поэтому исходная призма может быть разбита на восемь ей подобных призм (рисунок 8в). Теперь две призмы А и В можно повернуть, так как они составляют правильную треугольную призму. Далее призмы С и D составляют прямоугольный параллелепипед с квадратной гранью 1х1. Поэтому повернём эту пару на 90˚ и разместим её в том же месте.

Таким образом мы получили конструкцию Конвея-Радина (рисунок г). Заметим что в этой конструкции идентичны призмы, повёрнутые друг относительно друга на 120˚ и 90˚ вокруг взаимно перпендикулярных осей. Самоподобная мозаика из призм Конвея-Радина которая строится при помощи ди-процесса наряду с каждой призмой Р будет содержать призмы, повёрнутые относительно Р при помощи всевозможных комбинаций вида

g1∙g2∙g1∙g2∙…∙g1∙g2,

где g1 и g2– повороты на 120˚ и 90˚ вокруг взаимно перпендикулярных осей.

За ориентирующую тройку векторов можно взять три взаимно перпендикулярные направленных ребра призмы, исходящих из вершины прямого угла основания призмы. Нетрудно показать, что в силу перпендикулярности осей поворотов g1 и g2 множество различных ориентаций должно быть бесконечным.

4.Задача Конвея.

Ошибочно было бы думать, что из, например, «стульев» можно составить только непериодические мозаики.

На рис.9 приведена периодическая мозаика, составленная из них. Таким образом, самоподобные многоугольники наряду со строго иерархическими мозаиками, которые непериодичны, могут допускать также и периодические замощения.

Джон Конвей поставил вопрос: существует ли на плоскости такая многоугольная фигура (или даже криволинейная), из которой можно составить лишь непериодические мозаики? Любопытно, что в пространстве такая фигура существует – это бипризма Шмитта-Конвея-Данцера, чертёж которой – рис.10.

Бипризма определяется следующим образом. Возьмём сначала треугольную призму АВСА1В1С1, у которой боковая грань АВВ1А1 есть ромб ( с острым углом α). Теперь приставим к ромбовидной грани такую же призму, повернув исходную призму на угол 180˚ вокруг диагонали ромбической грани. Заметим, что боковые рёбра второй призмы составляют угол α с боковыми рёбрами первой призмы. Пара так приставленных друг к другу призм составляет исходную бипризму. Нетрудно убедиться в том, что бипризма разбивает пространство, т. е. заполняет его без пропусков и перекрытий.

Устройство всех мозаик предопределено. Если мы хотим заполнить пространство бипризмами, мы должны составить из них слой (рис.11а). В данном случае все бипризмы параллельны друг другу. При этом каждый слой представляет собой периодическое семейство бипризм. Далее всё пространство заполняется такими слоями (рис11.б). Очевидно что каждый следующий получается из предыдущего поворотом на угол α (где α равно острому углу) ромба с параллельным переносом.

Поэтому, если угол ромба несоизмерим с π, т. е. α не равно m/n∙π, то параллельного переноса переводящего покрытие само в себя.

Но для Евклидовой плоскости задача Конвея ещё не решена и на данный момент требуется либо найти «апериодическую» плитку, либо доказать, что её не существует.

2

Некоторые теоремы, связанные с замощениями плоскости.

Теорема: замощения треугольниками Робинсона (указанное во второй части третьего раздела) не является периодическим.

Доказательство: предположим, что замощение плоскости треугольниками Робинсона периодическое с периодами u и v. Покроем плоскость сетью параллелограммов со сторонами u и v.

Обозначим через р число Р-треугольников, у которых левая нижняя вершина (относительно нашей сети) расположена в заштрихованном параллелограмме; аналогично определим число q (назовём отобранные р + q треугольников фундаментальной областью).

Рассмотрим круг радиусом R с центром О. Обозначим через рR (соответственно qR) число Р-треугольников (соответственно q-треугольников), лежащих внутри этого круга.

Можно доказать, что lim(pR/qR)=p/q.

Действительно, число треугольников, пересекающих окружность радиуса R, пропорционально R, в то время, как число треугольников внутри круга радиуса R пропорционально R². Поэтому в пределе отношение числа Р-треугольников к числу Q-треугольников в круге равно отношению в фундаментальной области.

Возьмём теперь наше замощение и выполним преобразование дефляции. Тогда в исходной фундаментальной области окажется р’=2р+q меньших Р-треугольников и q’=p+q меньших Q-треугольников. Обозначим через р’R и q’R число меньших треугольников в круге радиуса R. Теперь легко получить противоречия. В самом деле, p/q=lim (pR/qR)=lim(p’R/q’R)=p’/q’=2p+q / p+q откуда решая уравнение p/q=(2p+q)/(p+q), находим p/q = (1+√5)/2 в то время, как p и q – целые. Противоречие показывает, что замощение треугольниками Робинсона – непериодическое.

Теорема: иерархические мозаики не являются периодическими.

Доказательство: предположим, что существует параллельный перенос t, который передвигает всю строго иерархическую мозаику в себя. Ясно, что перенос t перемещает каждую плитку F1 мозаики в какую-то другую плитку F2. В силу однозначной определённости следующей мозаики из плиток 2-го уровня параллельный перенос t перемещает в себя также мозаику 2-го уровня и, вообще, мозаику любого k-го уровня. Опять, в силу того, что плитки мозаики второго уровня однозначно составляются в плитки мозаики 3-го уровня, параллельный перенос t, перемещающий в себя мозаику 2-го уровня, перемещает в себя мозаику 3-го уровня, и, вообще, мозаику любого k-го уровня.

Плитки k-го уровня в 2 раз больше плитки мозаики 1-го уровня. Поэтому, если в плитку 1-го уровня можно поместить круг диаметром d, то в плиту k-го уровня можно поместить круг диаметром 2 ∙d. При достаточно большом значении k диаметр 2 ∙d превзойдёт длину вектора переноса t. Значит перенос на вектор t переводит круг радиуса 2 ∙d в круг такого же радиуса, перекрывающийся с первым. Но с другой стороны, эти круги должны принадлежать разным плиткам k-го уровня и потому круги не могут пересекаться.

II.Моё решение задачи Конвея.

Напомню формулировку задачи Конвея: найти такую плитку, которой можно замостить всю плоскость только непериодически (или доказать несуществование таковой).

Найдём сначала набор таких фигур. Пусть наши фигуры могут быть разного размера. Тогда самым простейшим замощением будет покрытие кругами и «кольцами» (оно очевидно: в нём используется один круг и бесконечное количество колец).

Но во всех показанных выше мозаиках мы использовали плитки с фиксированными размерами. Будем считать, что мы нашли такой «апериодический» набор плиток. «Склеим» из них тогда какие-то большие фигуры. Получим тогда мозаику из плиток большего размера и повторяя этот процесс далее делаем вывод, что мы получим этот набор только тогда, когда в процессе инфляции у нас выйдет моноэдральная мозаика.

Следовательно наша задача сводится всё-таки к нахождению одной такой «апериодической плитки». Из всех предыдущих теорем нам известно, что единственный способ получить её – это воспользоваться самоподобной фигурой.

Рассмотрим какую-либо самоподобную фигуру и разрежем её на минимальное число треугольников (случай 1). На рис.13 приведены примеры разрезания «стула» и параллелограмма. Далее, если мы разрежем эту фигуру на подобные ей и каждую из получившихся разрежем на треугольники подобным образом то придём к случаю 2. Но как можно заметить, есть такое разрезание треугольников на себе подобные в случае 1, что разрезания в обоих случаях будут равны.

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

Каким образом мы будем заполнять плоскость этими треугольниками? Будем считать, что если два наших многоугольника (произвольных) касаются, то они в нашей мозаике будут касаться одинаковыми сторонами, иначе говоря, будут касаться соответствующими сторонами наши треугольники. Тогда будем объединять наши такие пары одинаковых треугольников в параллелограммы. Но так как в таком случае наши параллелограммы будут строится по какому-то конкретному алгоритму, который будет постоянно повторяться (что не соблюдается в узоре Пенроуза), то мы получим из параллелограммов периодическую мозаику. Если же мы[MSOffice1]  не сможем получить из этих треугольников вообще какую-то мозаику. Из чего мы делаем вывод: из многоугольников либо не получится мозаика, либо одна из получившихся будет периодической.

Рассматривая криволинейную фигуру скажу, что мы можем рассмотреть её аналогичным образом, «отрезав» от неё криволинейные части, а оставшееся «разрезать» на треугольники.

Список используемой литературы.

1.  «Квант» №2 за 1998 год.

2.  «Квант» №6 за 1997 год.

 [MSOffice1]