1. Potiaže s peniazmi vzorové riešenie

Dano čerstvo zmaturoval. Od septembra sa chystá nastúpiť na matfyz, kde bude študovať informatiku a popri tom vedúcovať KSP aj PRASK. Počas prázdnin však chcel zažiť niečo nové. Zbalil si teda svoj modrý batôžtek a vybral sa stopom do Absurdistanu – krajiny neobmedzených možností.

V Absurdistane totiž máločo funguje tak akoby malo a ľudia sú zvyčajne jednoduchšieho charakteru. Šikovní junáci ako Dano teda vedia rýchlo spraviť dieru do sveta. Čo bolo v skutočnosti presne to, čo Dano spravil ako prvé, keď do Absurdistanu dorazil. Zobral do ruky svoj verný rýľ a vykopal dieru. Keď sa ho okolo idúci občan spýtal, prečo to spravil, Dano mu vysvetlil, že to preto, aby sa mohol do tej diery postaviť a vyzerať nižšie. Nižším ľuďom totiž zvyšní viac dôverujú. A okolo idúci občan mu uveril.

Netrvalo dlho a Dano v jame si získal dôveru všetkých občanov Absurdistanu. Túto dôveru následne premenil na politický kapitál a onedlho už sedel v ministerskej stoličke. Bohužiaľ, postaviť sa z nej nemohol, lebo potom by bol vyšší ako zvyšní ľudia a to by mu už nikto neveril. Dano sa stal ministrom financií v Absurdistane.

Úloha

Byť ministrom financií však nebolo také jednoduché. Dano veľmi rýchlo pochopil, aká problématická je menová politika Absurdistanu. Každá mena používa niekoľko platidiel, mincí alebo bankoviek rôznych nominálnych hodnôt, pre jednoduchosť ich však volajme dokopy mince. V rámci tohto zadania je teda v poriadku povedať, že na Slovensku používame 20 eurovú mincu. Sada mincí je navyše dobrá ak spĺňa nasledovné dve vlastnosti.

1. Majme neobmedzený počet mincí každého druhu. Pomocou týchto mincí vieme zaplatiť ľubovoľnú celočíselnú kladnú sumu peňazí.
2. Majme neobmedzený počet mincí každého druhu. Ak pri platení ľubovoľnej sumy postupujeme tak, že vždy vyberieme mincu s najväčšou hodnotou, ktorá nepresahuje sumu, ktorú máme ešte zaplatiť, na zaplatenie použijeme najmenší možný počet mincí.

Napríklad euro spĺňa obe tieto vlastnosti. Pomocou euromincí vieme platiť všetky celočíselné sumy peňazí. A dodržiac vyššie uvedený postup použijeme aj najmenší počet mincí. Zoberme si napríklad, že chceme zaplatiť sumu 34 euro. Najväčšia minca (opäť pripomínam, že pod pojmom minca rozumieme mince aj bankovky), ktorá sa do 34 zmestí je 20 eurová bankovka. Po jej použití nám ostáva zaplatiť 14 euro. Opäť najväčšia minca, ktorá je nanajvýš takto veľká je 10 eurovka, použijeme aj tú. Na zaplatenie zvyšných 4 eur potom použijeme najskôr 2 eurovú mincu, a potom opäť 2 eurovú mincu. Dokopy sme teda zaplatili \(20 + 10 + 2 + 2 = 34\) peňazí a použili sme 4 mince. To je naozaj najmenší počet mincí, ktoré sme mohli použiť. Túto sumu sme mohli zaplatiť aj ako \(20 + 5 + 5 + 2 + 1 + 1\), vtedy by sme však použili až 6 mincí.

Podúloha a. (2 body)

Nie každá sada mincí však musí mať tieto dve vlastnosti. Navrhnite sadu mincí, ktorá poruší obe podmienky. To znamená, že sa ňou nebudú dať zaplatiť všetky celočíselné sumy peňazí a existuje aspoň jedna hodnota \(S\), pri ktorej platení opakovaním použitím najväčšej možnej mince nepoužijeme najmenší počet mincí.

K obom pravidlám uveďte aj príklad, v ktorom daná podmienka nie je splnená. V druhom prípade to znamená, že ukážete, že pri platení zvolenej sumy \(S\) uvedeným postupom je nutné použiť viac mincí ako pri platení iným spôsobom (vydávanie nie je dovolené).

Navrhnúť sadu mincí znamená určenie ich nominálnych hodnôt. Môžete napríklad povedať, že vaše mince majú hodnotu \(1\), \(2\) a \(4\). Takáto sada však spĺňa obe podmienky.

Podúloha b. (4 bodov)

Ani platenie v Absurdistane však nie je jednoduché. Ich mince majú totiž nasledovné hodnoty: 1, 4, 7 a 19. Niet preto divu, že pri platení nastávajú zmätky. Ktovie, ktoré hodnoty sa vôbec dajú zaplatiť a koľko najmenej mincí pri tom použiť. O tomto probléme sa Dano dozvedel, keď k nemu ráno prišiel človek a spýtal sa ho: “Koľko najmenej mincí mám použiť na zaplatenie sumy 1?”. Hneď potom však prišiel druhý a spýtal sa to isté, akurát pre sumu 2. A takto to postupne pokračovalo až do obeda.

Dano sa preto rozhodol vydať brožúrku, v ktorej bude vysvetlené, koľko najmenej mincí je potrebných na zaplatenie všetkých súm, postupne od 1 po 20. Pre každú z týchto hodnôt určite, koľko najmenej mincí je potrebných na jej zaplatenie.

Zoberte si sadu mincí, ktorú ste navrhli v podúlohe a. Pre každú z hodnôt 1 až 20 zistite, koľko najmenej mincí je potrebných na jej zaplatenie.

V oboch prípadoch uvažujte stav, v ktorom máte z každej mince k dispozícii neobmedzene veľa kusov a vydávanie nie je povolené.

Podúloha c. (5 bodov)

Dano sa rozhodol, že zmení nominálne hodnoty mincí v Absurdistane. Je mu však jasné, že ho potom čaká odpovedanie na všetky tie otázky znovu. A čo keď sa rozhodne zmeniť hodnoty viackrát? Zišiel by sa mu postup, ktorým by tieto hodnoty vedeli vypočítať všetci občania Absurdistanu.

Predstavte si, že máte zadanú hodnotu \(n\) rôznych mincí. Táto sada môže, ale nemusí spĺňať vyššie uvedené podmienky. Navyše máte všetkých mincí neobmedzene veľa. Popíšte postup, ktorým by ste vedeli vypočítať, koľko najmenej mincí je potrebných na zaplatenie všetkých súm od 1 po \(S\). Tento postup by mal byť všeobecný a mal by fungovať aj pre väčšie hodnoty \(n\) a \(S\) (napríklad 500).

Podúloha d. (4 bodov)

Nastal problém. V Absurdistane fungujú s novou sadou \(n\) mincí rôznych hodnôt. Dve z týchto mincí sú špeciálne a majú hodnoty \(x\) a \(y\). Čím sú špeciálne? Na minci \(x\) je Danova podobizeň, na minci \(y\) je podobizeň aktuálneho premiéra. Dana majú všetci radi, lebo je nižší ako oni a mincu \(x\) všetci radi používajú. Naopak, premiéra nemá nikto rád, lebo sa týči nad nimi, a mincu \(y\) ľudia priam zahadzujú do koša. V krajine je teda v obehu oveľa viac mincí \(x\) ako \(y\) a to nie je dobré.

Dano preto vydal nové nariadenie. Podľa neho je nutné pri platení ľubovoľnej sumy použiť aspoň toľko mincí \(y\) ako mincí \(x\). To znamená, že nemôžete pri platení použiť 2 mince \(x\) a iba jednu mincu \(y\), bez ohľadu na to, akú sumu platíte a aké zvyšné mince ste použili.

Danova brožúrka a jeho postup však s takýmto niečom nepočítali. Ako sa dá upraviť postup z podúlohy c. tak, aby dodržiaval nové pravidlo? Popíšte teda postup, ktorý pre všetky sumy od 1 až \(S\) vypočíta, aký najmenší počet mincí je potrebný na ich zaplatenie s dodržaním nového pravidla.