Kombinatorne igre - 2.primjer
Ponekad nije moguće u potpunosti analizirati cijelu igru na "rekurzivni" način kao u prethodnom primjeru. Stoga ćemo se često oslanjati na to da pobjedničku strategiju formuliramo indirektno, tako što ćemo ovisno o prethodnom potezu protivnika odrediti svoj potez. Često će nam za to trebati neki oblik simetrije. Promotrimo sljedeći primjer.
Primjer Dva igrača, Anđelko i Budimir, igraju igru. Na okrugli stol naizmjence stavljaju svaki po jedan novčić. Svi novčići su istog oblika i veličine, igrači ne smiju stavljati novčiće jedan na drugi, niti uspravno, te ne smiju pomicati prethodno postavljene novčiće. Gubi onaj igrač koji više ne može staviti novčić na stol. Koji igrač ima pobjedničku strategiju?
Rješenje Primijetimo prvo da jedan igrač sigurno ima pobjedničku strategiju, tj. da igra mora završiti. Naime, kad igra ne bi imala kraj, u nekom trenutku bi površina postavljenih novčića postala veća od površine stola, što je nemoguće. Dakle, u nekom trenutku više neće biti moguće postaviti novčić na stol, te tad igra mora završiti pobjedom igrača koji je zadnji stavio novčić na stol.
Ovo nam olakšava analizu igre. Naime, umjesto da pokazujemo da postoji strategija kojom jedan igrač gubi, tj. postaje nesposoban staviti novčić, dovoljno je vidjeti da postoji strategija kojom drugi igrač ne može izgubiti, tj. postoji strategija koja mu omogućava da uvijek može staviti novčić na stol. Pokazat ćemo da prvi igrač ima takvu strategiju.
Strategija prvog igrača je sljedeća. U prvom potezu stavlja novčić na sredinu stola. U svakom sljedećem potezu, kada njegov protivnik negdje stavi novčić, prvi igrač postavlja svoj novčić centralno simetrično u odnosu na novčić koji je stavio njegov protivnik. Prateći ovu strategiju, prvi igrač uvijek može staviti novčić na stol. Ako je njegov protivnik mogao staviti novčić na slobodno mjesto, to znači da je i mjesto koje je dijametralno suprotno u tom trenutku slobodno, te on može tamo staviti novčić.
Napišite rjesenje za nastavak.