XXIX OM - I - Zadanie 2

Zawody matematyczne:

XXIX OM, 1977-1978

Etap:

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.