Ацтекский бриллиант

Процесс вычисления функции высоты одной из точек разбиения ацтекского бриллианта порядка 3

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

Рангом разбиения ${\displaystyle T}$ ацтекского бриллианта на домино называется минимальное количество поворотов двух доминошек, имеющих общую длинную грань, вокруг центра их общей грани, необходимое для того, чтобы превратить разбиение в такое, где все плитки лежат горизонтально (такое разбиение, очевидно, существует только одно). Можно доказать, что такое превращение через такие преобразования всегда возможно, так что понятие ранга определено для любого разбиения ${\displaystyle T}$.[2]

Максимальный возможный ранг разбиения ацтекского бриллианта порядка ${\displaystyle n}$ достигается при разбиении, в котором все плитки ориентированы вертикально. В этом случае ранг равен ${\displaystyle {\frac {1}{6}}n(n+1)(2n+1)}$[4]

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

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

Данное определение оказывается независимо от выбора пути, а зависит только от разбиения.

Для упрощения иллюстраций и формулировки доказательств часто используется условное деление всех плиток ${\displaystyle 1\times 2}$ конкретного рассматриваемого замощения на четыре класса.[6][7] Для их описания удобно представить раскраску клеток ацтекского бриллианта по типу шахматной доски такую, что верхняя из двух самых левых клеток - чёрная. Тогда классы определяются так:

• N (north - север) - горизонтально ориентированная плитка, у которой левая клетка - чёрная;
• S (south - юг) - горизонтально ориентированная плитка, у которой левая клетка - белая;
• W (west - запад) - вертикально ориентированная плитка, у которой верхняя клетка - чёрная;
• E (east - восток) - вертикально ориентированная плитка, у которой верхняя клетка - белая.

Названия классов, как видно, соответствуют сторонам, в которых находятся клетки при двух тривиальных разбиениях (где каждая горизонталь или вертикаль - прямая линия из последовательных плиток). При иллюстрации бриллианта плитки разных классов иногда изображаются разными цветами.

При доказательстве через знакочередующиеся матрицы произвольному разбиению ацтекского бриллианта порядка ${\displaystyle n}$ ставится в соответствие матрица размера ${\displaystyle n\times n}$, элементы которой соответствуют целым точкам, сравнимым по модулю 2 и лежащим внутри бриллианта (каждая диагональ воспринимается как строка или столбец матрицы). Если такая точка принадлежит границам двух доминошек, то соответствующий элемент матрицы принимается равным -1, если трём, то 0, если четырём, то 1.

Можно доказать, что определяемые таким образом матрицы всегда будут знакочередующимися. Более того, можно доказать, что конкретную матрицу ${\displaystyle A}$ можно получить ровно из ${\displaystyle 2^{N_{+}(A)}}$ разбиений, где ${\displaystyle {N_{+}(A)}}$ - количество единиц в матрице ${\displaystyle A}$.

Аналогично, рассматривая не сравнимые по модулю 2 целые точки, лежащие внутри фигуры и на границе, и соответствующие матрицы размера ${\displaystyle (n+1)\times (n+1)}$, можно доказать, что любой такой матрице соответствует ${\displaystyle 2^{N_{-}(A)}}$ разбиений, где ${\displaystyle {N_{-}(A)}}$ - количество минус единиц в матрице ${\displaystyle A}$.

В итоге из очевидного для знакочередующихся матриц размера ${\displaystyle n\times n}$ тождества ${\displaystyle N_{+}(A)=N_{-}(A)+n}$ и полученного тождества ${\displaystyle AD(n)=\sum \limits _{A\in {\mathcal {M}}_{n+1}}{2^{N_{-}(A)}}=\sum \limits _{A\in {\mathcal {M}}_{n}}{2^{N_{+}(A)}}}$ (где ${\displaystyle {\mathcal {M}}_{n}}$ - множество всех знакочередующихся матриц порядка ${\displaystyle n}$) легко получается, что[8]

${\displaystyle AD(n)=2^{n}\sum \limits _{A\in {\mathcal {M}}_{n}}{2^{N_{-}(A)}}=2^{n}AD(n-1)=2^{n+(n-1)}AD(n-2)=\dots =2^{(1+2+\dots +n)}=2^{\frac {n(n+1)}{2}}}$

При доказательстве через паросочетания рассматривается граф ${\displaystyle G_{n}}$, вершины которого соответствуют клеткам ацтекского бриллианта порядка ${\displaystyle n}$, а рёбра проходят между вершинами, клетки которых соседствуют по горизонтали или по вертикали. Количество замощений ацтекского бриллианта порядка ${\displaystyle n}$ равно количеству совершенных паросочетаний в графе ${\displaystyle G}$.

В доказательстве для произвольного графа ${\displaystyle G=(V,E)}$ и функции весов на его рёбрах ${\displaystyle \omega :E\to {\mathbb {R} }}$ рассматривается его статистическая сумма ${\displaystyle Z(G)=\sum \limits _{M}\prod \limits _{e\in M}\omega (e)}$, где суммирование под знаком суммы ведётся по всем возможном совершенным паросочетаниям.

Основой доказательства является лемма, позволяющая вырезать из графа четыре вершины, правильным образом перестроив рёбра и веса рядом с ними, так, что статистическая сумма графа изменится на предсказуемую величину. Это возможно только если удаляемые вершины находятся в особой рёберной конфигурации с некоторыми другими четырьмя вершинами. Чтобы добиться существования большого количества таких конфигураций в рассматриваемом графе, граф ${\displaystyle G_{n}}$ можно расширить до некоторого графа ${\displaystyle {\tilde {G_{n}}}}$, правильным образом утроив вершины так, что количество паросочетаний не изменится.

Веса рёбер графа ${\displaystyle G_{n}}$ полагаются равными единице (тогда количество паросочетаний равно статистической сумме), так же как и веса графа ${\displaystyle {\tilde {G_{n}}}}$, а нетривиальные веса появляются только после применения леммы об удалении вершин. Однако в получившемся после всех возможных удалений вершин графе ${\displaystyle {\tilde {G_{n}}}^{*}}$ все веса на рёбрах равны либо ${\displaystyle 1}$, либо ${\displaystyle {\frac {1}{2}}}$, причём рёбра с весом ${\displaystyle 1}$ непременно входят в любое паросочетание. Кроме того, ${\displaystyle {\tilde {G_{n}}}^{*}}$ после отбрасывания рёбер веса ${\displaystyle 1}$ оказывается равным графу ${\displaystyle G_{n-1}}$ ацтекского бриллианта предыдущего порядка, только с уменьшенным в два раза весом каждого ребра (а в каждом паросочетании участвуют ровно ${\displaystyle n(n-1)}$ его рёбер). Это позволяет вывести рекуррентную формулу:[9]

${\displaystyle AD(n)=Z(G_{n})=Z({\tilde {G_{n}}})=2^{n^{2}}Z({\tilde {G_{n}}}^{*})=2^{n^{2}}{\frac {Z(G_{n-1})}{2^{n(n-1)}}}=2^{n}Z(G_{n-1})=2^{n}AD(n-1)}$

Ещё один способ доказательства - взаимо-однозначно сопоставить каждому разбиению ацтекского бриллианта порядка ${\displaystyle n}$ набор из ${\displaystyle n}$ непересекающихся путей Шрёдера. Тогда количество возможных разбиений оказывается равным количеству таких наборов.

Для этого достаточно отметить середины вертикальных отрезков нижней левой части границы бриллианта, а далее вести от них линии, каждый раз проводя новый отрезок симметрично относительно центра домино, в котором отрезок находится - горизонтально для горизонтально лежащих плиток и под наклоном для вертикальных плиток. Тогда, если продолжить вне бриллианта каждый путь наклонными линиями до единого уровня, то получится как раз ${\displaystyle n}$ непересекающихся путей Шрёдера (каждый путь по бриллианту гарантированно закончится на той же горизонтали, где начался).

Более того, количество ${\displaystyle H_{n}}$ таких наборов оказывается равным определителю матрицы Ганкеля, составленной из чисел Шрёдера. Рассматривая малые пути Шрёдера (то есть такие, где горизонтальные отрезки не лежат на уровне 0) и количество ${\displaystyle G_{n}}$ их наборов без пересечений (оно тоже будет выражаться матрицей Ганкеля, но для другой последовательности), можно вывести соотношения ${\displaystyle H_{n}=G_{n+1}}$ и ${\displaystyle H_{n}=2^{n}G_{n}}$, откуда легко получить рекуррентное выражение для ${\displaystyle H_{n}}$[10]:

${\displaystyle AD(n)=H_{n}=2^{n}H_{n-1}=2^{n}AD(n-1)}$

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

• в шахматной раскраске две из них - белые, а две - чёрные;
• при вырезании любых чёрной и белой клетки замощений клеток вблизи половины границы определяется однозначно, так что оставшаяся часть представляет собой ацтекский бриллиант порядка ${\displaystyle n-1}$;
• при вырезании четырёх клеток однозначно определяется ориентация всех доминошек, касающихся границы, так что оставшаяся часть представляет собой ацтекский бриллиант порядка ${\displaystyle n-2}$.

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

${\displaystyle AD(n)AD(n-2)=2AD(n-1)^{2}}$

Тем же методом можно вывести короткую формулу для частного случая производящей функции (см. ниже):

${\displaystyle AD(n;x)=(1+x)^{\frac {n(n+1)}{2}}}$

Известен алгоритм равновероятного выбора случайного разбиения бриллианта заданного размера из всех разбиений такого размера.[6][11]

Для генерации случайного разбиения размера ${\displaystyle n}$ алгоритм использует заранее сгенерированное случайное разбиение ацтекского бриллианта размера ${\displaystyle n-1}$ и специальным образом преобразует его со внесением дополнительной случайности. Таким образом, для генерации случайного разбиения размера ${\displaystyle n}$ нужно последовательно генерировать разбиения размера ${\displaystyle 1,2,\dots ,n-1,n}$.

Преобразование при переходе от размера ${\displaystyle n-1}$ к ${\displaystyle n}$ включает в себя три стадии:

1. Разрушение. Из разбиения удаляются следующие пары плиток (если таковые присутствуют):
   • плитка S, соприкасающаяся нижней гранью с клеткой типа N;
   • плитка E, соприкасающаяся правой гранью с плиткой типа W.
2. Сдвиг. Все оставшиеся плитки сдвигаются на одну клетку согласно своему типу в стандартной нотации - N вверх, S вниз, E вправо, W влево. Предшествующая стадия разрушения гарантирует, что при этом не возникнет наложений одной плитки на другую.
3. Генерация. Доказано, что в результате двух предыдущих стадий все пустые клетки в области ацтекского бриллианта размера ${\displaystyle n}$ можно разбить на квадраты размера 2x2. На стадии генерации каждый такой квадрат отдельно заполняется равновероятно либо двумя вертикальными, либо двумя горизонтальными плитками.

Примеры типичных случайных разбиений ацтекских бриллиантов порядков, 10, 15, 25 и 40, раскрашенных соответственно стандартной нотации плиток. Форма области с хаотичным поведением стремится к вписанному кругу.

Рассмотрим окружность, вписанную в квадрат, ограничивающий ацтекский бриллиант. Она отрезает от квадрата четыре угла. Оказывается, что у случайно выбираемого замощения с очень большой вероятностью почти все доминошки, попадающие в эти углы, т. е. вне этой окружности, будут "заморожены": в нижнем и верхнем углу они все будут горизонтальными, а в левом и правом — вертикальными. Напротив, поведение замощения внутри этой окружности предсказать нельзя — оно является хаотичным. Все вышесказанное составляет утверждение теоремы о полярном круге, доказанной в 1995 году У. Джокушем, Дж. Проппом и П. Шором[12][3]:

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