9. Keď Milionárom Si vzorové riešenie

Môžeme si všimnúť, že po každej operácii celkový počet mincí ostane rovnaký, alebo sa zvýši. Ak by sa nám vždy podarilo zvýšiť počet mincí, raz budeme mať dosť veľa mincí na to, aby na niektorej kôpke bolo aspoň \(2019^{2020}\) mincí. V prípade ak bude na každej kôpke len \(2017\) mincí, tak nevieme urobiť žiadnu operáciu a skončili sme. Ak bude na niektorej kôpke viac ako \(2017\) mincí, už vieme robiť nejaké operácie a ukážeme si, že dokonca vždy budeme vedieť pridať ďalšiu mincu.

Odteraz nech je na kôpkach spolu aspoň \(3\cdot2017+1\) mincí. Vždy vieme spraviť nejaký ťah, lebo ak je na všetkých kôpkach nepárny počet mincí, na tej najväčšej musí byť aspoň 2019 mincí a použijeme na ňu operáciu \(\textit{(2)}\). Ak je na niektorej kôpke párny počet mincí, vieme ju rozdeliť na zvyšné dve kôpky operáciou \(\textit{(1)}\). V takomto prípade dostaneme na jednej kôpke \(0\) mincí a kým budeme robiť len operácie \(\textit{(1)}\), stále bude na niektorej kôpke \(0\) mincí. Keď použijeme operáciu \(\textit{(2)}\), zvýšime celkvý počet mincí a môžeme začať odznova. Preto stačí dokázať, že keď sme v stave, kde je na niektorej kôpke \(0\) mincí, vieme spraviť niekoľko ťahov \(\textit{(1)}\) tak, aby sme potom mohli spraviť ťah \(\textit{(2)}\).Počty mincí na dvoch nenulových kôpkach označíme \(A, B\), kde \(A\) je ten väčší počet, \(A \geq B\).

Ak \(A\) je nepárne, vidíme, že \(A \geq 2019\). Stačí keď použijeme operáciu \(\textit{(2)}\) na kôpku \(A\), teda sme pridali celkovo \(1\) mincu.

Ak je \(A\) párne a \(B\) je nepárne, pozrime sa ešte, aké veľké je \(B\). Ak \(B \geq 2019\), tak použijeme naň operáciu \(\textit{(2)}\) a zvýšime celkový počet mincí. V opačnom prípade (označme \(A=2K\)) kôpku \(A\) rozdelíme na dve polovice po \(K\). Počty mincí na kôpkach budú \(K\) a \(B+K\). Keďže \(B\) mohlo byť najviac \(2017\), tak \(A\) bolo aspoň \(2 \cdot 2017+1\), teda \(K\) je aspoň \(2018\). Spolu máme nepárny počet mincí (\(A+B\)), takže na niektorej kôpke je nepárny počet mincí. Na oboch kôpkach (\(K\) aj \(B+K\)) je aspoň \(2018\) mincí, takže na tej nepárnej je aspoň \(2019\) mincí, môžeme na ňu použiť operáciu \(\textit{(2)}\).

Ak je \(A\) aj \(B\) párne, jednoducho kôpku na ktorej je menej mincí vždy rozdelíme na dve polovice Takto sa nám vždy zmenší počet mincí na menšej kôpke, takže raz sa musíme zaseknúť. V takom prípade bude na oboch kôpkach nepárny počet mincí, takže na väčšiu z nich použijeme operáciu \(\textit{(2)}\).

Keď na začiatku bolo na kôpkach \((2017, 2017, 2017)\) mincí, tak moreplavci nevedia dostať na žiadnej kôpke \(2019^{2020}\) mincí. Vo všetkých ostatných prípadoch vedia, pretože vždy vedia pridať \(1\) mincu a raz, keď bude všetkých mincí dosť veľa, tak na niektorej kôpke bude musieť byť aspoň \(2019^{2020}\) mincí.