Ацтекский алмаз - Aztec diamond

В комбинаторный математика, Ацтекский алмаз порядка п состоит из всех квадратов квадратной решетки, центры которой (Икс,у) удовлетворить |Икс| + |у| ≤ п. Здесь п - фиксированное целое число, а квадратная решетка состоит из единичных квадратов с началом координат в качестве вершины четырех из них, так что оба Икс и у находятся полуцелые числа.^[1]

В Теорема ацтеков об алмазе заявляет, что количество мозаики домино ацтекского алмаза порядка п 2^п(п+1)/2.^[2] В теорема о полярном круге говорит, что случайная мозаика большого ацтекского алмаза имеет тенденцию застывать за пределами определенного круга.^[3]

• 

  Ацтекский алмаз четвертого порядка с 1024 мозаиками домино

• 

  Одна возможная укладка.

• 

  Ромбовидная плитка из шестиугольника, выбранного равномерно наугад, причем «замороженные» плитки изображены белым цветом. (Теорема Полярного круга.)

Обычно плитки окрашивают следующим образом. Сначала рассмотрим раскраску ромба в шахматную порядке. Каждая плитка будет покрывать ровно один черный квадрат. Вертикальные плитки, где верхний квадрат покрывает черный квадрат, окрашиваются в один цвет, а остальные вертикальные плитки в другой. Аналогично для горизонтальной плитки.

Непересекающиеся пути

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

• (1,1) когда мы находимся внизу вертикальной плитки
• (1,0) где мы являемся концом горизонтальной мозаики
• (1, -1), когда мы находимся на вершине вертикального тайла

Тогда через любую плитку мы можем получить эти пути из нашего источники нашим раковины. Эти движения похожи на Пути Шредера. Например, рассмотрим ацтекский бриллиант 2-го порядка, и после его рисования ориентированный граф мы можем обозначить это источники и раковины. Источники должны быть ${displaystyle a_ {1}, a_ {2}}$ наши источники и ${displaystyle b_ {1}, b_ {2}}$ наши раковины. На его ориентированном графе мы можем провести путь из ${displaystyle a_ {i}}$ к ${displaystyle b_ {j}}$, это дает нам матрица путей, ${displaystyle P_ {2}}$,

${displaystyle P_ {2} = {egin {bmatrix} a_ {1} b_ {1} & a_ {2} b_ {1} a_ {1} b_ {2} & a_ {2} b_ {2} end {bmatrix} } = {egin {bmatrix} 6 & 2 2 & 2 end {bmatrix}}}$

куда ${displaystyle a_ {i} b_ {j} =}$ все пути от ${displaystyle a_ {i}}$ к ${displaystyle b_ {j}}$. Количество мозаик для порядка 2 равно

Det${displaystyle (P_ {2}) = 12-4 = 8 = 2 ^ {2 (2 + 1) / 2}}$

В соответствии с Линдстрем-Гессель-Вьеннот, если мы позволим S быть набором всех наших источников и Т - множество всех наших стоков нашего ориентированного графа, тогда

Det${displaystyle (P_ {n}) =}$количество непересекающиеся пути от S до T.^[4]

Рассматривая ориентированный граф ацтекского алмаза, Эу и Фу также показали, что Пути Шредера и мозаика ацтекского алмаза в биекция.^[5] Следовательно, нахождение детерминант из матрица путей, ${displaystyle P_ {n}}$, даст нам количество плиток для ацтекского бриллианта порядка п.

Другой способ определить количество плиток ацтекского алмаза - использовать Матрицы Ганкеля больших и малых Числа Шредера,^[5] используя метод из Линдстрем-Гессель-Вьеннот опять таки.^[4] Нахождение детерминант из этих матрицы дает нам количество количества непересекающиеся пути малых и больших Числа Шредера, который в биекция с мозаиками. Маленький Числа Шредера находятся ${displaystyle {1,1,3,11,45, cdots} = {y_ {0}, y_ {1}, y_ {2}, y_ {3}, y_ {4}, cdots}}$ и большой Числа Шредера находятся ${displaystyle {1,2,6,22,90, cdots} = {x_ {0}, x_ {1}, x_ {2}, x_ {3}, x_ {4}, cdots}}$, а вообще наши два Матрицы Ганкеля будет

${displaystyle H_ {n} = {egin {bmatrix} x_ {1} & x_ {2} & cdots & x_ {n} x_ {2} & x_ {3} & cdots & x_ {n + 1} vdots & vdots && vdots x_ {n} & x_ {n + 1} & cdots & x_ {2n-1} end {bmatrix}}}$и${displaystyle G_ {n} = {egin {bmatrix} y_ {1} & y_ {2} & cdots & y_ {n} y_ {2} & y_ {3} & cdots & y_ {n + 1} vdots & vdots && vdots y_ {n} & y_ {n + 1} & cdots & y_ {2n-1} end {bmatrix}}}$

где дет${displaystyle (H_ {n}) = 2 ^ {2 (n + 1) / 2}}$ и дет${displaystyle (G_ {n}) = 2 ^ {2 (n-1) / 2}}$ куда ${displaystyle ngeq 1}$ (Также верно, что det${displaystyle (H_ {n} ^ {0}) = 2 ^ {2 (n-1) / 2}}$ где это Матрица Ганкеля подобно ${displaystyle H_ {n}}$, но началось с ${displaystyle x_ {0}}$ вместо ${displaystyle x_ {1}}$ для первой записи матрицы в верхнем левом углу).

Другие проблемы с плиткой

Рассмотрим форму, ${displaystyle 2 imes n}$ блок, и мы можем задать тот же вопрос, что и для Ацтекского Бриллианта порядка п. Поскольку это было доказано во многих статьях, мы будем ссылаться на.^[6] Позволяя ${displaystyle 2 imes n}$ форма блока обозначается ${displaystyle B_ {n}}$, то видно

Количество мозаик ${displaystyle B_ {n} = F_ {n}}$

куда ${displaystyle F_ {n}}$ это п${displaystyle ^ {th}}$ Число Фибоначчи и ${displaystyle ngeq 0}$. Понятно, что ${displaystyle B_ {0}}$ это ${displaystyle 2 imes 0}$ форма, которую можно облицовывать плиткой только в 1 сторону, никакие способы. С помощью индукция, учитывать ${displaystyle B_ {1}}$ и это просто ${displaystyle 2 imes 1}$ домино плитка где есть только ${displaystyle F_ {1} = 1}$ черепица. Предполагая количество мозаик для ${displaystyle B_ {n} = F_ {n}}$, то считаем ${displaystyle B_ {n + 1}}$. Сосредоточившись на том, как мы можем начать мозаику, у нас есть два случая. Мы можем начать с того, что наша первая плитка будет вертикальной, что означает, что у нас осталось ${displaystyle B_ {n}}$ у которого есть ${displaystyle F_ {n}}$ разные плитки. Другой способ начать укладку плитки - это положить две горизонтальные плитки друг на друга, что оставляет нам ${displaystyle B_ {n-1}}$ который имеет ${displaystyle F_ {n-1}}$ разные плитки. Сложив эти два вместе, количество мозаик для ${Displaystyle B_ {n + 1} = F_ {n} + F_ {n-1} = F_ {n + 1}}$.^[6]

Генерация действительных мозаик

Нахождение действительных мозаик ацтекского алмаза требует решения лежащей в основе набор-покрытие проблема. Позволять ${displaystyle D = {d_ {1}, d_ {2}, dots, d_ {n}}}$ быть набором домино 2X1, где каждое домино в D может быть помещено в ромб (не пересекая его границы), когда нет других домино. Позволять ${displaystyle S = {s_ {1}, s_ {2}, dots, s_ {m}}}$ быть набором 1X1 квадратов, лежащих внутри ромба, который необходимо покрыть. Два домино в пределах D могут быть найдены, чтобы покрыть любой граничный квадрат в пределах S, и четыре домино в пределах D могут быть найдены, чтобы покрыть любой неграничный квадрат в пределах S.

Определять ${displaystyle c (s_ {i}) подмножество D}$ быть набором домино, покрывающим квадрат ${displaystyle s_ {i}}$, и разреши ${displaystyle x_ {i}}$ быть индикаторной переменной такой, что ${displaystyle x_ {i} = 1}$ если ${displaystyle i ^ {th}}$ домино используется в мозаике, и 0 в противном случае. С помощью этих определений задача мозаики ацтекского ромба может быть сведена к задаче удовлетворения ограничений, сформулированной в виде двоичной целочисленной программы:

${displaystyle min sum _ {1leq ileq m} 0cdot x_ {i}}$

При условии:${displaystyle sum _ {iin c (s_ {i})} x_ {i} = 1,}$ за ${displaystyle 1leq ileq m}$, и ${displaystyle x_ {i} в {0,1}}$.

В ${displaystyle i ^ {th}}$ ограничение гарантирует, что квадрат ${displaystyle s_ {i}}$ будет покрыт одной плиткой, а набор ${displaystyle m}$ Ограничения гарантируют, что каждый квадрат будет закрыт (без отверстий в покрытии). Эта формулировка может быть решена с помощью стандартных пакетов целочисленного программирования. Могут быть созданы дополнительные ограничения для принудительного размещения определенных домино, обеспечения использования минимального количества горизонтальных или вертикально ориентированных домино или создания различных мозаик.

Альтернативный подход - применить Алгоритм Кнута X чтобы перечислить допустимые мозаики для задачи.

Источники

В проектах мозаики используется множество инструментов, но есть два полезных: GeoGebra и программа создана Джим Пропп, Грег Куперберг и Дэвид Уилсон в SageMath для подсчета мозаики фигуры.^[7] Ссылка на эту конкретную программу находится во внешних ссылках в разделе Программа тайлинга в Sage.

внешняя ссылка

• Программа плитки на Sage
• геогебра.org
• GeoGebraканал на YouTube
• Сайт координации разработки
• Вайсштейн, Эрик В. «Ацтекский бриллиант». MathWorld.

Рекомендации