Anketa - Ahoj Rieškar, stalo sa ti niekedy, že si nerozumel zadaniam? Chcel by si v lete prísť na denný tábor? Sú nejaké akcie, ktoré by si chcel, aby sme robili častejšie? … Prejsť na článok
×9. príklad - Vzorové riešenie
Zadanie
V prachu je vyrytých niekoľko prirodzených čísel. Merlin aj Macker obaja vedia na svojom ťahu zmazať dve čísla a napísať namiesto nich ich súčet alebo ich najväčšieho spoločného deliteľa. Merlin chce dosiahnuť, aby na konci ostalo párne číslo, a Macker chce nepárne. Prvý je na ťahu Merlin. Kto má výhernú stratégiu pre aké čísla?
Poznámka: Výherná stratégia znamená, že hráč vie pomocou nej vyhrať bez ohľadu na to, ako hrá jeho súper.Vzorové riešenie
Keďže v zadaní sa spomína parita (to, či je číslo párne alebo nepárne), asi sa zíde zamyslieť sa nad paritou čísel v priebehu celej hry. Poďme sa teda pozrieť na to, akú paritu budú mať čísla, ktoré vzniknú po jednom ťahu, ak spravíme ťah podľa pravidiel.
Ak sčítame 2 párne čísla alebo 2 nepárne čísla, dostaneme párne číslo, a ak sčítame párne a nepárne číslo, dostaneme nepárne číslo. O najväčšom spoločnom deliteľovi vieme, že je to najväčšie číslo, ktoré je deliteľom oboch čísel. Pritom nepárne číslo nemá párneho deliteľa, teda z toho vyplýva, že najväčší spoločný deliteľ párneho a nepárneho čísla alebo 2 nepárnych čísel je nepárny. A ak máme 2 párne čísla, tak obe sú deliteľné 2, teda aj ich najväčší spoločný deliteľ musí byť deliteľný 2 (inak ho vieme vynásobiť 2 a dostali sme väčšieho spoločného deliteľa) a teda je párny.
Všimnime si, že počet nepárnych čísel sa v žiadnom ťahu nezvýši, a zníži sa len v ťahu, v ktorom zmažeme 2 nepárne čísla. Z toho vidíme, že ak niekedy v priebehu hry máme dokopy 0 alebo 1 nepárnych čísel, ich počet sa už nezmení.
Taktiež vieme, že ak je posledné číslo párne, teda máme 0 nepárnych čísel, vyhral Merlin, a ak je posledné číslo nepárne, teda máme 1 nepárne číslo, vyhral Macker. Teda ak sa v priebehu hry dostaneme do takej situácie, že na zemi je 0 nepárnych čísel, vyhral Merlin, a ak sa dostaneme do situácie, v ktorej je na zemi 1 nepárne číslo, vyhral Macker.
Ak je Merlin na ťahu a na zemi sú 2 nepárne čísla, môže obe nahradiť ich súčtom, ktorý je párny, teda na zemi neostane žiadne nepárne číslo a Merlin teda vyhral. Keďže Merlin začína, tak ak sú na začiatku hry na zemi 2 nepárne čísla, Merlin vyhral.
No ak je na ťahu Macker a na zemi sú 2 nepárne čísla, môže obe nahradiť ich najmenším spoločným deliteľom, pričom na zemi ostane jedno nepárne číslo a Macker teda vyhral. A ak sú na zemi 3 nepárne čísla, tak ich môže Macker obe nahradiť ich najväčším spoločným deliteľom, pričom na zemi ostane jedno nepárne číslo a Macker teda vyhral.
Vidíme teda, že ak je Macker na ťahu a na zemi sú 1, 2, alebo 3 nepárne čísla, Macker vyhral. Zároveň, ak na začiatku hry boli na zemi aspoň 3 nepárne čísla, pred prvým Mackerovým ťahom tam aspoň jedno nepárne číslo ostalo (lebo po Merlinovom ťahu sa počet nepárnych čísel znížil najviac o 2). Teraz si všimnime, že ak Macker pre 1, 2, alebo 3 nepárne čísla na kôpke vyhrá (už vieme, že vtedy vie vyhrať) a pre väčší počet nepárnych čísel na kôpke nahradí dve nepárne čísla ich najväčším spoločným deliteľom, čím zníži ich počet o 1, tak sa počet nepárnych čísel medzi dvoma jeho ťahmi (ak sa ešte nedostal k 1, 2, alebo 3 nepárnym číslam) zníži najviac o 3 (Macker ho zníži o 1 a Merlin ho vie znížiť najviac o 2). Z toho ale vyplýva, ak na začiatku hry boli viac ako 3 nepárne čísla, Macker sa raz dostane na svojom ťahu do situácie, kedy sú na zemi 1, 2, alebo 3 nepárne čísla, a vyhrá.
Odpoveď: Ak na začiatku hry boli na kôpke 0 alebo 2 nepárne čísla, vyhrá Merlin, inak vyhrá Macker.