8. Karambol Matematických Stratégií vzorové riešenie

Začnime jednoduchým pozorovaním o celkovom súčte čísel. Platí \[1 + 2 + \ldots + 2n = \dfrac{2n(2n+1)}{2} = n(2n+1) = 2n^2 + n.\] Môžeme si všimnúť, že súčet všetkých čísel dáva po delení \(2n\) zvyšok \(n\). Teda ak sa Krtkovi podarí vybrať čísla tak, aby bol ich súčet deliteľný \(2n\), súčet ostatných bude mať zvyšok \(n\). Vo všeobecnosti Krtko rozdelí čísla na \(2\) kôpky – tú, ktorú si vezme, a tú, ktorú nechá tak. Môžeme si všimnúť, že ak je súčet na jednej kôpke násobkom \(n\), na druhej je tiež. Zvyšky daných súčtov po delení \(2n\) teda musia byť \(0\) a \(n\), aby sedel celkový súčet.

Rozdeľme si príklad na \(2\) časti, podľa toho, či je \(n\) párne alebo nepárne. Z predošlého odseku vieme, že Krtko vyhrá práve vtedy, keď rozdelí čísla na dve kôpky tak, že súčet čísel na hociktorej z nich je násobkom \(n\). Pre jednoduchosť počítajme miesto s pôvodnými číslami, s ich zvyškami po delení \(n\).

Začnime s párnym \(n\). Ľahko si všimneme, že Merlin dokáže popárovať čísla tak, aby tie s rovnakým zvyškom po delení \(n\) boli spolu. (Každé číslo od \(1\) po \(n\) bude v dvojici s číslom o \(n\) väčším.) Nech bude Krtko robiť čokoľvek, nakoniec si vezme z každého zvyšku po jednom. V takom prípade však prehrá, lebo \(0 + 1 + \ldots + (n-1) = n(n-1)/2\). Keďže \(n-1\) je nepárne, výsledné číslo nebude deliteľné \(n\). Merlin má teda vyhrávajúcu stratégiu.

Prejdime k nepárnemu \(n\). Veľmi ľahko vidíme, že Merlinova stratégia, ktorá fungovala pre párne \(n\), teraz nefunguje. Po chvíli skúšania si všimneme, že Krtkovi sa aj pre iné rozdelenia vcelku darí voliť čísla dosť šikovne na to, aby vyhral. Skúsme teda dokázať, že to tak bude pre každé nepárne \(n\). Opäť využijeme, že Krtkovo víťazstvo závisí na tom, či dokáže čísla rozdeliť tak, aby mala každá kôpka súčet deliteľný \(n\). Pre jednoduchosť rozlíšme červenú a modrú kôpku. Krtko rozdelí každú dvojicu od Merlina medzi tieto dve kôpky. Ak budú mať obe súčet deliteľný \(n\), jedna bude mať súčet deliteľný dokonca \(2n\) a jej voľbou Krtko vyhrá. My ukážeme niečo ešte silnejšie, a to dokonca, že Krtko vie zariadiť, aby aj červená aj modrá kôpka obsahovali každý zvyšok po delení \(n\) práve raz. To mu pomôže, pretože súčet čísel od \(0\) do \(n-1\) je pre nepárne \(n\) deliteľný \(n\).

Nech si teda Krtko na začiatku zvolí nejakú dvojicu \(a,b\), ktorú vytvoril Merlin. Keďže ešte nie je nič zaradené, môže dať \(a\) na červenú kopu a nič tým nepokazí. Číslo s rovnakým zvyškom ako \(a\) po delení \(n\) potom zaradí do modrej. Ak toto číslo bolo \(b\), môže začať „odznova“ so zvyšnými číslami, keďže zaradené čísla nemajú na zvyšok vplyv. Inak je to \(c \neq b\) z dvojice \(c,d\). Krtko zaradí \(d\) do červenej a pokračuje s novým zvyškom ďalej rovnako. Prejde do novej dvojičky a číslo s daným zvyškom zaradí do modrej. Takto nenarazí znovu na zvyšok, ktorý už je zaradený. Keďže má k dispozícii len konečne veľa čísel, raz sa dostane k číslu, ktorého dvojička už zaradená je. Toto číslo zaradené ešte nebolo, takže je to \(b\). To zaradí do modrej kôpky, čo sedí, keďže \(a\) je v červenej. Zaradené dvojičky ani zvyšky už nemajú vplyv na zvyšné čísla, a tak môže Krtko začať svoj postup znovu.

Ako môžeme vidieť, Krtko dokáže rozdeliť zvyšky na modrú a červenú kôpku a udržať sa pritom v medziach stanovených zadaním. Následne si už len vyberie jednu tak, aby vyhral. Krtko má teda víťaznú stratégiu.