pewna quasi-fraktalna struktura

Permutacje. Kombinacje. Wariacje. Rozmieszczanie kul w urnach. Silnie i symbole Newtona. Przeliczanie zbiorów. Funkcje tworzące. Teoria grafów.
matemix
Użytkownik
Użytkownik
Posty: 465
Rejestracja: 10 cze 2008, o 19:38
Płeć: Mężczyzna
Lokalizacja: Wrocław
Podziękował: 12 razy
Pomógł: 1 raz

pewna quasi-fraktalna struktura

Post autor: matemix »

Załóżmy, że mamy pewną matrycę pikseli \(\displaystyle{ n}\) wierszy na \(\displaystyle{ 2^n}\) kolumn. Piksele są czarne i białe.

Utwórzmy w niej pewną quasi-fraktalną strukturę która spełnia następujące warunki:

1. W każdej pod-matrycy stopnia \(\displaystyle{ k}\) tzn. \(\displaystyle{ k}\) wierszy na \(\displaystyle{ 2^k}\) kolumn zaczynając od lewego górnego rogu w kolejnych kolumnach mamy wszystkie wariacje bez powtórzeń ustawień pikseli białych i czarnych.

2. Ponad to struktura ta jest samo-podobna, tzn. każda pod-matryca \(\displaystyle{ k+1}\) wierszy na \(\displaystyle{ 2^k+1}\) kolumn (zaczynając od lewego górnego rogu) jest podobna do pod-matrycy \(\displaystyle{ k}\) wierszy na \(\displaystyle{ 2^k}\) kolumn.

Przy czym to co rozumiem tu przez podobieństwo jest najbardziej skomplikowanym punktem tej struktury. Pod-matryca stopnia \(\displaystyle{ k+1}\) jest podobna do matrycy stopnia \(\displaystyle{ k}\), jeżeli matryca stopnia \(\displaystyle{ k}\) składa się z kolumn ustawionych w takiej kolejności, że w matrycy stopnia \(\displaystyle{ k+1}\) wystarczy wykonać najmniejszą możliwą (najmniejszą możliwą - tzn., że każde inne ustawienie kolumn w matrycy stopnia \(\displaystyle{ k}\) będzie implikowało konieczność wykonania większej ilości przesunięć, niż to minimalne ustawienie) ilość przesunięć w poziomie pojedynczych pikseli barwy czarnej, aby uzyskać dokładnie ten sam rozkład barw który występuje w matrycy stopnia \(\displaystyle{ k}\). Przy czym w praktyce, aby wykonać te operacje np. w pod-matrycy stopnia \(\displaystyle{ 3}\) i \(\displaystyle{ 2}\) każdy piksel matrycy stopnia \(\displaystyle{ 3}\) trzeba podzielić w poziomie na 2 mniejsze i dodatkowo przy przesunięciu połowy takiego podzielonego piksela (bo takie właśnie przesunięcia są konieczne, aby uzyskać dokładnie ten sam rozkład co w matrycy stopnia \(\displaystyle{ 2}\)) o jedno miejsce liczyć to jako 0,5 przesunięcia.

3. Powyższe warunki nie są jednoznaczne i pozwalają na dowolność podczas tworzenia kolejnych matryc takiej struktury, dlatego tego rodzaju struktur jest nieskończenie wiele.

4. Przykłady:

10101010
01100110
10010110

oraz:

10101010
11001100
01111000


Moje pytanie dotyczy tego co dzieje się z tymi strukturami w nieskończoności, tzn. gdy stopień takiej matrycy jest nieskończony. Moja hipoteza jest następująca: w dowolnej tego typu strukturze stosunek pikseli czarnych do białych w dowolnie wybranej kolumnie (która dla matrycy nieskończonego stopnia ma nieskończenie wiele pikseli) jest zawsze mniejszy lub równy 1 - gdy jako pierwszy piksel w lewym górnym rogu postawimy piksel czarny. Czy hipoteza ta jest prawdziwa?


Przykłady - cd:

Dlaczego matryca 2 na 4:

1010
0110

jest podobna do matrycy 1 na 2:

10

Matrycę 1 na 2 można wypełnić tylko na dwa sposoby, pamiętając o założeniu, że musimy mieć wszystkie wariacje bez powtórzeń, zatem mamy dwie możliwości 10 oraz 01 (nie można brać pod uwagę np. matrycy 11). Aby uzyskać wynik 01 musimy wykonać następujące operacje w matrycy:

1010 1001 0101 0011 0011 0011
0110 0110 0110 0110 0101 0011

To jest 5 operacji. Natomiast, aby uzyskać wynik 10:

1010 1100 1100 1100
0110 0110 1010 1100

Czyli 3 operacje. Ponieważ to minimalna ilość operacji mówimy, że matryca:

1010
0110

jest podobna do matrycy:

10
ODPOWIEDZ