10. príklad - Vzorové riešenie

Príklad vyzerá pomerne komplikovane, tak si ho skúsme prepísať tak, aby sme lepšie videli, ako funguje. Strážca počúva pesničky, ktoré majú nejakú kvalitu -- celé číslo n. Podľa kvality pesničky, sa potom niečo udeje s jeho únavou. Začnime v prípade, že mal únavu 1. Jeho únava sa zmení na výraz

2^{3n^2+n} + n \cdot 2^{3n^2+n+1}.

Vyskytujú sa v ňom nejaké mocniny 2. V druhom bode, keď je únava väčšia ako 1, sa tiež hovorí niečo o mocninách 2. (Dokonca 4^x = 2^{2x}, takže sú to opäť len mocniny 2.) Taktiež sa tam hovorí niečo o deliteľnosti a delení, takže nemusí byť na škodu, upraviť výraz vyššie tak, aby zodpovedal nejakému súčinu, aby sme odlíšili jednotlivé delitele a pri delení upravovali len niektoré činitele. Dostaneme

2^{3n^2+n} + n \cdot 2^{3n^2+n+1} = 2^{3n^2+n}+2n \cdot 2^{3n^2+n} = 2^{3n^2+n} \cdot (1 + 2n).

Dostali sme mocninu dvoch, ktorú násobíme nejakým nepárnym číslom. To nám pomáha určiť najväčšiu mocninu 2, ktorá tento výraz delí. Bude to 2^{3n^2+n}. Keď si teda strážca vypočuje túto pesničku, odčíta sa dvojnásobok tohto čísla (ďalšia mocnina) a teda miesto (2n+1)-krát, bude naša mocnina v čísle len (2n-1)-krát.

Pozrime sa teraz na príklad všeobecnejšie. Máme nejaké číslo tvaru 2^x \cdot (2y + 1), kde x a y sú nejaké kladné celé čísla. Na to, aby bol strážcova únava 1, musia byť x = y = 0. Inak sa stane nasledovné:

1. Odčíta sa najmenšia mocnina 2, ktorá toto číslo nedelí. Ako sme povedali už vyššie 2^x násobíme nepárnym číslom, takže hľadaná mocnina bude 2^{x+1} = 2 \cdot 2^x. Dostaneme 2^x \cdot (2y + 1 - 2) = 2^x \cdot (2(y-1) + 1).
2. Únava sa vydelí číslom 4^n = 2^{2n}. Keď delíme dve mocniny s rovnakým základom, dostame mocninu, kde sme odčítali exponenty. Čiže nové číslo bude 2^{x - 2n} \cdot (2(y-1) + 1).

Môžeme si všimnúť, že strážcova únava bude kladné celé číslo, len ak y \geq 0 a x \geq 0, čo sa môže ľahko pokaziť. Keďže y sa po každej pesničke zníži o 1, máme len n pesničiek, od kedy sme mali únavu 1, na to, aby sme sa dostali späť na 1, inak strážnik zaspí. Zároveň vieme, že skôr sa y na 0 nedostane, takže potrebujeme nájsť spôsob, ako x znulovať za rovnaký čas.

Zopakujme si, čo už vieme. Ak mal strážnik únavu 1 a vypočul si pesničku kvality n, má presne n pesničiek na to, aby sa dostal späť na 1. V jeho únave 2^x \cdot (2y+1) sa za ten čas y znuluje bez ohľadu na kvalitu pesničiek. Potrebujeme teda zabezpečiť, aby sa znulovalo aj x. To začína na kvalite 3n^2 + n a po každej pesničke sa zníži o dvojnásobok kvality danej pesničky.

V riešení nás zaujíma, či sa to dá. Ľahko si všimneme, že bez ohľadu na to, či je n párne alebo nepárne, bude 3n^2 + n párne. Teda ak by sme volili pesničky moc nízkej kvality, vieme to na konci zachrániť nejakou super pesničkou, ktorá by mala kvalitu akurát na to, aby x vynulovala. Problém však môže nastať opačný. Pesničky musia byť v stúpacjúcej kvalite a keďže bola predošlá pesnička kvality n, môže sa stať, že nebudeme mať na výber a x znulujeme príliš skoro, či nebodaj s ním prejdeme do záporu. Koľko najviac teda môže byť x po n pesničkách? To sa dozvieme, keď budeme dávať najmenšie možné kvality a teda postupne n,\, n+1,\, n+2,\, \ldots,\, 2n.

2 \cdot (n+1) + 2 \cdot (n+2) + \ldots + 2 \cdot 2n = 2 \cdot ((n+1) + (n+2) + \ldots + 2n) =\\= 2 \cdot \dfrac{((n+1) + 2n) \cdot n}{2} = 3n^2 + n.

V predposlednom kroku sme použili vzorec na súčet n po sebe idúcich čísel. Môžeme vidieť, že vybratie najmenších n po sebe idúcich čísel (väčších ako n) presne sedí. Vráťme sa k úlohe v zadaní. Máme nájsť spôsob, ako strážnik dosiahne únavu 1 ľubovoľne veľakrát.

Odpoveď: Vidíme, že ak má strážca únavu 1, vie si vypočuť ľubovoľnú pesničku s kvalitou n vyššou ako predchádzajúca pesnička, a následne si vypočuť n pesničiek kvality postupne n+1,\, n+2,\, \ldots,\, 2n a vrátiť sa späť na jednotku. Toto vie zopakovať ľubovoľne veľakrát. Konkrétne funguje napríklad počúvanie pesničiek kvality postupne 1,\, 2,\, 3,\, \ldots, ako dlho chce.

Komentár

Príklad bol mimoriadne náročný, čo sa odrazilo aj na počte riešení -- našli sa len dvaja riešitelia, čo niečo poslali. Jednou z príčin mohol byť napríklad komplikovaný výraz v zadaní, či všeobecne fakt, že tento príklad sa moc nepodobá na iné v sérii. Nemusí byť potom ľahké odhadnúť ako začať.

Ako teda začať? Prísť na to, kedy je vzorec upravený do rozumného tvaru, chce veľa skúseností, no i tak nemusí byť vždy zjavné ako upravovať. Obzvlášť, ak nevieme, kam nás riešenie zavedie. Avšak to, čo sa dá spraviť vždy, je skúsiť si chovanie úlohy na malých číslach. Občas to môže byť zavádzajúce, no v tomto príklade voľby pesničiek kvality 1 a 2 nás hneď na začiatku dali späť na únavu 1. Odvážnejší mohli (napríklad s pomocou výpočtovej techniky) prísť na to, že pokračovanie 3,\, 4,\, 5,\, 6 nás opäť priviedlo na 1. V takom prípade sa dalo tipnúť, že tento postup bude fungovať, aj keď to bolo ešte nutné dokázať. Tak ako tak, dokázať, že konkrétna postupnosť niečo spĺňa, nám dáva presnejšie požiadavky, čo v úlohe hľadať a čo od nej očakávať.