2. Kôpka Mincí on the Stôl vzorové riešenie

Keď začíname riešiť takúto úlohu, je dobré uvedomiť si, čo očakávame na konci, keď riešenie dopíšeme. Zvyčajne, keď sa pýtame na to, pre ktoré \(n\) má niečo platiť, potrebujeme ukázať, prečo to pre niektoré \(n\) platí a pre žiadne iné nie. V tomto prípade si za takúto otázku môžeme zvoliť to, pre aké \(n\) má víťaznú stratégiu ten, kto je práve na ťahu – či už ho budeme volať Adam alebo Milan, to je nám vo všeobecnosti jedno.

V úlohách ako táto je dobrý nápad skúsiť zopár jednoduchých prípadov, aby sme zistili, čo dostaneme, napr. ak je \(n = 1,\, 2,\, 3,\,4\, \dots\) (netreba to však preháňať). Následne je vhodné zamyslieť sa nad tým, na aké skupiny sa dajú prirodzené čísla rozdeliť, často sa totiž stáva, že vlastnosť, ktorú chceme ukázať majú len prvočísla, párne či nepárne čísla alebo také, ktoré dávajú zvyšok 4 po delení deviatimi, a podobne.

Väčšina z vás začala presne takto – vyskúšala, či je možné mať víťaznú stratégiu pre \(n = 2,\, 3,\, 4,\, \dots\) Ak to urobíme, zistíme, že pre párne \(n\) zvíťazí ten, čo je na ťahu, v tomto prípade Adam, zatiaľ čo v prípade, že \(n\) je nepárne, zvíťazí jeho súper, ak teda obaja rozmýšľajú racionálne. To ale nie je všetko, treba ukázať, prečo to tak je.

Prečo teda Adam vyhrá pri párnom \(n\)? Ak má Adam na stole párny počet mincí, dokáže z neho vždy spraviť nepárny (napr. odoberie jednu), ale aj párny (napr. odoberie dve), okrem prípadu, kedy tam sú dve mince, vtedy má len jednu možnosť – vezme jednu z nich a vyhral. Avšak, keď je na stole nepárny počet mincí, po ďalšom ťahu bude tento počet naisto párny. Prečo? Pretože nepárne číslo \(n\) nemôže mať párnych deliteľov. Ak by malo, muselo by obsahovať vo svojom prvočíselnom rozklade dvojku, a teda by muselo byť párne. A je ľahké ukázať, že rozdiel dvoch nepárnych čísel bude vždy párny. To je pre nás ale dosť zaujímavé, pretože ak po takomto ťahu vždy zostane párny počet mincí, tak ten, ktorý sa dostane na ťah, určite neprehrá – jedna minca na stole byť predsa nemôže. To znamená, že ak súperovi na stole vždy necháme nepárny počet mincí, zaručene neprehráme – teda vyhráme. No ale to vie hocikto ľahko zaručiť, keď má na stole párny počet mincí – stačí zobrať jednu. A to je víťazná stratégia :).

Ak by sme začali s nepárnym počtom mincí, Adam musí odobrať nepárny počet a pre Milana ich zostane párny počet, takže zvládne vyhrať pomocou vyššie popísanej stratégie.

Vďaka tomu, čo sme ukázali vyššie, už môžeme tvrdiť, že pre párne \(n\) zvíťazí ten, čo začína, v tomto prípade Adam, v opačnom prípade má víťaznú stratégiu Milan.