L MOM - Zadanie 3

Zawody matematyczne:

L MOM, 2009

Ściśle rosnący ciąg $s_1,s_2,s_3,\dots$ , którego wyrazy są dodatnimi liczbami całkowitymi, ma tę własność, że jego podciągi

$ s_{s_1},s_{s_2},s_{s_3},\dots\qquad\text{oraz}\qquad s_{s_1+1},s_{s_2+1},s_{s_3+1},\dots $

są ciągami arytmetycznymi. Dowieść, że ciąg $s_1,s_2,s_3,\dots$ również jest ciągiem arytmetycznym.

Rozwiązanie

Sposób I

Niech $D$ będzie różnicą ciągu arytmetycznego $(s_{s_n})$ , czyli $D=s_{s_{n+1}}-s_{s_n}$ dla $n=1,2,\dots$ . Niech ponadto

$ d_n=s_{n+1}-s_n\qquad\text{dla}\quad n=1,2,\dots. $

Naszym celem jest pokazanie, że ciąg $(d_n)$ jest stały. Najpierw pokażemy, że jest to ciąg ograniczony. Zgodnie z założeniem, dla każdego $n$ zachodzi nierówność $d_n\geq1$ , a stąd wynika, że

$ \begin{split} d_n&=s_{n+1}-s_n=\underbrace{1+1+\dots+1}_{s_{n+1}-s_n\text{ jedynek}}\leq\\ &\leq d_{s_n}+d_{s_n+1}+\dots+d_{s_{n+1}-1}=s_{s_{n+1}}-s_{s_n}=D, \end{split} $

czyli $1\leq d_n\leq D$ , a więc istotnie, ciąg $(d_n)$ jest ograniczony. Z tego, że jest on ograniczony, a jego wyrazy są liczbami całkowitymi, wynika, że przyjmuje on wartość najmniejszą i największą:

$ m=\min\{d_n\colon n=1,2,\dots\}\qquad\text{oraz}\qquad M=\max\{d_n\colon n=1,2,\dots\}. $

Pozostaje do pokazania, że $m=M$ .

Zauważmy, że dla każdego $n$ takiego, że $d_n=m$ (czyli $s_{n+1}=s_n+m$ ) zachodzi

$ \begin{split} D=s_{s_{n+1}}-s_{s_n}=s_{s_n+m}-s_{s_n}&=d_{s_n}+d_{s_n+1}+\dots+d_{s_n+m-1}\leq\\ &\leq\underbrace{M+M+\dots+M}_{m\text{ składników}}=mM, \end{split} $

przy czym równość w powyższym wzorze zachodzi wtedy i tylko wtedy, gdy $d_{s_n}=d_{s_n+1}=\dots=d_{s_n+m-1}=M$ . Podobnie, dla każdego $n$ takiego, że $d_n=M$ zachodzi

$ \begin{split} D=s_{s_{n+1}}-s_{s_n}=s_{s_n+M}-s_{s_n}&=d_{s_n}+d_{s_n+1}+\dots+d_{s_n+M-1}\geq\\ &\geq\underbrace{m+m+\dots+m}_{M\text{ składników}}=Mm, \end{split} $

przy czym równość zachodzi wtedy i tylko wtedy, gdy $d_{s_n}=d_{s_n+1}=\dots=d_{s_n+M-1}=m$ . Z powyższych dwóch obserwacji wynika, że $D=Mm$ , a ponadto, jeśli $d_n=m$ , to $d_{s_n}=M$ , a jeśli $d_n=M$ , to $d_{s_n}=m$ .

Rozważmy ciąg $(n_k)$ liczb całkowitych dodatnich, określony następująco:

$ \begin{cases}n_1\text{ jest dowolną (na przykład najmniejszą) liczbą taką, że }d_{n_1}=m\\ n_{k+1}=s_{n_k}\quad\text{dla }k=1,2,\dots \end{cases} $

Ponieważ $d_{n_1}=m$ , więc $d_{n_2}=d_{s_{n_1}}=M$ , a stąd $d_{n_3}=d_{s_{n_2}}=m$ , itd.: wyrazy ciągu $(d_{n_{k+1}})=(d_{s_{n_k}})$ są na przemian równe $m$ oraz $M$ .

Zauważmy, że

$ s_n=s_1+d_1+d_2+\dots+d_{n-1}\geq1+\underbrace{1+1+\dots+1}_{n-1\text{ jedynek}}=n. $

Wynika stąd, że dla każdego $k$ zachodzi $n_{k+1}=s_{n_k}\geq n_k$ , czyli ciąg $n_k$ jest niemalejący. Zachodzi jeden z dwóch przypadków: ciąg $(n_k)$ jest ściśle rosnący albo $n_k=n_{k+1}$ dla pewnego $k$ . Jeśli dla pewnego $k$ zachodzi $n_k=n_{k+1}$ , wówczas również $d_{s_{n_k}}=d_{s_{n_{k+1}}}$ , a ponieważ jedna z tych liczb jest równa $m$ , a druga $M$ , to $m=M$ , czyli ciąg $(s_n)$ jest ciągiem arytmetycznym. Jeśli natomiast ciąg $(n_k)$ jest ściśle rosnący, to jego wyrazy są parami różne i w ciągu $(d_{s_n})$ nieskończenie wiele wyrazów jest równych $m$ (między innymi wszystkie wyrazy $d_{s_{n_k}}$ , gdzie $k$ jest parzyste) oraz nieskończenie wiele wyrazów jest równych $M$ (w tym wszystkie wyrazy $d_{s_{n_k}}$ , gdzie $k$ jest nieparzyste). Ponieważ ciągi $(s_{s_n})$ i $(s_{s_n+1})$ są ciągami arytmetycznymi oraz $d_{s_n}=s_{s_n+1}-s_{s_n}$ , więc również ciąg $(d_{s_n})$ jest arytmetyczny. Wynika stąd, że $m$ = $M$ , czyli ciąg $(s_n)$ jest ciągiem arytmetycznym.

Sposób II

Ponieważ $(s_{s_n})$ oraz $(s_{s_n+1})$ są ciągami arytmetycznymi, więc istnieją liczby $A$ , $B$ , $C$ oraz $D$ takie, że

$ s_{s_n}=A+nC\qquad\text{oraz}\qquad s_{s_n+1}=B+nD\qquad\text{dla}\quad n=1,2,\dots. $

Ciąg $(s_n)$ jest ściśle rosnący, więc dla każdego $n$ zachodzi $s_{s_n}<s_{s_n+1}\leq s_{s_{n+1}}$ , czyli

$ A+nC<B+nD\leq A+(n+1)C $

albo równoważnie $0<B-A+n(D-C)\leq C$ . Wynika stąd, że $D=C$ (czyli różnice ciągów arytmetycznych $(s_{s_n})$ oraz $(s_{s_n+1})$ są takie same) oraz $B-A\leq C$ . Jeśli $B-A=C$ , to dla każdego $n$ zachodzi równość

$ s_{s_n+1}=B+nC=A+(n+1)C=s_{s_{n+1}}, $

a ponieważ ciąg $(s_n)$ jest ściśle rosnący, więc $s_n+1=s_{n+1}$ , a zatem ciąg $(s_n)$ jest ciągiem arytmetycznym o różnicy 1. Pozostaje zatem do rozważenia jedynie przypadek, gdy $B-A<C$ .

Niech $m$ i $N$ będą liczbami spełniającymi równości $m=\min\{s_{n+1}-s_n\colon n=1,2,\dots\}=s_{N+1}-s_N$ . Wówczas

$ B-A=(s_{s_n+1}-D)-(s_{s_n}-C)=s_{s_n+1}-s_{s_n}\geq m, $

$ C=s_{s_{s_1+1}}-s_{s_{s_1}}=s_{B+C}-s_{A+C}\geq(B-A)m $

oraz

$ \begin{split} m(A-B+C-1)&=m((A+(N+1)C)-(B+NC+1))\leq\\ &\leq s_{A+(N+1)C}-s{B+NC+1}=s_{s_{s_{N+1}}}-s_{s_{s_N+1}+1}=\\ &=(A+s_{N+1}C)-(B+(s_N+1)C)=\\ &=(s_{N+1}-s_N)C+A-B-C=mC+A-B-C. \end{split} $