XXVI - I - Zadanie 7

Niech $ Z $ będzie zbiorem wszystkich ciągów skończonych o wyrazach $ a, b, c $ i niech $ Z_1 $ będzie podzbiorem $ Z $ zawierającym dla każdego $ k $ naturalnego dokładnie jeden ciąg $ k $-wyrazowy.
Tworzymy najmniejszy zbiór $ Z_2 $ o tej własności, że $ Z_2 \supset Z_1 $ oraz, jeżeli pewien ciąg $ k $-wyrazowy należy do $ Z_1 $, to każdy ciąg $ (k+r) $-wyrazowy ($ r = 1, 2, \ldots $) powstający z tego ciągu $ k $-wyrazowego przez dopisanie ciągu $ r $-wyrazowego na początku lub na końcu, należy do $ Z_2 $.
Udowodnić, że dla każdego $ k $ istnieje w $ Z $ ciąg $ k $-wyrazowy nie należący do $ Z_2 $.

Rozwiązanie

Każdy ciąg $ n $-wyrazowy należący do $ Z_2 $ powstaje z ciągu $ (n - k) $-wyrazowego (gdzie $ 1 \leq k \leq n $) należącego do $ Z_1 $ przez dopisanie na początku lub na końcu pewnego ciągu $ k $-wyrazowego lub też jest ciągiem $ n $-wyrazowym należącym do $ Z_1 $. Liczba takich ciągów $ k $-wyrazowych jest równa $ 3^k $, ponieważ każdy wyraz ciągu może przybierać jedną z trzech wartości. Zatem liczba ciągów $ n $-wyrazowych należących do $ Z_2 $ powstających z pewnego ciągu $ (n-k) $-wyrazowego należącego do $ Z_1 $ jest nie większa niż $ 2 \cdot 3^k $. Wobec tego liczba wszystkich ciągów $ k $-wyrazowych należących do $ Z_2 $ jest nie większa niż

\[<br />
1 + \sum_{k=1}^{n-1} 2 \cdot 3^k = 1 + 2 \cdot 3 \cdot \frac{3^{n-1} - 1}{3-1} = 3^n - 2.<br />
\]

Liczba wszystkich ciągów $ n $-wyrazowych o wyrazach należących do zbioru trójelementowego jest równa $ 3^n $. Zatem dla każdej liczby naturalnej $ n $ istnieją co najmniej dwa ciągi $ n $-wyrazowe nie należące do $ Z_2 $.

Komentarze

Dodaj nową odpowiedź