XXVI - I - Zadanie 7

Zawody matematyczne:

XXVI OM, 1974-1975

Etap:

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$ .