Všadeprítomnosť Sierpinského trojuholníka - spektrum vedy

Všadeprítomnosť Sierpinského trojuholníka

Zvláštne čísla, zvláštne tvary: to je čiastočne to, čo robí matematiku tak príťažlivou. Ešte zvláštnejšie - a príťažlivejšie - sú prekvapivé súvislosti typické pre matematiku. Znova a znova sa ukazuje, že veci, ktoré navzájom zjavne nemajú nič spoločné, úzko súvisia. Jedným z mojich najobľúbenejších príkladov je Sierpinského trojuholník (obrázok nižšie). Je to - v terminológii Benoîta Mandelbrota - fraktál: celú postavu je možné rozdeliť na časti, ktoré sú menšími kópiami celku. Ale Sierpinského trojuholník súvisí aj s dvojbodkami zákrut, Pascalovým trojuholníkom, vežami Hanoja a zvláštnym číslom 466/885, ktoré sa zhruba rovná 0,52655.

Poľský matematik Waclaw Sierpinski (1882–1969) opísal svoj trojuholník v roku 1915. Ľahko sa kreslí: rozdelte rovnostranný trojuholník na štyri trojuholníky spojením stredu strán a potom stredový trojuholník odstráňte. Opakujte postup pre každý zo zvyšných trojuholníkov. Ak to urobíte nekonečne veľa krát, konečným výsledkom bude krivka, ktorá sa stretne v každom zo svojich bodov. Táto geometrická vlastnosť je v rozpore s myšlienkou, že takéto krivky boli pôvodne považované za „príšery“ a patologické (Spektrum der Wissenschaft 3/1992, s. 72). Ak to vezmete veľmi opatrne, Sierpinského krivka sa stretáva v každom zo svojich bodov, s výnimkou troch rohových bodov východiskového trojuholníka. Ale aj tento malý nedostatok obludnosti bol Sierpinski eliminovaný spojením šiestich kópií svojho trojuholníka a vytvorenia pravidelného šesťuholníka. Nedávno sa prekvapivo objavila praktická aplikácia tohto nekonečne zubatého tvaru: antény (pozri rámček nižšie).

Oveľa skôr, v roku 1890, francúzsky matematik Édouard Lucas (1842–1891) objavil matematickú vetu, ktorá vytvára spojenie medzi Sierpinského krivkou a Pascalovým slávnym trojuholníkom, v ktorom je každé číslo súčtom dvoch čísel nad ním. Tieto čísla sa tiež nazývajú binomické koeficienty. K-tý záznam v n-tom riadku (kde číslujeme riadky a stĺpce začínajúce na 0) predstavuje počet rôznych možností výberu k z n rôznych vecí. Lucas sa spýtal: Ktoré čísla v Pascalovom trojuholníku sú párne a ktoré nepárne? Úžasná odpoveď je viditeľná na prvý pohľad: Usporiadanie nepárnych binomických koeficientov vyzerá presne ako diskrétna verzia Sierpinského krivky (obrázok nižšie; pozri tiež Spektrum der Wissenschaft 8/1993, s. 10).

Zaujímavým dôsledkom je, že takmer všetky binomické koeficienty sú párne. To znamená, že s narastajúcou veľkosťou Pascalovho trojuholníka sa pomer nepárneho k párnemu koeficientu blíži k 0. David Singmaster z South Bank University v Londýne zovšeobecnil toto tvrdenie a dokázal, že pre každé prirodzené číslo m sú takmer všetky binomické koeficienty deliteľné m.

Sierpinského trojuholník - ktorý sa vtedy tak nehovoril - sa opäť objavuje v diele Édouarda Lucasa. V roku 1883 uviedol na trh slávnu hádanku Hanojských veží pod pseudonymom „N. Claus“ (pre nesprávne meno zatriasol písmenami toho správneho). Táto hra, ktorú už dávno ocenili amatérski matematici, sa skladá z ôsmich (alebo menej) diskov rôznych veľkostí na troch hokejkach. Puzdro s tromi diskami je zobrazené na obrázku vpravo. Disky sú spočiatku usporiadané podľa veľkosti na jednej z tyčí. Celý stoh sa má teraz presunúť disk po disku na inú tyč, pričom menší disk sa nikdy nesmie dostať pod väčší disk.

Je dobre známe, že riešenie má rekurzívnu štruktúru. To znamená, že riešenie hádanky v Hanoji s n + 1 rezmi sa dá ľahko odvodiť z riešenia s n rezmi. Povedzme, že viete, ako vyriešiť hádanku s tromi diskami, a musíte nájsť riešenie so štyrmi diskami. Najskôr ignorujte spodný disk a horné tri disky premiestnite na prázdnu palicu, pričom sa budete riadiť - dobre známym - receptom na riešenie hádanky s tromi diskami. Štvrtý disk položte na druhú, teraz voľnú hokejku, a opäť podľa receptu na tri disky naskladajte tri horné disky na štvrtý disk.

Túto rekurzívnu štruktúru môžeme znázorniť geometricky - ako každá hra, ktorá umožňuje iba konečný počet pozícií a pohybuje sa medzi nimi. Nakreslíme roh pre každú prípustnú pozíciu a hranu pre každý pohyb medzi dvoma pozíciami (alebo ich rohmi), ktoré sa týmto pohybom prevedú do jedného druhého. Celkovým výsledkom je graf. Ak to, ako v tomto prípade, môže obrátiť aj vlak, okraje nie sú jednosmerné ulice.

Vyvolajte graf verzie s n rezmi Hn. Ako vyzerá tento graf? Stretnime sa H3, t. J. Graf, ktorý popisuje polohy a pohyby v puzzle s 3 diskami (obrázok vyššie). Číslujeme disky 1, 2 a 3, pričom 1 je najmenší a 3 najväčšie. Potom číslujeme pruhy zľava doprava s 1, 2 a 3. Za predpokladu, že disk 1 je na pruhu 2, disk 2 na pruhu 1 a disk 3 na pruhu 2. Túto hernú situáciu môžeme reprezentovať postupnosťou 212, v ktorej Čísla postupne označujú, na ktorej tyči sú disky 1, 2 a 3. Skutočnosť, že disk 3 je pod diskom 1, nie je okamžite zrejmá z tejto ilustrácie, ale vyplýva z pravidiel. Každá pozícia v skladačke s 3 diskami zodpovedá takejto trojmiestnej postupnosti. Pozícií je 3 3 = 27, pretože každý disk môže byť na ľubovoľnom póle, bez ohľadu na ostatné.

Ktoré pohyby sú povolené z pozície 212? Najmenší disk na každej tyči musí byť hore. Nemôžeme teda položiť disk 2 na tyč 2, pretože by potom ležal na menšom disku 1. Z polohy 212 môžeme ťahať iba do pozícií 112, 312 a 232. Graf H3 zobrazuje všetky možné pohyby zo všetkých 27 pozícií. Skladá sa z troch kópií grafu H2 usporiadané do trojuholníka a spojené tromi okrajmi.

Každý z grafov H2 je podobne rozdelený na tri časti; je to dôsledok rekurzívnej štruktúry riešenia. Okraje, z ktorých sú tri exempláre HConnect 2 sú presne pohyby, v ktorých sa pohybuje najväčší disk. Tri H2-grafy zase zodpovedajú možnostiam pohybu iba dvoch najmenších rezov - jedna kópia pre každú možnú pozíciu tretieho rezu. To isté platí pre všetkých Hn: Skladá sa z troch kópií Hn-1, ktoré sú usporiadané do tvaru trojuholníka a spojené v rohoch. So zvyšujúcim sa počtom rezov vyzerá graf čoraz viac ako Sierpinskiho krivka.

Pomocou grafu Hn môžeme odpovedať na všetky druhy otázok o vežiach Hanoja. Napríklad graf je zjavne spojený - pozostáva z jedného kusu; takže z ktorejkoľvek polohy môžeme dosiahnuť ktorúkoľvek inú. Najkratšia cesta z obvyklej východiskovej polohy (jeden roh najväčšieho trojuholníka) do obvyklej cieľovej polohy (ďalší roh) vedie priamo po vonkajšej strane grafu a má 2 -1 hrany. Takže puzzle je v 2 -1 ťahy riešiteľné.

Asi pred desiatimi rokmi vypočítal mníchovský matematik Andreas Hinz pomocou Hanojských veží priemernú dĺžku najkratšej dráhy medzi akýmikoľvek dvoma bodmi na Sierpinského krivke. Hinz dokázal, že priemerný počet ťahov, ktorými sa človek dostane z ktorejkoľvek pozície na inú, je proti (466/885) 2 ide kedy sa stáva veľkým. Z toho vyplýva, že priemerná vzdialenosť medzi dvoma bodmi na Sierpinského krivke (pozdĺž krivky) je 466/885, keď je každá strana východiskového trojuholníka 1. Pre fanúšikov štatistík Hinz tiež dokázal, že rozptyl vzdialenosti medzi dvoma náhodne vybranými bodmi na jednotkovej Sierpinskiho krivke je presne 904808318/14448151575.

Bibliografia

Štyri stretnutia s tesnením Sierpi´nski. Autor: Ian Stewart v: Mathematical Intelligencer, zväzok 17, vydanie 1, s. 52 - 64, 1995.