Мозаика Робинсона

Перед вами пример апериодической мозаики — мозаика Робинсона. Из плиток этой мозаики, как их ни перекладывай, составить можно только непериодические замощения плоскости. Также замощения Робинсона обладают свойством квазипериодичности: любой конечный фрагмент повторяется в замощении бесконечное число раз. А всего различных замощений плоскости плитками Робинсона несчетное число.

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

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

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

В качестве примеров, относящихся к первому типу, можно указать, скажем, протомножества, состоящие всего из одного элемента, — пентамино, имеющего форму креста, или правильного шестиугольника:

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

Если же в качестве единственной фигуры в наборе мы рассмотрим квадрат или правильный треугольник, то замощения, составленные на ее основе, могут оказаться как периодическими, так и непериодическими, а различных замощений бесконечно много:

Что же касается апериодических протомножеств, то до середины XX века человечеству не было известно ни одного такого примера, так что в 1961 году китайский математик Хао Ван (Hao Wang) даже выдвинул гипотезу, что их не существует вовсе. Впрочем, уже в 1966 году американский математик Роберт Бергер (Robert Berger), ученик Вана, сконструировал первый апериодический набор, опровернув тем самым гипотезу своего учителя. Однако обозреть полученный Бергером набор было весьма непросто, поскольку состоял он из 20 426 плиток. Немного позже сам же Бергер сумел заметно уменьшить число различных многоугольников в апериодическом протомножестве, доведя его до 104, а в течение следующего десятилетия усилиями ряда ученых удалось понизить его до двух — это знаменитые мозаики Пенроуза. Существует ли апериодическое протомножество, состоящее ровно из одной плитки, неизвестно до сих пор.

В 1971 году американский математик Рафаэль Робинсон предъявил протомножество, состоящее всего из 6 плиток:

Выступы и пазы на них организованы таким образом, чтобы рисунок на прикладываемых друг к другу плитках был согласован: красные линии на одной плитке продолжаются на соседних плитках красными линиями, а синие — синими:

Плитка A отличается от остальных плиток формой углов. Нетрудно убедиться, что плитками двух видов, единственное различие которых заключается в форме углов, можно замостить плоскость тремя принципиально разными способами — регулярно, случайным образом сдвигая горизонтали и случайным образом сдвигая вертикали:

Однако выступы и пазы по сторонам плиток Робинсона накладывают на замощение дополнительные ограничения. Так, легко увидеть, что плитки типа A должны располагаться в углах квадрата 3×3 таким образом, чтобы красные линии на них смотрели друг на друга, а по центру этого квадрата должна находиться плитка типа B. У нас есть возможность выбрать одну из четырех ориентаций плитки B, но как только мы ее зафиксируем, оставшиеся позиции квадрата 3×3 заполняются однозначно:

Оказывается, сконструированные подобным образом квадраты 3×3 — так называемые макроплитки — ведут себя точно так же, как и плитки типа A. А именно, единственная возможность соединить их между собой — это расположить их по углам квадрата 7×7. Выходящие при этом из середин сторон макроплиток красные линии должны смотреть друг на друга. Снова по центру должна располагаться плитка типа B, а зафиксировав одну из четырех ее ориентаций, мы однозначно заполняем оставшиеся промежутки и получаем супермакроплитку:

Этот процесс укрупнения можно продолжать и дальше. Так, у нас возникает иерархия квадратов размера 1×1, 3×3, 7×7, 15×15, 31×31, ..., (2ⁿ−1)×(2ⁿ−1), ..., каждый из которых наделен узором: две из выходящих по центру его сторон линии являются красными, а остальные — синими. Когда мы объединяем макроплитки в супермакроплитки, красные линии сливаются в квадрат, благодаря чему образуется иерархия красных квадратов размера 2×2, 4×4, 8×8, 16×16, 32×32, ..., 2ⁿ×2ⁿ, ..., соответственно. Наличие этих красных квадратов объясняет удивительные свойства, присущие всем возможным замощениям из плиток Робинсона. Посмотрим на них более внимательно.

Во-первых, любое замощение плоскости плитками Робинсона является непериодическим, то есть используемое протомножество (рассмотренный выше набор из шести плиток) апериодично. Действительно, если бы существовал параллельный перенос, оставляющий какое-либо замощение неизменным, то существовал бы некоторый вектор \(\vec v\), при перемещении на который каждой плитки замощения мы бы не увидели разницы. Однако если данный параллельный перенос сохраняет замощение, то он должен перевести произвольный красный квадрат в точно такой же красный квадрат. Учитывая, что в любом замощении плитками Робинсона можно найти сколь угодно большие красные квадраты, причем квадраты одного размера не пересекаются между собой, это не представляется возможным. В самом деле, найдется квадрат, длина стороны которого больше длины вектора \(\vec v\), а значит, при параллельном переносе вдоль \(\vec v\) этот квадрат наложится сам на себя.

Во-вторых, в каждом замощении плоскости плитками Робинсона почти любой фрагмент встречается бесконечно много раз. Это утверждение нужно понимать в вероятностном смысле: если мы выберем замощение плитками Робинсона случайным образом, то оно будет квазипериодичным с вероятностью 1 — точно так же, как если бы мы случайным образом выбирали точку в квадрате \([0;\,1]\times[0;\,1]\), то с вероятностью 1 обе ее координаты оказались бы иррациональными. Чтобы убедиться в квазипериодичности подавляющего числа замощений, достаточно для произвольного фрагмента такого замощения найти достаточно большой красный квадрат, содержащий этот фрагмент внутри себя целиком. Поскольку квадратов одного и того же размера бесконечно много, то и содержащихся внутри них фрагментов заданного вида — тоже.

Оказывается, однако, что в некоторых замощениях присутствуют фрагменты, не содержащиеся ни в одном из красных квадратов. Чтобы понять, почему так получается, а заодно — чтобы убедиться, что таких фрагментов на самом деле не слишком много, поглядим более внимательно на процесс укрупнения, благодаря которому нам удается перейти от отдельных плиток к замощению всей плоскости в целом. Рассмотрим какую-нибудь плитку типа A. Она входит в макроплитку размера 3×3 в одном из четырех положений, которые мы обозначим цифрами 1, 2, 3 и 4:

Аналогично, макроплитка входит в супермакроплитку в одном из четырех положений, и так далее. Таким образом, если нам дано некоторое замощение плоскости, то каждой плитке мы можем сопоставить бесконечную последовательность из цифр 1, 2, 3 и 4. Для примера рассмотрим замощение, изображенное на следующем рисунке. Если мы стартуем с зеленой плитки, то первый элемент последовательности равен 3, поскольку зеленая плитка входит в оранжевую макроплитку в третьем положении. Второй элемент равен 1, так как оранжевая макроплитка входит в бежевую супермакроплитку в первом положении. Аналогично, третий элемент равен 2, четвертый — 4, и так далее. То есть зеленой плитке сопоставляется последовательность 3124…

Однако верно и обратное, то есть любой такой последовательности мы можем сопоставить некоторое замощение. Отметим, что некоторым последовательностям будет соответствовать замощение не всей плоскости, а только ее части. Например, если мы возьмем последовательность 222222..., то получим замощение четверти плоскости, а если 131313..., — то полуплоскости. Подобные куски можно «склеить» между собой, в результате чего возникнет замощение всей плоскости с исключительными линиями — прямыми или лучами:

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

Напоследок отметим, что число различных замощений плоскости плитками Робинсона несчетно. В самом деле, различных последовательностей из цифр 1, 2, 3 и 4 — континуум, а каждой последовательности можно сопоставить некоторое замощение. И хотя одно и то же замощение соответствует бесконечному числу различных последовательностей, поскольку стартовать мы можем из любой плитки, всё же плиток в замощении лишь счетное число. Следовательно, число замощений не может быть счетным, ведь объединение счетного числа счетных множеств счетно.

Рисунки © Хайдар Нурлигареев.

Хайдар Нурлигареев