Anketa - Ahoj Rieškar, stalo sa ti niekedy, že si nerozumel zadaniam? Chcel by si v lete prísť na denný tábor? Sú nejaké akcie, ktoré by si chcel, aby sme robili častejšie? … Prejsť na článok
×10. príklad - Vzorové riešenie
Zadanie
Máme postupnosť čísel f_1, f_2, \dots, kde f_1 = 2 a f_2 = 3. Pre každé ďalšie f_k platí f_k = f_{k - 1} + f_{k - 2}. Začiatok postupnosti je teda 2, 3, 5, 8, 13, \dots
Zoberme si nejaké kladné celé číslo n. Toto číslo v prvom kroku nahradíme najbližším násobkom f_1 (ak sú dva násobky rovnako blízko, zoberieme ten menší). Takto získané číslo v ďalšom kroku nahradíme najbližším násobkom f_2, toto nové číslo potom najbližším násobkom f_3, a tak ďalej. Nájdite všetky čísla n, s ktorými sme mohli začínať, ak sme po nejakom počte krokov dostali číslo 0, a vysvetlite, prečo ostatné čísla nevyhovujú.
Poznámka: Číslo 0 považujeme za násobok ľubovoľného celého čísla.Vzorové riešenie
Najprv si objasnime zopár vlastností postupnosti f:
- Všetky členy postupnosti f sú kladné. Platí to preto, lebo sú kladné prvé dva, a každý ďalší je len súčtom nejakých predošlých.
- Postupnosť f rastie. Inak povedané, každý člen postupnosti f je nižší ako nasledovný. Pre prvý člen f_1 to očividne platí: 2 \lt 3. Pre akýkoľvek ďalší člen f_i to platí, pretože zo zadania vieme, že f_{i+1} = f_i + f_{i-1}, teda že nasledovný člen je súčtom f_i a nejakého iného členu f_{i-1}. Ako už vieme, každý člen je kladný, vrátane f_{i-1}. Preto nasledovný člen f_{i+1} je určite vyšší ako f_i.
- Ľubovoľný člen postupnosti f je vyšší než polovica nasledujúceho členu. Opäť to očividne platí pre prvý člen: 2 je naozaj viac než polovica z 3. Dôkaz pre vyššie členy vieme dostať z toho, že postupnosť rastie. Vezmeme nerovnosť f_i \gt f_{i-1} a postupne ju upravíme. Pripočítajme k obom stranám f_i, čím dostaneme 2\cdot f_i \gt f_i + f_{i-1}. Vidíme, že na pravej strane dostávame veľkosť členu f_{i+1}, tak ju ním nahraďme: 2\cdot f_i = f_{i+1}. Teraz už len obe strany vydelíme dvomi a máme f_i \gt \frac{f_{i+1}}{2}, čo je náš želaný výsledok.
Teraz môžeme dokončiť riešenie. Ak niekedy dostaneme nulu, tak to bude určite hneď v prvom kroku. Prečo to nemôže nastať neskôr? Predstavme si, že prvý krok už prebehol. Teda číslo, ktoré momentálne máme, je nejaký kladný násobok nejakého f_i. Teda naše číslo je určite rovné aspoň f_i. Na to, aby sme ho teraz nahradili nulou, musela by byť nula najbližším násobkom f_{i+1} (alebo aspoň na zdieľanom prvom mieste, teda rovnako blízko, ako nejaký iný násobok). Ale my vieme, že každý člen f_i je vyšší než polovica f_{i+1}. Naše číslo je určite aspoň také veľké ako tento člen, preto tiež musí byť vyššie než táto polovica, a teda je určite bližšie k f_{i+1} ako k nule. Preto sa určite nemôže stať, že nula by bola najbližším násobkom f_{i+1}.
Ostáva nám už iba zistiť, ktoré počiatočné n sa hneď v prvom kroku zmenia na 0. f_1 je rovné 2, teda hľadáme nejaké také číslo, že je rovné najviac polovici z 2 (platí rovnaká logika ako pred chvíľou, ak je naše číslo vyššie než polovica nasledovného členu, určite nebude nula jeho najbližším násobkom...). Jediné také číslo je 1, a naozaj, pre neho si ľahko overiť, že sa hneď zmení na nulu.
Odpoveď: Jediným vyhovujúcim číslom n je 1.