Треугольник Серпинского

Треугольник Серпинского

Генерируется с использованием случайного алгоритма

логике: первые 16 союзов лексикографически Треугольник Серпинского в упорядоченных аргументов. Столбцы, интерпретируемые как двоичные числа, дают 1, 3, 5, 15, 17, 51... (последовательность A001317 в OEIS ).

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

Конструкции

Существует много различных способов построения треугольника Серпинского.

Удаление треугольников

Треугольник Серпинского можно построить из равностороннего треугольника путем многократного удаления треугольных подмножеств:

1. Начните с равностороннего треугольника.
2. Разделите его на четыре равных равносторонних треугольника меньшего размера и удалите центральный треугольник.
3. Повторяйте шаг 2 с каждым из оставшихся меньших треугольников бесконечно.

Эволюция треугольника Серпинского

Каждый удаленный треугольник ( трема ) топологически множеством является открытым . Этот процесс рекурсивного удаления треугольников является примером правила конечного подразделения .

Сокращение и дублирование

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

1. Начните с любого треугольника на плоскости (подойдет любая замкнутая ограниченная область на плоскости). Канонический треугольник Серпинского представляет собой равносторонний треугольник с основанием, параллельным горизонтальной оси (первое изображение).
2. Уменьшите треугольник до ⁠ 1/2 ​ ⁠ и высоты ⁠ 1/2 ширины, сделайте три копии и расположите три сморщенных треугольника так , . ⁠ чтобы каждый треугольник касался двух других треугольников в углах (изображение 2) Обратите внимание на появление центрального отверстия, поскольку три сморщенных треугольника между собой могут покрывать только ⁠ 3/4 ⁠ площади . оригинала (Дырки — важная особенность треугольника Серпинского.)
3. Повторите шаг 2 с каждым из меньших треугольников (изображение 3 и так далее).

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

Итерация от квадрата

Настоящий фрактал — это то, что будет получено после бесконечного числа итераций. Более формально его описывают в терминах функций на замкнутых множествах точек. Если мы обозначим d _A расширение в раз ⁠ 1/2 относительно точки A, то треугольник Серпинского с ⁠ углами A , B и C является фиксированным множеством преобразования ⁠ $d_{\mathrm {A} }\cup d_{\mathrm {B} }\cup d_{\mathrm {C} }$⁠ .

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

Игра Хаос

Анимированное создание треугольника Серпинского с помощью игры хаоса.

Если взять точку и применить к ней каждое из преобразований d _A , d _B и d _C случайным образом, полученные точки будут плотными в треугольнике Серпинского, поэтому следующий алгоритм снова будет генерировать к нему сколь угодно близкие приближения:

Начните с обозначения точек p ₁ , p ₂ и p ₃ как углов треугольника Серпинского и случайной точки v ₁ . Установить v _{n +1} = ⁠ 1/2 от v ⁠ ( v _n + p _{r n} ) , где n _— случайное число 1, 2 или 3. Нарисуйте точки v ₁ до r _∞ . Если первая точка v ₁ была точкой треугольника Серпинского, то все точки v _n лежат на треугольнике Серпинского. Если первая точка v ₁ , лежащая внутри периметра треугольника, не является точкой треугольника Серпинского, ни одна из точек v _n не будет лежать на треугольнике Серпинского, однако они сойдутся на треугольнике. Если v ₁ находится вне треугольника, единственный способ, которым v _n приземлится на настоящий треугольник, - это если v _n находится на том, что было бы частью треугольника, если бы треугольник был бесконечно большим.

Или проще:

1. Возьмите три точки на плоскости, чтобы образовать треугольник.
2. Случайным образом выберите любую точку внутри треугольника и считайте это своей текущей позицией.
3. Случайным образом выберите любую из трех вершинных точек.
4. Переместитесь на половину расстояния от вашего текущего положения до выбранной вершины.
5. Постройте текущую позицию.
6. Повторите с шага 3.

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

Конструкция наконечника прокладки Серпинского

Конструкция наконечника прокладки Серпинского

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

1. Начните с одного сегмента линии на плоскости.
2. Несколько раз замените каждый сегмент кривой тремя более короткими сегментами, образуя углы 120 ° на каждом стыке между двумя последовательными сегментами, при этом первый и последний сегменты кривой либо параллельны исходному сегменту линии, либо образуют с ним угол 60 °.

На каждой итерации эта конструкция дает непрерывную кривую. В пределе они приближаются к кривой, которая очерчивает треугольник Серпинского одним непрерывным направленным (бесконечно извилистым) путем, который называется стрелкой Серпинского . Фактически, целью оригинальной статьи Серпинского 1915 года было показать пример кривой (кривой Кантора), как об этом свидетельствует само название статьи.

Клеточные автоматы

Треугольник Серпинского также появляется в некоторых клеточных автоматах (таких как Правило 90 ), в том числе в тех, которые относятся к «Игре жизни» Конвея . Например, Life-like клеточный автомат B1/S12 при применении к одной ячейке будет генерировать четыре аппроксимации треугольника Серпинского. Очень длинная линия толщиной в одну клетку в обычной жизни создаст два зеркальных треугольника Серпинского. Временно-пространственная диаграмма шаблона репликатора в клеточном автомате также часто напоминает треугольник Серпинского, например, у обычного репликатора в HighLife. Треугольник Серпинского также можно найти в автомате Улама-Уорбертона и автомате Хекс-Улама-Уорбертона.

Треугольник Паскаля

Приближение пятого уровня треугольника Серпинского, полученное заштриховкой первых двух ⁵ (32) уровни треугольника Паскаля белые, если биномиальный коэффициент четный, и черные в противном случае

Если взять треугольник Паскаля с $2^{n}$ строки и цвета: четные числа белыми, а нечетные черными, результат является приближением к треугольнику Серпинского. Точнее, предел при n, приближающемся к бесконечности, этого цвета четности . $2^{n}$Треугольник Паскаля - это треугольник Серпинского.

Поскольку доля черных чисел стремится к нулю с увеличением n , следствием этого является то, что доля нечетных биномиальных коэффициентов стремится к нулю, когда n стремится к бесконечности.

Башни Ханоя

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

Характеристики

Для целого числа измерений $d$, при удвоении стороны объекта, $2^{d}$ создаются его копии, т.е. 2 копии для 1-мерного объекта, 4 копии для 2-мерного объекта и 8 копий для 3-мерного объекта. В треугольнике Серпинского удвоение его стороны создает три его копии. Таким образом, треугольник Серпинского имеет хаусдорфову размерность. ${\tfrac {\log 3}{\log 2}}\approx 1.585$, что следует из решения $2^{d}=3$ для $d$.

Площадь треугольника Серпинского равна нулю (по мере Лебега ). Площадь, оставшаяся после каждой итерации, равна ${\tfrac {3}{4}}$ площади из предыдущей итерации, а бесконечное количество итераций приводит к тому, что площадь приближается к нулю.

Точки треугольника Серпинского имеют простую характеристику в барицентрических координатах . Если точка имеет барицентрические координаты $(0.u_{1}u_{2}u_{3}\dots ,0.v_{1}v_{2}v_{3}\dots ,0.w_{1}w_{2}w_{3}\dots )$, выраженное в виде двоичных чисел , то точка находится в треугольнике Серпинского тогда и только тогда, когда $u_{i}+v_{i}+w_{i}=1$ для всех $i$.

Обобщение на другие модули

Обобщение треугольника Серпинского также можно создать с использованием треугольника Паскаля, если другой модуль $P$ используется. Итерация $n$ можно построить, взяв треугольник Паскаля с $P^{n}$ строки и раскраски чисел по их значению по модулю $P$. Как $n$ приближается к бесконечности, образуется фрактал.

Тот же фрактал можно получить, разделив треугольник на мозаику. $P^{2}$ аналогичные треугольники и удаление перевернутых треугольников из оригинала, а затем повторение этого шага для каждого меньшего треугольника.

И наоборот, фрактал также можно создать, начав с треугольника, продублировав его и расположив ${\tfrac {n(n+1)}{2}}$ новых фигур в той же ориентации в более крупный подобный треугольник с соприкасающимися вершинами предыдущих фигур, а затем повторяя этот шаг.

Аналоги в высших измерениях

Рекурсия пирамиды Серпинского (8 шагов)

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

Тетрикс, построенный из исходного тетраэдра с длиной стороны $L$ обладает тем свойством, что общая площадь поверхности остается постоянной на каждой итерации. Начальная площадь поверхности тетраэдра (итерация-0) с длиной стороны $L$ является $L^{2}{\sqrt {3}}$. Следующая итерация состоит из четырех копий с длиной стороны ${\tfrac {L}{2}}$, поэтому общая площадь равна ${\textstyle 4{\bigl (}{\tfrac {L}{2}}{\bigr )}^{2}{\sqrt {3}}=L^{2}{\sqrt {3}}}$ снова. Последующие итерации снова увеличивают количество копий в четыре раза и уменьшают длину стороны вдвое, сохраняя общую площадь. При этом объем строительства на каждом этапе уменьшается вдвое и поэтому приближается к нулю. Предел этого процесса не имеет ни объема, ни поверхности, а, подобно прокладке Серпинского, представляет собой сложносвязанную кривую. Его хаусдорфова размерность равна ${\textstyle {\tfrac {\log 4}{\log 2}}=2}$; здесь «логарифм» обозначает натуральный логарифм , числитель — логарифм количества копий фигуры, сформированной из каждой копии предыдущей итерации, а знаменатель — логарифм коэффициента, на который эти копии уменьшены по сравнению с предыдущей итерация. Если все точки проецируются на плоскость, параллельную двум внешним ребрам, они точно заполняют квадрат с длиной стороны ${\tfrac {L}{\sqrt {2}}}$ без перекрытия.

Анимация вращающегося тетрикса 4-го уровня, показывающая, как некоторые ортогональные проекции тетрикса могут заполнять плоскость — в этом интерактивном SVG перемещайтесь влево и вправо по тетриксу, чтобы повернуть 3D-модель.

История

Вацлав Серпинский описал треугольник Серпинского в 1915 году. Однако подобные узоры уже появляются как распространенный мотив инкрустированной каменной кладки в косматском стиле 13-го века .

Аполлоническая прокладка была впервые описана Аполлонием Пергским (3 век до н.э.) и далее проанализирована Готфридом Лейбницем (17 век) и является изогнутым предшественником треугольника Серпинского 20-го века.

Этимология

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

См. также

• Аполлоническая прокладка , набор взаимно касающихся кругов с той же комбинаторной структурой, что и треугольник Серпинского.
• Список фракталов по размерности Хаусдорфа
• Ковер Серпинского , еще один фрактал, названный в честь Серпинского и образованный путем многократного удаления квадратов из большего квадрата.
• Triforce — реликвия из Legend of Zelda . серии

Внешние ссылки

• «Прокладка Серпинского» , Математическая энциклопедия , EMS Press , 2001 [1994]
• Вайсштейн, Эрик В. «Решето Серпинского» . Математический мир .
• Ротемунд, Пол В.К.; Пападакис, Ник; Уинфри, Эрик (2004). «Алгоритмическая самосборка треугольников ДНК Серпинского» . ПЛОС Биология . 2 (12): е424. doi : 10.1371/journal.pbio.0020424 . ПМК   534809 . ПМИД   15583715 .
• Прокладка Серпинского от Trema Removal в кратчайшие сроки
• Прокладка Серпинского и Ханойская башня в разрубке
• Графический процессор в реальном времени сгенерировал треугольник Серпинского в 3D
• Треугольники Пифагора , Вацлав Серпинский, Courier Corporation, 2003 г.
• A067771 Число вершин в треугольнике Серпинского порядка n. в OEIS
• Интерактивная версия игры хаоса