10. príklad - Vzorové riešenie

Najskôr spravíme nasledovné pozorovanie: Ak pre nejaké n vie vždy vyhrať hráč, ktorý nerobí prvý ťah, tak pre n+1 vyhrá hráč, ktorý robí prvý ťah, rozdelením kôpky veľkosti n+1 na kôpky 1, n. Kôpka veľkosti 1 sa už nedá deliť ďalej a v kôpke veľkosti n už nerobí prvý ťah. Dostane sa teda do víťaznej situácie. Teraz si rozoberme niektoré malé prípady:

• Pre n=1 nenastane žiadne delenie, teda hra nemá víťaza.
• Pre n=2 vyhrá prvý hráč rozdelením na kôpky veľkostí 1, 1.
• Pre n=3 vyhrá prvý hráč rozdelením na kôpky veľkostí 2, 1.
• Pre n=4 vyhrá prvý hráč rozdelením na kôpky veľkostí 2, 2.
• Pre n=5 vyhrá druhý hráč. Ak prvý hráč rozdelí počiatočnú kôpku na kôpky veľkostí 1, 4, tak druhý hráč rozdelí 4 na 2, 2. Ak prvý hráč rozdelí 5 na 2, 3, tak druhý hráč rozdelí 3 na 1, 2.
• Pre n=6 vyhrá podľa pozorovania zo začiatku prvý hráč rozdelením na kôpky 1,5
• Pre n=7 vyhrá druhý hráč. Rozoberme si možnosti podľa toho, na aké kôpky môže rozdeliť 7 prvý hráč:
  • Kôpky 1,6: druhý hráč robí prvý ťah s kôpkou 6, teda vyhrá.
  • Kôpky 2,5: druhý hráč rozdelí 2 na 1,1. Ďalej sa dá deliť iba kôpka veľkosti 5, v ktorej druhý hráč nerobí prvý ťah a teda vyhrá.
  • Kôpky 3,4: druhý hráč rozdelí 4 na 1,3 čím ostanú kôpky 3,1,3. Prvý hráč teraz musí rozdeliť jednu z 3 na kôpky 1,2 a potom druhý hráč vie spraviť posledný ťah rozdelením druhej 3 na 1,2.
• Pre n=8 vyhrá, podľa pozorovania zo začiatku, prvý hráč rozdelením na kôpky 1,7.
• Pre n=9 vyhrá druhý hráč. Rozoberme si možnosti podľa toho, na aké kôpky môže rozdeliť 9 prvý hráč:
  • Kôpky 1,8: druhý hráč robí prvý ťah s kôpkou 8, teda vyhrá.
  • Kôpky 2,7: druhý hráč rozdelí 2 na 1,1. Ďalej sa dá deliť iba kôpka veľkosti 7, v ktorej druhý hráč nerobí prvý ťah, teda vyhrá.
  • Kôpky 3,6: druhý hráč rozdelí 6 na 3,3 čím ostanú kôpky 3,3,3. Prvý hráč teraz musí rozdeliť jednu z 3 na kôpky 1,2. Druhý hráč rozdelí 2 na 1,1, čím ostanú iba dve kôpky, ktoré sa dajú deliť veľkostí 3,3. Hociktorú z 3 rozdelí prvý hráč, tak druhý potom rozdelí tú druhú, čím vyhrá.
  • Kôpky 4,5: druhý hráč rozdelí 4 na 2,2, čím ostanú kôpky 2,2,5. Ak prvý hráč rozdelí niektorú z 2, tak druhý hráč rozdelí druhú, čím ostane jediná deliteľná kôpka veľkosti 5. Teda vyhrá druhý. Ak prvý hráč rozdelí 5 na 1,4 alebo 2,3, tak v oboch prípadoch vie druhý hráč vyhrať tým, že buď rozdelí 4 na 2,2 alebo 3 na 1,2.

Teraz chceme ukázať, že pre nepárne n>9 vyhrá druhý hráč. Využijeme fakt, že pre párne kôpky menších veľkostí a veľkosť 3 vyhrá prvý hráč a pre ostatné nepárne kôpky veľkosti menšej ako n vyhrá druhý hráč. Párne n>8 potom vyjdú z pozorovania zo začiatku.

Prvý hráč rozdelí kôpku veľkosti n na dve menšie. Keďže n je nepárne, kôpky sú jedna s párnou veľkosťou a jedna s nepárnou. Mohol nastať jeden z troch prípadov:

1. Jedna kôpka má veľkosť 2, teda kôpky majú veľkosti 2,n-2.
2. Jedna kôpka má veľkosť 3, teda kôpky majú veľkosti 3,n-3.
3. Niečo iné, teda kôpky majú veľkosti k,n-k pre k>3 a n-k > 3.

V prvom prípade vie druhý hráč rozdeliť kôpku veľkosti 2 na 1,1 čím ostane jediná kôpka ktorá sa dá deliť nepárnej veľkosti n-2, pričom o kôpke n-2 vieme z predpokladu že v nej vždy vie vyhrať druhý hráč.

V druhom prípade rozdelí druhý hráč párnu kôpku veľkosti n-3 na kôpky veľkosti 3,n-6, teda na stole sú tri kôpky veľkostí 3,3,n-6. Keďže n>9, tak n-6>3 a teda v takejto kôpke vyhráva hráč nerobiaci prvý ťah. Plán druhého hráča je teraz celkom jednoduchý. Sú dve kôpky veľkosti 3,3, teda akokoľvek bude deliť prvý hráč jednu z týchto kôpok, tak druhý hráč vie to isté zopakovať v druhej kôpke. Pre n-6 má vyhrávajúcu stratégiu nezačínajúci hráč, čo je v tomto prípade druhý hráč. Treba však overiť, že ho prvý hráč nemôže prinútiť začať. Vždy, keď prvý hráč rozdelí inú kôpku ako n-6, alebo tie čo z nej vznikli, tak musel deliť niektorú z 3 alebo 2 čo vznikli z 3. Druhý hráč potom vie to isté zopakovať v druhej 3, resp. 2, čiže prvý hráč poradie toho, ako sa delí kôpka veľkosti n-6 nezmení.

V treťom prípade druhý hráč rozdelí párnu z kôpok na dve rovnako veľké kopy, teda kôpky budú mať veľkosti m,m,n-2m. Hociako bude prvý hráč deliť kôpku veľkosti m a kôpky ktoré z nej vznikli, tak druhý hráč vie zopakovať rovnaké delenie v druhej kôpke veľkosti m a kôpkach ktoré z nej vznikli. Zároveň kôpka veľkosti n-2m je nepárna a teda má z predpokladu k>3, n-k>3 veľkosť aspoň 5. Vyhráva v nej teda nezačínajúci hráč, čo je v tomto prípade druhý hráč.

Týmto sme teda pokryli všetky možnosti ako môže deliť kôpku nepárnej veľkosti prvý hráč a v každej sme prišli na to že vyhráva druhý hráč. Z toho pre nepárne n>9 vždy vie vyhrať druhý hráč. Pridaním rozboru pre malé prípady a pozorovania zo začiatku dostaneme odpoveď.

Odpoveď: Pre párne n a n=3 vyhrá prvý hráč, pre nepárne n\geq 5 vyhrá druhý hráč a pre n=1 hra nemá víťaza.