Kategórie:
5
6
7
8
9

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

Opravovali: ViktorB

Najprv si objasnime zopár vlastností postupnosti f:

  1. 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.
  2. 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.
  3. Ľ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.​