Zadanie
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\).↩
Riešenie začneme tým, že sa pokúsime vybrať čo najmenej kartičiek tak, aby Krtko vedel vyskladať všetky súčty \(F_1,\, F_2,\, \ldots,\, F_{2022}\). Až potom sa zameriame na dôkaz toho, že to s menej kartičkami nepôjde.
Ako prvé si uvedomíme, že \(F_1 = F_2 = 1\). Číslo \(1\) nevieme dostať ako súčet menších čísel, takže potrebujeme aspoň jednu \(1\), no nie obe. Pri \(F_3 = 2\) máme dve možnosti. Buď vieme použiť dve \(1\), alebo rovno \(2\) a využiť našu jednotku na získanie väčšieho čísla. (Napríklad \(F_4 = 3 = 2 + 1\).) Druhá možnosť nám umožní nasčítať viac čísel, tak zvolíme tú. Toto však nemusí byť správny prístup. Pokojne by sa mohlo stať, že aj keď na menších hodnotách zvolíme viacero čísel, tak niekde vyššie naopak ušetríme. Zatiaľ však pokračujeme len intuitívne a to, či sa to oplatilo budeme riešiť až dodatočne.
Máme teda kartičky s číslami \(F_1 = F_2\) a \(F_3\). Vieme nasčítať aj \(F_4 = F_3 + F_2\). Ďalej nám stačí kúpiť až \(F_5\). Kartičku s \(F_5\) sme zjavne nevyužili pri získavaní \(F_4\), takže o \(F_6 = F_5 + F_4\) máme postarané. A tak ďalej. Kúpime teda kartičky s Fibonacciho číslami na nepárnych pozíciách, t. j. \(F_1,\, F_3,\, F_5,\, \ldots,\, F_{2021}\). Zvyšné (na párnych pozíciách) potom dostaneme ako súčet všetkých menších kartičiek. Pre \(F_2\) to sedí a pre \(k > 1\) máme vzťah \(F_{2k} = F_{2k - 1} + F_{2k-2}\), kde k už známemu spôsobu získania \(F_{2k-2}\) prihodíme kartičku \(F_{2k-1}\). Takto sme potrebovali \(1011\) kartičiek.
Teraz chceme nájsť nejaký dolný odhad, koľko kartičiek budeme potrebovať. V ideálnom prípade nám vyjde \(1011\) a sme hotoví. V horšom prípade nám vyjde, že by mohlo stačiť menej. Vtedy budeme musieť, buď zlepšiť náš výber kartičiek, aby ich bolo menej, alebo prísť s presnejším odhadom. S dávkou optimizmu sa pokúsime dostať k odhadu \(1011\).
Intuícia hovorí, že ak budeme potrebovať kartičiek polovicu z počtu Fibonacciho čísel, tak by niečo podobné mohlo platiť stále. Ukážeme teda, že ak na čísla \(F_1\) až \(F_n\) potrebujeme \(k\) kartičiek, tak na čísla \(F_1\) až \(F_{n+2}\) budeme potrebovať aspoň \(k+1\) kartičiek. Majme teda \(k\) kartičiek a overme, či z nich vieme vyskladať \(F_1\) až \(F_{n+2}\). Ak by to šlo, vieme ich použiť aj na \(F_1\) až \(F_n\), keďže to len vynecháme posledné dva súčty. Keďže \(k\) je minimum pre \(F_1\) až \(F_n\), určite každú kartičku použijeme aspoň na jedno z čísel. Najväčší súčet dostaneme, ak použijeme každú kartičku práve raz. Tento súčet však bude menší alebo rovný súčtu \(F_1 + F_2 + \ldots + F_n\), keďže v ňom by sme mohli kartičky využiť aj viackrát. Bude to však stačiť na zisk súčtu \(F_{n+2}\)?
Pre menšie \(n\) si všimneme, že odpoveď je nie. \(F_1 < F_3\), \(F_1 + F_2 < F_4\). Využitím definície Fibonacciho čísel dostaneme, že ak \[F_1 + F_2 + \ldots + F_m < F_{m+2},\] tak pričítaním \(F_{m+1}\) k obom stranám dostaneme \[F_1 + F_2 + \ldots + F_m + F_{m+1} < F_{m+2} + F_{m+1} = F_{m+3}.\] Táto nerovnosť teda bude platiť vždy. Na zisk súčtu \(F_{n+2}\) teda budeme potrebovať pridať \((k+1)\)-vú kartu. Zároveň \(k+1\) kariet bude stačiť, lebo ak vieme použitím našich \(k\) kariet dostať všetko od \(F_1\) po \(F_n\), pridaním \(F_{n+1}\) budeme vedieť získať \(F_{n+1}\) aj \(F_{n+2} = F_{n+1} + F_n\).
Podľa nášho výpočtu potrebujeme aspoň \(k + 1010\) kartičiek na čísla \(F_1\) až \(F_{2022}\), kde \(k\) je počet kartičiek pre \(F_1\) až \(F_2\). Ako sme spomínali už na začiatku, potrebujeme aspoň \(1\) kartičku a bude to presne \(1\) kartička, keďže \(F_1 = F_2\).
Odpoveď: Krtko si potrebuje kúpiť aspoň \(1011\) kartičiek.
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ť.