Повсюдність трикутника Серпінського - спектр науки

Повсюдність трикутника Серпінського

Дивні цифри, дивні форми: це, частково, робить математику такою привабливою. Ще більш дивні - і більш привабливі - це дивовижні зв’язки, характерні для математики. Раз за разом речі, які, здається, не мають нічого спільного між собою, виявляються тісно пов’язаними. Одним з моїх улюблених прикладів цього є трикутник Серпінського (малюнок нижче). Це - за термінологією Бенуа Мандельброта - фрактал: всю фігуру можна розбити на частини, які є меншими копіями цілого. Але трикутник Серпінського також пов'язаний з двокрапками кривих, трикутником Паскаля, вежами Ханоя та дивним числом 466/885, яке приблизно дорівнює 0,52655.

Польський математик Вацлав Серпінський (1882–1969) описав свій трикутник у 1915 році. Намалювати просто: розділіть рівносторонній трикутник на чотири трикутники, з’єднавши середину сторін, а потім видаліть середній трикутник. Повторіть процес для кожного із трикутників, що залишилися. Якщо ви робите це нескінченну кількість разів, кінцевим результатом буде крива, яка зустрічається в кожній зі своїх точок. Ця геометрична властивість суперечить ідеї, що такі криві спочатку вважалися "чудовиськами" та патологічними (Spektrum der Wissenschaft 3/1992, с. 72). Якщо взяти її дуже обережно, крива Серпінського зустрічається в кожній з її точок, за винятком трьох кутових точок початкового трикутника. Але навіть цю незначну відсутність чудовиська усунув Серпінскі, об'єднавши шість копій свого трикутника, щоб сформувати правильний шестикутник. Нещодавно на подив з’явилося практичне застосування цієї нескінченно зубчастої форми: антени (див. Рамку нижче).

Набагато раніше, у 1890 році, французький математик Едуар Лукас (1842–1891) відкрив математичну теорему, яка встановлює зв'язок між кривою Серпінського та знаменитим трикутником Паскаля, в якому кожне число є сумою двох чисел над ним. Ці числа також називають біноміальними коефіцієнтами. K-й запис у n-му рядку (де ми нумеруємо рядки та стовпці, починаючи з 0) - це кількість різних можливостей вибрати k з n різних речей. Лукас запитав: Які числа в трикутнику Паскаля парні, а які непарні? Дивовижна відповідь видно з першого погляду: розташування непарних біноміальних коефіцієнтів виглядає точно як дискретна версія кривої Серпінського (малюнок нижче; див. Також Spektrum der Wissenschaft 8/1993, с. 10).

Цікавим висновком є те, що майже всі біноміальні коефіцієнти є парними. Тобто, коли розмір трикутника Паскаля збільшується, відношення непарних до парних коефіцієнтів наближається до 0. Девід Сінгмастер із Лондонського університету Саут-Бенка узагальнив це твердження і довів, що для кожного натурального числа m майже всі двовічні коефіцієнти діляться на.

Трикутник Серпінського, який тоді так не називали, знову з'являється у творі Едуарда Лукаса. У 1883 році він продав знамениту головоломку Ханоїських веж під псевдонімом "Н.Клаус" (за неправильне ім'я струсив літери правильного). Гра, яку вже давно оцінили математики-аматори, складається з восьми (або менше) дисків різного розміру на трьох паличках. Корпус із трьома дисками зображений на малюнку праворуч. Спочатку диски розташовуються відповідно до розміру на одній із брусків. Тепер весь стек повинен бути переміщений диском за диском на інший стрижень, завдяки чому менший диск ніколи не повинен потрапляти під більший диск.

Загальновідомо, що розчин має рекурсивну структуру. Тобто, рішення головоломки Ханоя з n + 1 фрагментами можна легко отримати з рішення з n фрагментами. Скажімо, ви знаєте, як розгадати головоломку з трьох дисків, і вам потрібно знайти рішення з чотирьох дисків. Спочатку проігноруйте нижній диск і перемістіть три верхні диски на порожню палицю, дотримуючись - загальновідомого - рецепту розгадування головоломки з трьох дисків. Покладіть четвертий диск на іншу, тепер вільну паличку, і знову, слідуючи рецепту з трьох дисків, складіть три верхні диски на четвертий.

Ми можемо представити цю рекурсивну структуру геометрично - як і будь-яка гра, яка допускає лише кінцеву кількість позицій і переміщення між цими позиціями. Ми малюємо кут для кожного допустимого положення та ребро для кожного ходу між двома положеннями (або їх кутами), які цим ходом перетворюються в одне. Загальний результат - графік. Якщо, як у цьому випадку, поїзд також може його повернути назад, краї не є вулицями з одностороннім рухом.

Викличте графік версії з n фрагментами Hп. Як виглядає цей графік? Давай зустрінемось H3, тобто графік, який описує положення та переміщення у 3-дисковій головоломці (малюнок вище). Ми пронумеруємо диски 1, 2 і 3, причому 1 - найменший, а 3 - найбільший. Потім ми пронумеруємо смуги зліва направо на 1, 2 і 3. Припускаючи, що диск 1 знаходиться на стовпці 2, диск 2 на стовпці 1 і диск 3 на стовпчику 2. Ми можемо представити цю ігрову ситуацію за послідовністю 212, в якій Цифри вказують послідовно, на яких стержнях розташовані диски 1, 2 і 3. Той факт, що диск 3 знаходиться нижче диска 1, не одразу видно з цієї ілюстрації, але випливає з правил. Кожній позиції в головоломці з 3 дисків відповідає така тризначна послідовність. Є 3 3 = 27 позицій, оскільки кожен диск може знаходитись на будь-якому полюсі, незалежно від інших.

Які ходи дозволені з позиції 212? Найменший диск на кожній паличці повинен бути зверху. Отже, ми не можемо покласти диск 2 на стержень 2, оскільки тоді він буде лежати на меншому диску 1. Ми можемо лише витягнути з положення 212 в положення 112, 312 та 232. Графік H3 показує всі можливі ходи з усіх 27 позицій. Він складається з трьох копій графіка H2, розташовані трикутником і з’єднані трьома ребрами.

Кожен з графіків H2 поділено подібно на три частини; це наслідок рекурсивної структури розчину. Краї, які мають три зразки HConnect 2 - це саме ті ходи, в яких переміщується найбільший диск. Троє H2-графіки, у свою чергу, відповідають можливостям лише переміщення двох найменших зрізів - по одній копії для кожного можливого положення третього зрізу. Те саме стосується всіх Hn: Він складається з трьох примірників Hn-1, які розташовані у формі трикутника і з'єднані по кутах. Зі збільшенням кількості зрізів графік все більше схожий на криву Серпінського.

За допомогою графіка Hn ми можемо відповісти на всілякі запитання про вежі Ханоя. Наприклад, графік, мабуть, пов’язаний - він складається з одного шматка; тому з будь-якої позиції ми можемо досягти будь-якої іншої. Найкоротший шлях від звичайної вихідної позиції (один кут найбільшого трикутника) до звичайної цільової позиції (інший кут) - лише один поза графіка і має 2 -1 краї. Отже, загадка в 2 -1 рухається розв'язуваним.

Близько десяти років тому мюнхенський математик Андреас Гінц за допомогою Ханойських веж розрахував середню довжину найкоротшого шляху між будь-якими двома точками на кривій Серпінського. Гінц довів, що середня кількість ходів, з якими хтось потрапляє з будь-якої позиції в будь-яку іншу, є проти (466/885) 2 йде коли стає великим. З цього випливає, що середня відстань між двома точками на кривій Серпінського (вздовж кривої) становить 466/885, коли кожна сторона стартового трикутника дорівнює 1. Для шанувальників статистики Хінц також довів, що дисперсія відстані між двома випадково обраними точками на одиниці кривої Серпінського становить рівно 904808318/14448151575.

Бібліографія

Чотири зустрічі з прокладкою Серпійського. Йен Стюарт у: The Mathematical Intelligencer, том 17, випуск 1, стор. 52-64, 1995.