XXIX OM - I - Zadanie 2

Dla danej liczby naturalnej $ k>7 $ skonstruować ciąg $ S = (a_0, a_1, \ldots, a_{k-1}) $ o tej własności, że dla każdego $ i $ ($ 0 < i < k - 1 $) $ a_i $ równe liczbie wyrazów ciągu $ S $ równych $ i $.

Rozwiązanie

Dla dowolnej liczby naturalnej $ k $ znajdziemy wszystkie ciągi $ S $ spełniające warunki zadania.

Z warunków zadania wynika, że w ciągu $ S $ jest $ a_0 $ wyrazów równych $ 0 $, $ a_1 $ wyrazów równych $ 1 $, $ \ldots $ , $ a_{k-1} $ wyrazów równych $ k - 1 $ i innych wyrazów nie ma. Zatem liczba wszystkich wyrazów ciągu $ S $ jest równa $ a_0 + a_1 +  \ldots  + a_{k-1} $ i stąd

\[<br />
(1) \qquad a_0 + a_1+  \ldots  + a_{k-1} = k.<br />
\]

Z określenia ciągu $ S $ wynika, że $ a_0 \ne 0 $. Niech $ a_{i_1}, a_{i_2}, \ldots, a_{i_s} $, gdzie $ 0 = i_1 < i_2 <  \ldots  < i_s $ będą wszystkimi różnymi od zera wyrazami ciągu $ S $. Wtedy $ k - s $ wyrazów tego ciągu jest równych zero, a więc $ a_{i_0} = a_0 = k - s $ i $ a_{k-1} \geq 1 $.

Z (1) otrzymujemy, że $ a_{i_1} + a_{i_2} + \ldots + a_{i_s} = k $ i wobec tego

\[<br />
(2) \qquad a_{i_2} + a_{i_3} + \ldots + a_{i_s} = k - a_{i_1} = s.<br />
\]

Ponieważ liczby $ a_{i_2}, \ldots, a_{i_s} $ są naturalne i jest ich $ s - 1 $, więc z (2) wynika, ze $ s - 2 $ z tych liczb jest równych $ 1 $, a jedna jest równa $ 2 $.

1). Jeżeli $ a_0 = 1 $, to w ciągu $ S $ jeden wyraz jest równy $ 0 $, $ s - 2 $
wyrazy są równe $ 1 $ i jeden wyraz równy jest $ 2 $. Wobec tego $ a_2 = 1 $ i $ a_j = 0 $ dla $ j > 2 $. Wynika stąd, że $ a_1 = 2 $ (ponieważ tylko ten wyraz może być różny od $ 0 $ i $ 1 $) oraz $ a_3 = 0 $ i $ k - 1 = 3 $ (ponieważ tylko jeden wyraz ciągu $ S $ jest równy $ 0 $), Zatem $ S = (1,2,1,0) $.

Sprawdzamy bez trudu, że ten ciąg $ S $ spełnia warunki zadania.

2). Jeżeli $ a_0 = 2 $, to w ciągu $ S $ dwa wyrazy są równe $ 0 $, $ s - 2 $ wyrazy są równe $ 1 $ i dwa wyrazy są równe $ 2 $, wliczając $ a_0 $. Wobec tego $ a_2 = 2 $ i $ a_j = 0 $ dla $ j > 2 $, a także $ a_1 \leq 1 $.

Jeżeli $ a_1 = 0 $, to również $ a_3 = 0 $ i $ k - 1 = 3 $ (ponieważ nie ma wyrazów równych $ 1 $ i są dwa wyrazy równe $ 0 $). Otrzymujemy ciąg $ S = (2, 0, 2, 0) $, który oczywiście spełnia warunki zadania.

Jeżeli zaś $ a_1 = 1 $, to $ a_3 = a_4 = 0 $ i $ k - 1 =4 $ (ponieważ są dwa wyrazy równe $ 0 $). Otrzymujemy w tym przypadku ciąg $ S = (2, 1, 2, 0, 0) $ który również spełnia warunki zadania.

3). Jeżeli $ a_0 > 2 $, to w ciągu $ S $ jest $ a_0 = k - s $ wyrazów równych $ 0 $, $ s- 2 $ wyrazy równe $ 1 $ i jeden wyraz jest równy $ 2 $. Wobec tego $ a_2 = 1 $, $ a_{k-s} = 1 $ (i przy tym $ k - s > 2 $) oraz $ a_j = 0 $ dla $ j > 2 $, $ j \ne k - s $. Wynika stąd, że $ a_1 \geq 2 $. Zatem w ciągu $ S $ dokładnie dwa wyrazy są równe $ 1 $, a więc $ a_1 = 2 $ i $ s - 2 = 2 $, czyli $ s = 4 $.

Otrzymujemy więc ciąg $ S $, w którym $ a_0 = k - 4 $, $ a_1 = 2 $, $ a_2 = 1 $, $ a_{k-4} = 1 $, a pozostałe wyrazy są równe zeru. Przy tym $ k - 4 > 2 $, tzn. $ k \geq 7 $. Sprawdzamy bez trudu, że na odwrót, dla każdej liczby naturalnej $ k \geq 7 $ określony wyżej ciąg $ S $ spełnia warunki zadania.

Uwaga. Rozwiązaliśmy zadanie ogólniejsze. Udowodniliśmy, że dla $ k \geq 7 $ istnieje dokładnie jeden ciąg $ S $ spełniający warunki zadania (i skonstruowaliśmy taki ciąg), ponadto dla $ k = 4 $ istnieją dwa takie ciągi $ (2, 0, 2, 0) $ i $ (1, 2, 1, 0) $, a dla $ k = 5 $ jeden ciąg $ (2, 1, 2, 0, 0) $. Dla $ k = 2 $, $ 3 $ i $ 6 $ takich ciągów $ S $ nie ma.

Komentarze

Dodaj nową odpowiedź