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

Фрактал, состоящий из треугольников

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

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

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

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

Конструкции

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

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

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

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

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

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

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

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

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

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

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

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

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

Игра Хаос

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

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

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

Или проще:

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

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

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

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

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

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

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

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

Треугольник Серпинского также появляется в некоторых клеточных автоматах (таких как Правило 90 ), включая те, которые относятся к Игре жизни Конвея . Например, клеточный автомат Life-like B1/S12 при применении к одной клетке сгенерирует четыре приближения треугольника Серпинского. ^[8] Очень длинная линия толщиной в одну клетку в стандартной жизни создаст два зеркальных треугольника Серпинского. Диаграмма времени-пространства репликаторного шаблона в клеточном автомате также часто напоминает треугольник Серпинского, такой как треугольник обычного репликатора в HighLife. ^[9] Треугольник Серпинского также можно найти в автомате Улама-Уорбертона и автомате Гекс-Улама-Уорбертона. ^[10]

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

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

Если взять треугольник Паскаля со строками и раскрасить четные числа в белый цвет, а нечетные — в черный, то получится приближение к треугольнику Серпинского. Точнее, пределом при n , стремящемся к бесконечности, этого четно -раскрашенного -рядного треугольника Паскаля является треугольник Серпинского. ^[11] ${\displaystyle 2^{n}}$ ${\displaystyle 2^{n}}$

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

Башни Ханоя

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

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

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

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

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

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

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

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

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

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

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

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

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

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

История

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

Аполлоновская прокладка была впервые описана Аполлонием Пергским (III в. до н. э.) и далее проанализирована Готфридом Лейбницем (XVII в.) и является изогнутым предшественником треугольника Серпинского XX в. ^[20]

Этимология

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

Смотрите также

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

Ссылки

1. "" Прокладка Серпинского от Trema Removal"".
2. Майкл Барнсли и др. (2003), «Фракталы и суперфракталы V-переменной», arXiv : math/0312314
3. NOVA (программа общественного телевидения). Странная новая наука хаоса (эпизод). Общественный телеканал WGBH Boston. Вышел в эфир 31 января 1989 года.
4. Фельдман, Дэвид П. (2012), «17.4 Игра хаоса», Хаос и фракталы: элементарное введение , Oxford University Press, стр. 178–180, ISBN 9780199566440.
5. Прусинкевич, П. (1986), «Графические приложения L-систем» (PDF) , Труды Graphics Interface '86 / Vision Interface '86 , стр. 247–253.
6. Серпинский, Вацлав (1915). «Sur une courbe не рекламирует точку est un point de разветвления». Компет. Ренд. акад. наук. Париж . 160 : 302–305.
7. Брунори, Паола; Магроне, Паола; Лалли, Лаура Тедескини (2018-07-07), Императорский Порфирий и Золотой Лист: Треугольник Серпинского в средневековом римском монастыре, Достижения в области интеллектуальных систем и вычислений, т. 809, Springer International Publishing, стр. 595–609, doi :10.1007/978-3-319-95588-9_49, ISBN 9783319955872, S2CID  125313277
8. Рампф, Томас (2010), «Конвеевская игра «Жизнь», ускоренная с помощью OpenCL» (PDF) , Труды Одиннадцатой международной конференции по мембранным вычислениям (CMC 11) , стр. 459–462.
9. Билотта, Элеонора ; Пантано, Пьетро (лето 2005 г.), «Явление возникновения паттернов в 2D клеточных автоматах», Artificial Life , 11 (3): 339–362, doi : 10.1162/1064546054407167, PMID  16053574, S2CID  7842605.
10. Хованова, Таня; Не, Эрик; Пураник, Алок (2014), «Треугольник Серпинского и автомат Улама-Уорбертона», Math Horizons , 23 (1): 5–9, arXiv : 1408.5937 , doi : 10.4169/mathhorizons.23.1.5, S2CID  125503155
11. Стюарт, Ян (2006), Как разрезать торт: и другие математические головоломки, Oxford University Press, стр. 145, ISBN 9780191500718.
12. Ян Стюарт, «Как разрезать торт», Oxford University Press, стр. 180
13. Ромик, Дэн (2006), «Кратчайшие пути в графе Ханойской башни и конечные автоматы», SIAM Journal on Discrete Mathematics , 20 (3): 610–62, arXiv : math.CO/0310109 , doi :10.1137/050628660, MR  2272218, S2CID  8342396.
14. Фальконер, Кеннет (1990). Фрактальная геометрия: математические основы и приложения . Чичестер: John Wiley. стр. 120. ISBN 978-0-471-92287-2. Збл  0689.28003.
15. Хельмберг, Гилберт (2007), Знакомство с фракталами, Вальтер де Грюйтер, стр. 41, ISBN 9783110190922.
16. «Множество способов формирования прокладки Серпинского».
17. Шеннон, Кэтлин М.; Бардзелл, Майкл Дж. (ноябрь 2003 г.). «Закономерности в треугольнике Паскаля – с изюминкой». Сходимость . Математическая ассоциация Америки . Получено 29 марта 2015 г.
18. Джонс, Хью; Кампа, Аурелио (1993), «Абстрактные и естественные формы из итерированных функциональных систем», в Тальманн, Н. М.; Тальманн, Д. (ред.), Связь с виртуальными мирами , CGS CG International Series, Токио: Springer, стр. 332–344, doi :10.1007/978-4-431-68456-5_27
19. Уильямс, Ким (декабрь 1997 г.). Стюарт, Ян (ред.). «Мостовые Космати». Математический турист. Математический интеллектуал . 19 (1): 41–45. doi :10.1007/bf03024339. S2CID  189885713.
20. Мандельброт Б. (1983). Фрактальная геометрия природы . Нью-Йорк: WH Freeman. стр. 170. ISBN 978-0-7167-1186-5.
    Aste T, Weaire D (2008). В погоне за идеальной упаковкой (2-е изд.). Нью-Йорк: Taylor and Francis. стр. 131–138. ISBN 978-1-4200-6817-7.
21. Бенедетто, Джон; Войцех, Чая. Интеграция и современный анализ . п. 408.

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

• «Прокладка Серпинского», Энциклопедия математики , EMS Press , 2001 [1994]
• Вайсштейн, Эрик В. «Решето Серпинского». MathWorld .
• Ротемунд, Пол В.К.; Пападакис, Ник; Уинфри, Эрик (2004). «Алгоритмическая самосборка треугольников Серпинского ДНК». PLOS Biology . 2 (12): e424. doi : 10.1371/journal.pbio.0020424 . PMC  534809. PMID  15583715 .
• Удаление прокладки Серпинского от Trema в Cut-the-Knot
• Прокладка Серпинского и Ханойская башня на Cut-the-Knot
• Треугольник Серпинского, созданный в реальном времени с помощью графического процессора в формате 3D
• Пифагоровы треугольники, Вацлав Серпинский, Courier Corporation, 2003
• A067771 Количество вершин в треугольнике Серпинского порядка n. в OEIS
• Интерактивная версия игры хаос