XXIX OM - II - Zadanie 3

Zawody matematyczne:

XXIX OM, 1977-1978

Etap:

Dany jest taki ciąg liczb naturalnych $(a_i)$ , że dla każdej liczby naturalnej $n$ suma tych wyrazów ciągu, które są nie większe od $n$ , jest liczbą nie mniejszą od $n$ . Udowodnić, że dla każdej liczby naturalnej $k$ można wybrać z ciągu $(a_i)$ ciąg skończony o sumie wyrazów równej $k$ .

Rozwiązanie

Zastosujemy indukcję względem $k$ . Rozpatrzmy przypadek $k = 1$ . Z założenia suma tych wyrazów danego ciągu, które są nie większe od $1$ (a więc są równe $1$ ), jest liczbą nie mniejszą od $1$ . Istnieje więc w danym ciągu wyraz równy $1$ . Wobec tego suma wyrazów ciągu jednowyrazowego złożonego z tego właśnie wyrazu jest równa $1$ .

Z kolei niech $k$ będzie ustaloną liczbą naturalną i załóżmy, że dla każdej liczby naturalnej i nie większej od $k$ z danego ciągu można wybrać ciąg skończony o sumie wyrazów równej $i$ . Udowodnimy, że z danego ciągu można wybrać ciąg skończony o sumie wyrazów równej $k + 1$ .

Na mocy założenia indukcyjnego z danego ciągu można wybrać ciąg skończony

$ (1) \qquad (a_{i_1}, a_{i_2}, \ldots, a_{i_r}) $

o sumie wyrazów równej $k$ . Niech $a_m$ będzie najmniejszym wyrazem danego ciągu, który nie występuje w ciągu (1).

Ponieważ na mocy warunków zadania suma wszystkich wyrazów danego ciągu, które nie przekraczają $k + 1$ , jest nie mniejsza od $k + 1$ , a suma wyrazów ciągu (1) jest równa $k$ , więc pewien wyraz danego ciągu nie większy od $k + 1$ nie występuje w ciągu (1). Zatem $a_m \leq k+1$ .

Jeżeli $a_m = 1$ , to suma wyrazów ciągu $(a_{i_1}, a_{i_2}, \ldots, a_{i_r}, a_m)$ jest równa $k + 1$ .

Jeżeli $a_m > 1$ , to $1 \leq a_m - 1 \leq k$ . Wobec tego na mocy założenia indukcyjnego liczba $a_m - 1$ jest sumą pewnych wyrazów danego ciągu. Wszystkie te wyrazy występują w ciągu (1), ponieważ najmniejszym wyrazem danego ciągu nie występującym w (1) jest $a_m$ . Niech