Krtko sa rozlúčil s kráľovskou rodinou s tým, že by sa už mal vrátiť domov. Hoci už veľmi túžil po svojej mäkkej posteli, ešte sa rozhodol, že sa prejde do neďalekého mesta na trhy, aby si pohľadal nejaký suvenír. Ako sa tak prechádzal od jedného stánku k druhému, zaujal ho stánok s hrami.
Keď sa pri ňom pristavil, predajca mu hneď začal ukazovať všakovaké kartičky s historickými osobnosťami, kde každá kartička mala priradené práve jedno prirodzené číslo. Ale Krtko mal už histórie dosť, a tak sa ho spýtal, či nemá náhodou nejaké matematické kartičky. Na to mu predajca odvetil, že všetky kartičky, ktoré majú na sebe Fibonacciho čísla1 \(F_1,F_2,\dots,F_{2022}\), majú na sebe vyobrazeného matematika. Krtko sa potešil a rozhodol sa, že si ich kúpi \(2022\). Ale keď začal počítať, koľko by ho to stálo, tak zistil, že nemá dosť peňazí. Preto prišiel so záložným plánom, v ktorom si kúpi kartičky s nejakými prirodzenými číslami tak, aby všetky svoje vytúžené vedel z nich nasčítavať.
Koľko najmenej kartičiek si potrebuje Krtko kúpiť, aby vedel každé z Fibonacciho čísel \(F_1,F_2,\dots,F_{2022}\) dostať ako súčet čísel na niekoľkých (možno len jednej) z kúpených kartičiek? Krtko si môže kúpiť aj viacero kartičiek s rovnakým číslom. Pri sčítavaní však nemôže jednu konkrétnu kartičku použiť viackrát.
Fibonacciho čísla \(F_1\), \(F_2\), \(F_3\) a tak ďalej sú definované tak, že \(F_1 = 1\), \(F_2 = 1\) a všetky zvyšné Fibonacciho čísla sú určené predpisom \(F_n = F_{n-1} + F_{n-2}\) pre \(n \ge 3\).↩
Odovzdávanie
Na odovzdávanie sa musíš prihlásiť
Otázky a diskusia
Po skončení kola budete mať príležitosť na diskutovanie o riešeniach v diskusii pod vzorovým riešením.