Zagadki są ciekawe, czasem nawet podniecające, ale dobrze jest gdy można podejrzeć zagadki rozwiązanie. Zatem dziś: rozwiązanie zagadki z poprzedniej notki, nawet jeśli nie została tam ona wyraźnie sformułowana jako zagadka. Komentarze (szczególnie Bjaba) pod poprzednią notką przybliżyły nas do rozwiązania, ale pozostał jeszcze kawałek drogi.
Przypomnę:
Mamy dwie macierze 2x2:
a = [[1,0],[0,3]]
b = [[1,2],[0,3]]
W postaci tabelkowej wyglądają tak
a:
[1 0]
[0 3]
b:
[1 2]
[0 3]
Tworzymy losowe, coraz dłuższe słowa mnożąc macierze a i b. Będę je mnożył z lewej strony. Czemu?
No bo tak, słowo wieloliterowe zapisujemy jako abaabb.... I czytamy z lewej do prawej: najpierw a, potem b, potem dwa razy a itd. No dobrze, najpierw a, ale co? Macierze zazwyczaj lubią działać na wektory. A działanie macierzy na wektor zapisujemy zazwyczaj tak, że wektor stoi po prawej stronie, np. ax, gdzie a jest macierzą zaś x wektorem. Jeśli najpierw podziałać mam a, potem podziałać mam b, to będzie to bax. A z czasem naszymi macierzami będziemy na wektory działać. Zatem lepiej już teraz umówić się, że ciąg zapisany jako a1.....a1000000 będę rozumiał jako iloczyn macierzy w odwrotnej kolejności: a1000000.....a1 .
Nasze obie macierze mają w dolnym lewym rogu zero. Wyznacznik każda z nich ma 3, więc są odwracalne. W ogólności macierze, które pod główną przekątną (tą lewa góra – prawa dół) mają same zera nazywają się macierzami górno-trójkątnymi. Odwracalne macierze górno-trójkątne tworzą grupę. Iloczyn dwóch macierzy górno-trójkątnych jest macierzą górno-trójkątną, a także odwrotność macierzy górno-trójkątnej (jeśli macierz jest odwracalna, to odwrotność istnieje) jest taką macierzą. Mnożąc więc nasze macierze pozostaniemy w grupie macierzy górno-trójkątnych.
To taka uwaga, na boku, z sednem zagadki nie mająca wiele wspólnego. Jednak kiedyś może się przydać.
Tworząc iloczyny wielu macierzy a i b, w dowolnych kolejnościach, zauważamy regularności. W lewym górnym rogu będzie zawsze 1, w prawym dolnym rogu będzie zawsze 3 w potędze równej długości słowa. Gdy słowa stają się długie, potęgi trójki stają się ogromnymi liczbami całkowitymi. Trudno dawać sobie z nimi radę (choć można, jeśli ma się cierpliwość i odpowiedni pakiet do komputera pozwalający na obliczanie z dowolnie wybraną precyzją). By tego uniknąć dobrze jest zastąpić macierze a i b macierzami „zrenormalizowalnymi”
a' = a/3
b' = b/3
Teraz
a' = [[1/3,0],[0,1]]
b' = [[1/3,2/3],[0,1]]
Mnożąc przez siebie macierze a' i b' w lewym górnym rogu będzie teraz zawsze 1/3n, gdzie n jest długością słowa, w prawym dolnym rogu będzie zawsze 1. W lewym dolnym rogu będzie zawsze 0. Jedyne co ciekawe to liczba w prawym górnym rogu.
Zapuszczam generator liczb „losowych” i generuję „przypadkowy” ciąg zer i jedynek. Wyszedł mi taki:
0,1,0,1,1,0,0,1,1,0
Interpretuję 0 jako a', 1 jako b'. Ciąg czytam od lewej do prawej, macierze mnożę od prawej do lewej. Będę miał więc takie coraz dłuższe słowa:
a'
b'a'
a'b'a'
b'a'b'a'
b'b'a'b'a'
a'b'b'a'b'a'
a'a'b'b'a'b'a'
b'a'a'b'b'a'b'a'
b'b'a'a'b'b'a'b'a'
a'b'b'a'a'b'b'a'b'a'
W prawym górnym rogu otrzymam w ten sposób taki ciąg liczb:
0
2/3
2/9
20/27
74/81
74/243
74/729
1532/2187
5906/6561
5906/19683
Wszystkie one leżą w przedziale [0,1]. Mogę je namalować – może zobaczę jakąś regułę?
Hmm... Niewiele widać. Zapuszczam więc do roboty komputer o i każę mu rachować 1 mln razy ( z generatorem losowym wybierającym a' lub b') . Trwa to ok 5 sekund. Tyle, że rysować milion punktów nie ma wielkiego sensu. Powłażą na siebie i nie się ni zobaczy. Zatem robię sztuczkę. Przyjmuję rozdzielczość 570 pikseli i dzielę odcinek [0,1] na 570 równych części. Następnie dla każdej z tych 570 części liczę jaka to część punktów z mojego miliona wpadnie do tego przedziału. Nad tym pikselem stawiam wtedy słupek o tej wysokości.
Jak powiedziałem – tak zrobiłem. Oto wynik:
A teraz, kumulatywnie, od lewej do prawej dodaję wysokości słupków i rysuję wyniki tych dodawań:
Zaraz, zaraz …. Takie obrazki już gdzieś widzieliśmy.... Zbiór Cantora? Diabelskie schody? I tak już jest, że rozwiązanie każdej ciekawej zagadki stawia nas oko w oko z zagadką kolejną.
