Zadanie

Milý denníček,
mám za sebou tretiu operáciu. A to som preukázal svoj um a prekabátil som aj „červenú čiapočku“, s ktorou som vôbec nerátal. To už som mal v sebe babičku, takže to bola hostina. Ale s horárom som si poradiť nedokázal, keďže tu nemohla o sirôtkach byť žiadna reč. Ale poviem Ti to radšej celé postupne.

Budem ti postupne rozprávať čísla. Začnem číslom \(x_{1} = 2\) a potom si každé ďalšie číslo spočítam z toho predošlého ako \(x_{n+1} = \frac{2+x_n}{1-2x_n}\). Ak narazím na čísla \(0\) alebo \(\frac{1}{2}\), skončím. Dokážte, že nikdy neskončím.

Vzorové riešenie si požičalo postup od Mariána Kovaľa.

Namiesto postupnosti, ktorú nám ponúka zadanie, uvážme \(2\) postupnosti \[\begin{align} a_{n+1}&=a_n+2\cdot b_n,\\ b_{n+1}&=b_n-2\cdot a_n\end{align}\] s počiatočnými členmi \(a_0=2\) a \(b_0=1\). Všimnime si, že členy týchto postupnosti sú celé čísla a spĺňajú, že ich podiely tvoria pôvodnú postupnosť. Skutočne, \(x_0=2=a_0/b_0\) a \[x_{n+1}=\frac{2+ x_n}{1-2x_n}=\frac{2+\frac{a_n}{b_n}}{1-2\cdot \frac{a_n}{b_n}}=\frac{a_n+2b_n}{b_n-2a_n}=\frac{a_{n+1}}{b_{n+1}}.\] Takže na to, aby sme v pôvodnej postupnosti niekedy dostali číslo \(x_k=1/2\), potrebujeme, aby pre nejaké \(k \in \mathbb{N}\) platilo, že \(2a_k=b_k\). Keďže ide o celé čísla, minimálne potrebujeme, aby \(b_k\) bolo párne. Všimnime si, že \(b_0=1\) je nepárne. Ďalej však od neho iba odrátavame \(2a_n\), čo je párne číslo, a teda parita sa zachová. Pôvodná postupnosť teda nikde nedosiahne hodnotu \(1/2\).

Aby sme ukázali, že sa ani \(0\) v pôvodnej postupnosti nevyskytne, stačí ukázať, že \(a_k\) nikdy nebude nula. Pozrime sa na zvyšky, ktoré dávajú členy postupnosti po delení piatimi. Keďže \(a_0=2\) a \(b_0=1\), tak by mohlo byť zaujímavé, ako sa menia zvyšky, ak platí \[\begin{align} a_n &\equiv 2 \pmod{5},\\ b_n &\equiv 1 \pmod{5}.\end{align}\] Potom dostávame \[\begin{align} a_{n+1} &\equiv a_n+2 b_n \equiv 2+2 \equiv 4 \pmod{5},\\ b_{n+1} &\equiv b_n-2 a_n \equiv 1-4 \equiv 2 \pmod{5}.\end{align}\] Ďalej, \[\begin{align} a_{n+2} &\equiv a_{n+1}+2 b_{n+1} \equiv 4+4 \equiv 3 \pmod{5},\\ b_{n+2} &\equiv b_{n+1}-2 a_{n+1} \equiv 2-8 \equiv 4 \pmod{5}.\end{align}\] Nevzdávame to a odhodlane počítame \[\begin{align} a_{n+3} &\equiv a_{n+2}+2 b_{n+2} \equiv 3+8 \equiv 1 \pmod{5},\\ b_{n+3} &\equiv b_{n+2}-2 a_{n+2} \equiv 4-6 \equiv 3 \pmod{5} .\end{align}\] Nakoniec, \[\begin{align} a_{n+4} &\equiv a_{n+3}+2 b_{n+3} \equiv 1+6 \equiv 2 \pmod{5},\\ b_{n+4} &\equiv b_{n+3}-2 a_{n+3} \equiv 3-2 \equiv 1 \pmod{5}.\end{align}\] Už sme spomínali, že \(a_0=2\) a \(b_0=1\). Z výpočtu uvedeného vyššie a indukcie je jasné, že hodnota \(a_k\) nikdy nebude deliteľná piatimi, a teda nemôže byť \(0\), čo sme chceli ukázať.

Diskusia

Tu môžte voľne diskutovať o riešení, deliť sa o svoje kusy kódu a podobne.

Pre pridávanie komentárov sa musíš prihlásiť.