XXIX OM - II - Zadanie 3

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

\[<br />
(1) \qquad (a_{i_1}, a_{i_2}, \ldots, a_{i_r})<br />
\]

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

\[<br />
a_m - 1 = a_{i_1} + a_{i_2} +  \ldots  + a_{i_s},<br />
\]

gdzie $ s \leq r $. Wtedy suma wyrazów ciągu

\[<br />
(a_{i_{s+1}}, a_{i_{s+2}}, \ldots, a_{i_r}, a_m)<br />
\]

jest równa

\[<br />
(a_{i_1} + a_{i_2} + \ldots + a_{i_r})-(a_{i_1} + a_{i_2} + \ldots + a_{i_s} + a_m  = k - (a_m - 1 ) + a_m = k+1.<br />
\]

Na mocy zasady indukcji dla każdej liczby naturalnej $ k $ można więc wybrać z danego ciągu ciąg skończony o sumie wyrazów równej $ k $.

Komentarze

Dodaj nową odpowiedź