Feladat: 1322. matematika feladat Korcsoport: 18- Nehézségi fok: nehéz
Megoldó(k):  Bóta K. ,  Deák István ,  Huhn A. ,  Lovász L. ,  Márki L. ,  Mátrai M. ,  Patkós A. ,  Pelikán J. ,  Recski A. ,  Surányi László ,  Sükösd Cs. ,  Székely G. ,  Veres Ferenc 
Füzet: 1966/április, 148 - 149. oldal  PDF  |  MathML 
Témakör(ök): Nim, Feladat
Hivatkozás(ok):Feladatok: 1964/május: 1322. matematika feladat

A szöveg csak Firefox böngészőben jelenik meg helyesen. Használja a fenti PDF file-ra mutató link-et a letöltésre.

*
Egy halom esetén egyetlen vesztő állás az, amelyben egyetlen kő áll az asztalon, jelöljük így: (1); a soron következő kénytelen ezt elvenni, és veszt. Azok az állások, amelyekből az (1) végző vesztő állás előállítható, más szóval a végző megnyerhető állások csak (1, a) és (b) típusúak lehetnek, ahol a1 és b2. Ilyen állás visszahagyására kell kényszerítenünk ellenfelünket utolsó előtti lépésében, az ő ezen lépése előtti állásnak viszont (1, a)-tól és (b)-től különbözőnek kellett lennie, különben mi vesztünk. Így az állás típusa nem lehetett más, mint vagy (1, a, c), ahol c1, vagy (d, a), ahol d2, ilyenkor azonban nem lehet a=1. Az utóbbi típus adódik (b)-ből is (b, e) alakban, ahol e2.
Azonban ilyen típusú állásból csak akkor kényszerül az ellenfél nekünk megnyerhető állás előállítására, ha c és d nem nagyobb a legkisebb lehetséges értéknél, vagyis ha (1, a, c)-ben c=1, és emiatt egyszersmind a=1, ill. ha (d, a)-ban d=a=2; különben ugyanis kevesebbet is vehet el. Csak az (1, 1, 1) és a (2, 2) állások biztosítják, hogy az ellenfél két lépésben veszít.
Innen adódik, hogy (e, e) minden e>2 esetén is vesztő állás. Ha ugyanis az ellenfél az egyik halmot kiüríti, akkor mi a másikból 1 követ hagyunk; ha ő hagy 1-et, mi ürítjük ki a másikat, ha pedig 1-nél többet hagy, mi ugyanannyira csökkentjük a másik halmot, tehát vagy már a 2. lépesében veszt a partner, vagy legkésőbben a (2, 2) állásból. ‐ Más két halmos vesztő állás nincs, ti. (e, f) típusú, ahol f>e2, mert ebből az ellenfél állíthat elő (e, e) típusú, számunkra vesztő állást.
Az (e, e) az eredeti játékmódban is vesztő állás, minden e esetén, és ott sincs más két halmos vesztő állás. Eszerint két halmos vesztő állások csak azok az állások, amelyek a nim eredeti játékmódja szerint azok, kivéve közülük az (1, 1)-et.
Az (1, 1, 1) legkisebb összegű három halmos vesztő állás (vesztő trió) utáni legkisebb összegű vesztő trió (1, 2, 3), összege 6, ugyanis a 4 és 5 összegűek megnyerhetők: (1, 1, 2)-ből az (1, 1, 1) állítható elő, és (1, 1, 3)-ból is, (1, 2, 2)-ből pedig a (2, 2); másrészt az (1, 2, 3) vesztő trió, mert ha nem üríti ki azt a halmot, amelyből elvesz, akkor legalább 4 kő marad, amit most láttunk, ha pedig kiüríti, akkor (0, 2, 3)-ból a (2, 2) állítható elő, különben pedig az (1) vesztő állás. ‐ Az (1, 2, 3) ugyancsak vesztő trió az eredeti játékmód esetén is.
Megmutatjuk, hogy minden az eredeti játékmód szerinti vesztő trió a módosítás stratégiájában is vesztő trió. Tudjuk, hogy ha egy eredeti vesztő trióban van 1 kőből álló halom, akkor az (1, 2k, 2k+1) típusú. Ebből már csak a k>1 esetet kell tekintenünk. Ha ebből ellenfelünk az 1-es halmot veszi el, mi (2k, 2k)-t állítunk elő; ha a másik két halom bármelyikéből 2-nél kevesebb követ hagy, akkor (1)-et vagy (1, 1, 1)-et, ha pedig legalább 2 követ hagy, akkor mi a másik nagy halomban 1-gyel több, ill. kevesebb követ hagyunk aszerint, hogy ő páros vagy páratlan számú követ hagyott vissza, és így (1, 2m, 2m+1) alakú állást (ahol 1m<k), azaz eredeti vesztő állást hagyunk ellenfelünkre.
Már csak azok az eredeti vesztő triók vannak hátra, amelyekben mindegyik halomban legalább 2 kő van. Tudjuk, hogy ilyennek minden halmában különböző számú kő van, így sem az (1), sem az (1, 1, 1), sem (e, e) nem állítható elő belőle, ezért ellenfelünk bármely lépésére az eredeti stratégia szerinti lépéssel válaszolunk.
Stratégiánk csak akkor használható, ha a kiindulási állás vesztő állás és a partner kezd, vagy pedig ha a kiindulási állás megnyerhető és mi kezdünk, (végül, ha a partner hibáz).
Veres Ferenc (Miskolc, Kilián Gy. G.)
Surányi László (Budapest, Fazekas M. Gyak. G.)


*Lásd a következő cikket: Dr. Báron Gyula: A nim-játék stratégiájáról, a nyerő stratégia felkutatása, K. M. L. 28. (1964) 193‐198. o. ‐ Röviden ismételjük a szükséges tudnivalókat. A játékot ketten játsszák, miután bizonyos számú, meg nem különböztetett elemet, pl. követ tetszés szerinti számú halomba osztottak. Felváltva lépnek, egy lépés abban áll, hogy valamely halomból elvesznek valamennyi követ, legalább 1-et, de akár az egész halmot is. Az nyer, aki az utolsó követ veszi el, akár magában, akár az utolsó halom még meglevő köveivel együtt. A nyerő stratégia lényege, hogy húzásunkkal mindig ún. vesztő állást állítsunk ellenfelünk elé, amelyből bármely megengedett elvétellel számunkra megnyerhető állást állít elő. Van ilyen stratégia: azok a vesztő állások, amelyekben a halmokban levő elemek számát 2-es számrendszerben felírva az egyenlő helyi értékű számjegyek összege mindig páros. Két halom esetén minden vesztő állásban a halmok köveinek száma egyenlő: (a,a); három halmos vesztő állásban viszont nem lehet két halomban ugyanannyi kő.