Zadanie 1. Zbiór Cantora

Zadanie zostało przygotowane przez Centralną Komisję Egzaminacyjną i pojawiło się w zbiorze zadań z informatyki autorstwa CKE jako zadanie nr 15.

Zbiór (fraktal) Cantora rzędu 0 jest równy odcinkowi jednostkowemu $[0;\; 1]$. Zbiór Cantora rzędu 1 uzyskujemy, dzieląc odcinek jednostkowy $[0;\; 1]$ na trzy równe części i usuwając odcinek środkowy (pozostawiając zaś jego końce). Składa się on zatem z dwóch fragmentów odcinka jednostkowego:

Ogólnie zbiór Cantora rzędu n+1 tworzymy ze zbioru Cantora rzędu n w następujący sposób: każdy odcinek zbioru Cantora rzędu n dzielimy na trzy równe części i usuwamy odcinek środkowy, pozostawiając jego końce. Zgodnie z tą regułą zbiór Cantora rzędu 2 składa się z odcinków:

R17Ti6iWZYkie

Ilustracja przedstawia serię czarnych poziomych pasków różnej długości. Pierwszy pasek jest najdłuższy, poniżej niego po lewej i prawej stronie symetrycznie są dwa krótsze paski. Pod każdym z nich po lewej i prawej stronie są - również symetrycznie - namalowane po dwa paski krótsze od znajdującego się nad nimi. Pod każdym z pasków są kolejne - po lewej i prawej stronie - po dwa krótsze paski od tego, który jest powyżej nich. Poniżej jest kolejna sekwencja pasków krótszych od znajdujących się nad nimi. Pod krótkimi paskami po lewej stronie ilustracji jest cyfra zero, czyli na początku sekwencji pasków. Na końcu sekwencji jest cyfra 1.

Zadanie 1.1

Uzupełnij tabelę, wpisując liczbę odcinków w zbiorach Cantora podanych rzędów.

Podaj ogólny wzór określający C(n), czyli liczbę odcinków w zbiorze Cantora rzędu n:

Rozwiązanie

Z każdą kolejną potęgą w zbiorze Cantora dzielimy każdy odcinek na trzy części, z czego jedną usuwamy, więc zostają nam dwie. Z jednego odcinka powstają dwa, zatem wzór na liczbę odcinków w zbiorze Cantora rzędu n wynosi:

Uzupełniona tabela powinna wyglądać następująco:

Zadanie 1.2

Zauważ, że każdy odcinek w zbiorze Cantora ustalonego rzędu ma tę samą długość. Uzupełnij tabelę, podając długość jednego odcinka w zbiorach Cantora podanych rzędów.

Podaj ogólny wzór określający długość D(n) jednego odcinka w zbiorze Cantora rzędu n:

Rozwiązanie

Z każdą kolejną potęgą w zbiorze Cantora dzielimy każdy odcinek na trzy części, z czego dwie stają się kolejnymi odcinkami. Zatem aby otrzymać długość odcinka w zbiorze Cantora o potędze n+1, musimy podzielić długość odcinka w potędze n przez 3:

Uzupełniona tabela powinna wyglądać następująco:

Zadanie 1.3

Uzupełnij listę odcinków zbioru Cantora rzędu 3, których końce zapisane są jako ułamki zwykłe nieskracalneułamki zwykłe nieskracalneułamki zwykłe nieskracalne:

Końce odcinków zbiorów Cantora można opisać w zwarty i regularny sposób w systemie trójkowymsystem trójkowysystemie trójkowym. W szczególności odcinki zbioru Cantora rzędu 1 zapisane w systemie trójkowym to $[0;\; 0,1]$, $[0,2;\; 1]$, natomiast odcinki zbioru Cantora rzędu 2 zapisane w systemie trójkowym to $[0;\; 0,01]$, $[0,02;\; 0,1]$, $[0,2;\; 0,21]$ i $[0,22;\; 1]$. Podaj odcinki zbiorów Cantora rzędu 3 zapisane w systemie o podstawie 3 (trójkowym):

Rozwiązanie

Lista odcinków zbioru Cantora rzędu 3, których końce zapisane są jako ułamki zwykłe nieskracalne:

Lista odcinków zbioru Cantora rzędu 3 zapisanego w systemie o podstawie 3 (trójkowym):

Słownik