Több mint 400 évvel ezelőtt, 1612-ben egy francia matematikus, Claude Gaspar Bachet de Méziriac megjelentetett egy könyvet, amelynek címe nagyjából így fordítható: Szórakoztató és élvezetes feladatok számokkal. Ebben a kötetben bukkant fel a kombinatorikus játékelmélet egyik legelső írásos feladata, ami a mai napig kiválóan szemlélteti e tudományág alapvető logikáját.

Az említett játék szabályai egyszerűek: van egy szám, ami kezdetben nulla, és két játékos felváltva növeli ezt a számot egy pozitív egész számmal, de legfeljebb 10-zel. Az nyeri a játékot, aki eléri a 100-at.

Amikor először próbáljuk ki a játékot, az első néhány körben még úgy tűnhet, sötétben tapogatózunk, hiszen túl messze van a cél. Ahogy azonban egyre közelebb érünk a 100-hoz, sokkal könnyebbé válik a kalkuláció. Ezen a ponton fedezhetjük fel a játék megértésének kulcsát: stratégiánkat hátulról visszafelé haladva kell kialakítanunk.

Képzeljük el a végjátékot! Ha el tudjuk érni a 89-et, azaz mi mondjuk ki ezt az összeget, akkor nyert ügyünk van, hiszen ellenfelünk ezután kénytelen legalább 1-et, de legfeljebb 10-et hozzáadni a számhoz. Bármit is lép, az új összeg garantáltan 90 és 99 közé fog esni, ami az ellenfélnek vesztő pozíció, mert ezek bármelyikéből tovább tudunk lépni a 100-ra, és megnyerjük a játékot.

A 89 tehát egy nyerő mérföldkő, azaz 100 helyett lehet ez a célszámunk. Akkor viszont hasonló logikával nyert ügyünk van, ha elérjük a 78-at, ami tehát szintén nyerő mérföldkő. Ha ezt a gondolatmenetet tovább folytatjuk visszafelé, minden számról megállapíthatjuk, hogy nyerő vagy vesztő pozíció-e. A nyerő pozíciók mindenképpen nyerők, akárhogy is lép az ellenfél, a vesztő pozíció pedig veszít, ha az ellenfél jól játszik.

Az ilyen típusú kétszemélyes játékokat – amelyekben a játékosok felváltva lépnek, minden információ nyíltan elérhető számukra (nincs benne például véletlen kockadobás), és a küzdelem véges lépésen belül biztosan véget ér – kombinatorikus játékoknak nevezzük. Az ilyen játékoknál pontosan az információk teljes nyíltsága és a véletlen hiánya miatt működik hibátlanul a hátulról visszafelé gondolkodás, hiszen a játék minden egyes lehetséges állapota egyértelműen besorolható a nyerő vagy a vesztő pozíciók közé, amiket hátulról kezdve visszafejthetünk.

Most azonban csavarjunk egyet a szabályokon! Nézzük az alábbi példát: vajon itt is működik a visszafelé gondolkodás?

297. feladvány: A 13-as célszám

Kinek van nyerő stratégiája az alábbi két fős játékban, a kezdőnek vagy a második játékosnak?

A játékosok felváltva következnek és növelnek egy számot, ami kezdetben nulla. Az első játékos ezt kötelezően 1-gyel növeli. A második játékos az eredményhez hozzáadhat 1-et vagy 2-t. A következő játékos mindig hozzá kell adjon az addigi összeghez egy pozitív egész számot, ami viszont legfeljebb 1-gyel lehet nagyobb, mint bármely korábbi szám, amit valaki hozzáadott, és így tovább. Az nyer, aki eléri a 13-at.

Most is haladhatunk hátulról visszafelé, csak arra kell vigyázni, hogy egy állapotot két dolog határoz meg: maga a szám, és az, hogy mekkorát lehet maximum hozzáadni.

A játék állapotát most nem elég a számmal leírnunk, amit növelgetünk, hanem azt is tudnunk kell egy adott szituációban, hogy mekkora volt az eddigi legnagyobb növekmény, azaz legfeljebb mekkora számot adhatunk most a számhoz. A játék állapotát ezért írjuk le a (D, M) a számpárral, ahol D a célszámig hátralévő távolság, M pedig a legnagyobb lépés, amit eddig valaki tett, tehát M+1 a maximális lépés, amit a soron következő játékos tehet.

Keressünk hátulról olyan állapotot, aminek elérése kedvező lenne számunkra. A (4, 2) állapot például ilyen. Ha az ellenfél a (4, 2) állapotból indul, maximum 3-at léphet, vagyis egy lépésen belül nem tudja elérni a célt, mi viszont bármekkorát is lép, a maradék távolságot egy lépésben le tudjuk küzdeni.

Nézzük most az (5, 3) állapot. Ha az ellenfél az (5, 3) állapotból indul, maximum 4-et léphet, és az előző esethez hasonlóan: egy lépésen belül nem tudja elérni a célt, mi viszont bármekkorát is lép, a maradék távolságot egy lépésben le tudjuk küzdeni.

Most ugorjunk egyet, és nézzük a (7, 2) állapotot. Ha az ellenfél a (7, 2) állapotból indul, maximum 3-at léphet. Ha 1-et vagy 2-t lép: a távolság 6 vagy 5 lesz, de M értéke marad 2, és mi 2-t vagy 1-et lépve a (4, 2) állapotba jutunk, ami nyerő számunkra. Ha viszont az ellenfél 3-at lép, a távolság 4 lesz, mi viszont már léphetünk 4-et, mert M értéke 3-ra változott.

Nézzük most a (10,2) állapotot, amiből az ellenfél ugyancsak maximum 3-at léphet: Ha 1-et vagy 2-t lép, akkor a távolság 9 vagy 8 lesz, és M értéke nem változik, mi pedig 2-t vagy 1-et lépve elérhetjük a (7, 2) állapotot, ami nyerő. Ha viszont az ellenfél 3-at lép, akkor a távolság 7 lesz és M értéke 3-ra változik, innen viszont 2-t lépve elérhetjük az (5, 3) állapotot, ami szintén nyerő nekünk.

Ezek után megállapíthatjuk, hogy a második játékosank van nyerő stratégiája. A kezdő távolság 13, az első játékos kötelezően lép 1-et, és ezzel a (12,1) állapotot hagyja a második játékosra, amiből 2-t lépve a (10,2) állapotba juthat, amiről már megállapítottuk, hogy nyerő állapot.

Ha szereted a fejtörőket, tekintsd meg korábbi feladványainkat is! Ha megjegyzésed lenne, vagy feladványt javasolnál, írj az eszventura@qubit.hu e-mail címre! Ha pedig tetszik a rovat, ezt a Vendégkönyvben kifejezésre juttathatod.

Az Ész Ventura feladványügyi rovat gazdája: Gáspár Merse Előd fizikus, kognitív kutató, társasjáték-fejlesztő és bűvész.

Forrás