Mince

Toto je ukážka úlohy, kde niečo hľadáme, nejakú množinu hodnôt.

Zadanie úlohy

V Kocúrkove majú mince v hodnotách $8$ a $20 \text{ Bk}$ (Bláznivých korún). Nájdite všetky sumy, ktoré možno pomocou nich zaplatiť, ak je dovolené aj vydávať.

Pokus o riešenie 1

$4 \text{ Bk}$ vieme zaplatiť tak, že dáme $20 \text{ Bk}$ a vydajú nám $2 \cdot 8 \text{ Bk} = 16 \text{ Bk}$. Keď už vieme zaplatiť $4 \text{ Bk}$, vieme zaplatiť všetky násobky štyroch tak, že tento proces zopakujeme. Všetky hodnoty, čo vieme zaplatiť sú teda násobky štyroch.

Rozbor riešenia

Uvedené riešenie správne ukazuje, že vieme zaplatiť zaplatiť násobky štyroch, čo je aj správne riešenie úlohy. Neukazuje však, prečo nemôžeme zaplatiť iné hodnoty. Nemôže sa nám stať, že nejako naskladáme mince a zaplatíme tak napr. $2 \text{ Bk}$.

Pokus o riešenie 2

Hodnoty oboch mincí sú deliteľné štyrmi. Sčítavaním a odčítavaním násobkov štyroch dostaneme opäť násobok štyroch. Preto všetky hodnoty, ktoré vieme zaplatiť, sú všetky násobky štyroch.

Rozbor riešenia 2

Toto riešenie zas ukazuje, prečo nevieme zaplatiť hodnoty, ktoré nie sú násobkami štyroch. Avšak neukazuje, že všetky násobky štyroch naozaj vieme zaplatiť. Čo ak niektorá hodnota, napr. $12 \text{ Bk}$, by z nejakého iného dôvodu nešla zaplatiť.

Môžeme spraviť veľmi podobnú úvahu. Hodnoty oboch mincí sú párne, preto všetky hodnoty, ktoré vieme zaplatiť, sú párne. Na základe nej by sme teraz tvrdili, že riešením úlohy sú všetky párne čísla. To však pravda nie je. Napr. $6 \text{ Bk}$ nevieme zaplatiť napriek tomu, že je to párna suma. Existuje totiž iný dôvod, prečo nejde zaplatiť – deliteľnosť štyrmi.

Vzorové riešenie

Ukážeme, že riešením úlohy sú všetky násobky štyroch.

Hodnoty oboch mincí sú deliteľné štyrmi. Sčítavaním a odčítavaním násobkov štyroch dostaneme opäť násobok štyroch. Preto hodnoty, ktoré vieme zaplatiť, musia byť deliteľné štyrmi.

Ukážeme, že všetky hodnoty, ktoré sú deliteľné štyrmi, naozaj vieme danými mincami zaplatiť. Pre nezáporné celé číslo $k$, sumu $4k \text{ Bk}$ vieme zaplatiť ako $k \cdot 20 \text{ Bk} - 2k \cdot 8 \text{ Bk}$.

Poznámky k vzorovému riešeniu

Všimnite si prehľadnú štruktúru riešenia. Dva body, ktoré potrebujeme pri tejto úlohe ukázať sú pekne vyčlenené a prehľadne napísané.

Podotkneme, že spôsob, ktorými platíme niektoré hodnoty, nie je optimálny. Napr. sumu $20 \text{ Bk}$ platíme ako $5\cdot 20 \text{ Bk} - 10 \cdot 8 \text{ Bk}$, pričom oveľa jednoduchšie je zaplatiť ju priamo jednou $20 \text{ Bk}$ mincou. Zadanie úlohy po nás chce len existenciu nejakého spôsobu, ako danú sumu zaplatiť. Preto nemusíme hľadieť na optimálne riešenie. Môžeme tak nájsť jednoduchý, jednotný systém, ako všetko zaplatiť, ktorý ľahko v riešení opíšeme. Nemusíme sa zamotávať v rozoberaní viacerých prípadov, kedy čo a ako optimálne zaplatíme.