Есть одна любимая популяризаторами математики почти иконическая картинка — треугольник Серпинского. К ней прилагается много историй: про фрактальность, про самоподобие (это разные вещи), про его связь с треугольником Паскаля, или кругами Форда через функцию Минковского.
Существует достаточно неочевидный способ получения этого образа с помощью одного простого случайного процесса, который называется Chaos game
Выделим на плоскости три произвольные точки, не лежащие на одной прямой. Далее выбирем ещё одну точку x, и применим к ней многократно одно и то же преобразование:
случайным образом выберем одну из выделенных точек, и переместим точку x на середину отрезка, соединяющего выбранную точку с точкой x.
Как видите, в описанном процессе много случайного. Благодаря этому последовательность перемещений точки x не сходится к какой-то из выделенных точек, а превращается в хаотичную беготню по плоскости. И постепенно из тумана точек эффектно проявляется образ знаменитого треугольника.
Обратите внимание, точки явно избегают белых областей и выбирают для следующего случайного скачка неслучайно расположенные позиции.
А что если выделенных точек будет не три, а две? Появится ли при этом какая-то структура в подобном процессе? Нет, отрезок заполнится равномерно.
А если увеличить число выделенных точек до четырёх и сформировать из них прямоугольник? Тоже никакой структуры не проявится: получится равномерно заполняемая случайными точками фигура.
В чём же магия треугольника?
Для этого надо разобраться с описанным нами преобразованием, как с динамической системой, и выяснить структуру его аттракторов. Про аттракторы мы уже говорили несколько раньше.
Для удобства введём простые обозначения. Выделенные точки пронумеруем, а скачок в сторону точки i обозначим как Гᵢ. Греческая буква гамма выбрана оттого, что перемещение в сторону точки на половину расстояния до неё является гомотетией — хорошо известным геометрическим преобразованием.
Если мы применим преобразование Гᵢ сразу ко всем внутренним точкам треугольника образованного точками 1,2 и 3, то они образуют треугольник вдвое меньший исходного. Применение всех трёх преобразований породит три уменьшенные копии исходного множества и создаст пустую область посередине между ними. Повторное применение всех трёх преобразований ко всей полученной конфигурации вновь создаст три уменьшенные копии с новыми пустотами и так далее.
В пределе случайная последовательность из трёх возможных преобразований гомотетии будет отображать все внутренние точки во множество, которое уже не будет изменяться под действием этих преобразований — в треугольник Серпинского.
Самоподобие треугольника Серпинского и его бесконечно повторяющаяся на разных масштабах структура приводит к тому, что если применить Г, ко всем его точкам, то он уменьшится вдвое и полностью совпадет какой-то из своих третей. Бесконечность его структуры и случайность выбора выделенных вершин для гомотетии в этих рассуждениях играют ключевую роль, без этого точного совпадения не получится.
Таким образом, мы понимаем, что треугольник Серпинского — это множество, инвариантное, относительно Г. Это значит, под действием преобразования оно переходит само в себя. Обозначив множество точек треугольника Серпинского буквой S, это утверждение можно записать так: Г(S) = S. Поэтому любая точка S, независимо от того, какую из выделенных вершин использовать при этом преобразовании, вновь попадёт в это множество. Случайность в выборе вершин роли в этом не играет.
Почему же с отрезком и прямоугольником не происходит ничего интересного? Для этого надо взглянуть на образы отрезка и прямоугольника, получаемые преобразованием с использованием всех точек и убедиться в том, что они сами являются своими инвариантными множествами, поэтому никакой новой структуры мы наблюдать не будем.
Напоследок, покажу ряд красивых множеств, инвариантных относительно немного модифицированного преобразования для различного числа выделенных точек. В этом преобразовании одну и туже выделенную точку нельзя выбирать дважды.
Изображения созданы с помощью этого сайта. Здесь можно исследовать игру хаоса с тонкими настройками параметров и красивой графикой.