5. Zadatak
Na ploči dimenzija koja je na početku prazna igra se igra za dva igrača koji naizmjence vuku poteze. U pojedinom potezu igrač odabire dva prazna polja koja se nalaze u istom retku ili istom stupcu te stavlja po jedan žeton na ta polja. Gubi igrač koji ne može odigrati dopušteni potez.
Ako Kristina igra prva, a Ana druga, koja od njih može osigurati svoju pobjedu?
Neovisno o Kristininoj igri Ana može osigurati pobjedu. Nakon prvog Kristininog poteza Ana bira red u kojem se nalazi barem jedan žeton. Nazovimo taj red posebnim.
Ana nakon svakog svojeg poteza može osigurati sljedeće:
- u posebnom redu nalazi se neparno mnogo žetona;
- ako se u nekom polju posebnog retka ne nalazi žeton, žeton se ne nalazi ni u ostalim poljima stupca koji to polje određuje.
Nakon prvog poteza i nakon što odabere poseban redak, Ana će postići oba gornja uvjeta tako da stavi dva žetona u poseban redak ako je Kristina prije toga stavila jedan žeton u poseban redak, odnosno tako da stavi po jedan žeton u poseban redak i neki drugi redak ako je Kristina stavila dva žetona u poseban redak.
Počevši s drugim potezom, dok god poseban redak nije ispunjen, Ana radi svoj potez ovisno o Kristininom zadnjem potezu:
- ako je Kristina stavila dva žetona u istom stupcu, od čega jedan u poseban redak, Ana može ponovno staviti dva žetona u neki drugi stupac, od čega jedan u poseban redak (kako je prije Kristininog poteza neparno mnogo polja posebnog retka bilo zauzeto, zajedno sa svojstvom (ii) Ana može naći slobodan stupac);
- ako je Kristina stavila dva žetona u istom stupcu, od čega nijedan u poseban redak, Ana postavlja dva žetona u poseban redak, od čega jedan u onaj stupac u kojem je Kristina stavljala svoje žetone (slično, iz (i) i (ii) takva dva polja su slobodna);
- ako je Kristina stavila dva žetona u isti redak koji nije poseban, Ana postavlja dva žetona u posebni redak u iste stupce kao Kristinina dva žetona što je sigurno moguće;
- ako je Kristina stavila dva žetona u poseban redak, Ana može postaviti dva žetona u iste stupce nekog drugog retka (ta polja su slobodna, inače bi se kosilo s pravilom (ii)).
Možemo primijetiti da su oba svojstva (i) i (ii) očuvana nakon svakog Aninog poteza. Ova Anina strategija osigurava da se sigurno tijekom igre ispuni poseban redak.
Nakon što se ispuni poseban redak, Ana će sigurno pobijediti neovisno o preostalim potezima. Naime, broj polja na kojima se ne nalazi žeton je uvijek neparan, pa će u svakom potezu postojati redak u koji se može staviti barem dva žetona sve dok na ploči ne preostane samo jedno polje na kojem nema žetona. Budući da ukupan broj polja () daje ostatak pri dijeljenju s , ta situacija nastaje nakon Aninog poteza.