7. príklad - Vzorové riešenie

Keď sa budeme chvíľu s príkladom hrať prídeme na to, že pre x vyhovujú možnosti 4, 5, 20. Tie vieme dostať napríklad nasledovne:

1 \xrightarrow{+4} 5 \xrightarrow{\cdot 4} 20 \xrightarrow{+4} 24 \xrightarrow{\cdot 4} 96 \xrightarrow{+4} 100,\\ 1 \xrightarrow{\cdot 5} 5 \xrightarrow{+5} 10 \xrightarrow{+5} 15 \xrightarrow{+5} 20 \xrightarrow{\cdot 5} 100,\\ 1 \xrightarrow{\cdot 20} 20 \xrightarrow{+20} 40 \xrightarrow{+20} 60 \xrightarrow{+20} 80 \xrightarrow{+20} 100.

Otázkou však zostáva, či nemôžu byť nejaké ďalšie čísla, ktoré sme prehliadli? Ako určiť o nejakých číslach, že zadaniu nevyhovujú? Prvá vec, ktorá nás môže napadnúť je veľkosť čísla. Keďže len sčitujeme a násobíme, číslo uložené v stroji bude po každom kroku väčšie a väčšie. To diskvalifikuje napríklad všetky x > 100, keďže tie už po prvom kroku prekročia náš cieľ.

Skúsme sa teda zamyslieť, aké najmenšie a najväčšie číslo vieme dostať pomocou x. Začnime tým, že si rozmyslíme, ako sa správajú operácie \cdot a +. Majme v stroji nejaké číslo a. Kedy dostaneme vynásobením x menšie číslo ako keby sme k a pripočítali x?

a \cdot x \lt a + x,\\ a \cdot (x - 1) \lt x,\\ a \lt \frac{x}{x-1} = 1 + \frac{1}{x-1}.

Ak x \geq 2 pravá strana je najviac 2 a teda a, ktoré meníme môže byť jedine 1. Inak by násobenie dalo aspoň toľko ako sčítanie. Pre x = 1 si ľahko rozmyslíme, že násobenie číslo nemení, kým pripočítavanie ho zvyšuje. Pre x = 1 teda ľahko zistíme, že najväčšie číslo, ktoré vieme dostať je 1+1+1+1+1+1 = 6. Moc malá bude už len dvojka, keďže

1 \xrightarrow{+2} 3 \xrightarrow{\cdot 2} 6 \xrightarrow{\cdot 2} 12 \xrightarrow{\cdot 2} 24 \xrightarrow{\cdot 2} 64,\\ 1 \xrightarrow{+3} 4 \xrightarrow{\cdot 3} 12 \xrightarrow{\cdot 3} 36 \xrightarrow{\cdot 3} 108 \xrightarrow{\cdot 3} 324.

Vráťme sa ešte k tým x, pre ktoré vyjdú len čísla vyššie ako 100. Najmenšie, čo vieme pomocou x dosiahnuť (už vieme, že x > 1) je

1 \xrightarrow{\cdot x} x \xrightarrow{+x} 2x \xrightarrow{+x} 3x \xrightarrow{+x} 4x \xrightarrow{+x} 5x.

Nutne teda 100 \geq 5x, čo znamená, že 20 \geq x.

Čo ďalej? Vyradili sme kopu čísel, no stále máme 18 kandidátov (od 3 po 20), z ktorých sme našli riešenie len pre 4,5,20. Po chvíli skúšania si môžeme všimnúť, že až podozrivo často je výsledné číslo násobkom x. A skutočne, ak v niektorom kroku násobíme číslom x, dostaneme násobok x. Po poslednom násobení môžeme ešte pripočítať niekoľkokrát x, no to na fakte, že výsledok je násobok x nič nezmení. Ak sme teda niekedy násobili, potrebujeme, aby 100 bolo násobkom x. To z našich možností platí len pre 4, 5, 10, 20.

Ešte je tu samozrejme možnosť, že sme nenásobili ani raz. S tým sa vysporiadame ľahko. Výsledné číslo je 1+x+x+x+x+x = 1+5x = 100, čiže x = 99:5, čo nie je celé číslo.

Posledná možnosť, o ktorej nevieme, či môže alebo nemôže byť x, je 10. Po chvíli skúšania si všimneme, že po prvom kroku dostaneme 10 alebo 11. Ak teda budeme po prvom kroku násobiť, dosiahneme 100 moc skoro, alebo stovku naopak prekročíme. Keďže je však 100 násobkom 10 násobiť niekedy musíme. Jediná možnosť je teda v prvom kroku. Jediný prípustný spôsob je teda

1 \xrightarrow{\cdot 10} 10 \xrightarrow{+10} 20 \xrightarrow{+10} 30 \xrightarrow{+10} 40 \xrightarrow{+10} 50,

čo nedáva správny výsledok.

Odpoveď: Jediné vstupy x, pre ktoré vieme dostať 100 sú 4, 5, 20.