Informatika - Algoritmikus eljárások témakörbe eső problémák:

• 1.1. probléma* (ld. még 1.6; a könyv 1. oldalán): {\rm Nim játék.} Osszunk több halomba egy csomó gyufaszálat. Két játékos felváltva vesz el akármelyik $($de csak egy$)$ halomból legalább egy gyufaszálat. Az nyer, aki utoljára vesz el.
• 1.2. probléma* (ld. még 1.1, 1.3, 6.26; a könyv 3. oldalán): {\rm Wythoff-nim.} Az eredeti nim-et úgy játsszuk, hogy $2$ halom van, azok bármelyikéből lehet elvenni, vagy a két halomból egyszerre ugyanannyit lehet elvenni, és az veszít, aki nem tud lépni.
• 1.3. probléma* (ld. még 1.1, 1.2, 6.26; a könyv 3. oldalán): Egy $k\times k$ méretű táblán két játékos felváltva léptet egy bábut a bal alsó sarok felé úgy, hogy egy lépésben vagy vízszintesen balra, vagy függőlegesen lefelé, vagy átlósan balra lefelé mozgatja a bábut akármennyi mezőn keresztül. Kinek van nyerő stratégiája?
• 1.4. probléma* (ld. még 1.1; a könyv 5. oldalán): A szabályok ugyanazok, mint a nimben, de most az veszít, aki az utolsó gyufaszálat kénytelen elvenni.
• 1.5. probléma** (ld. még 1.1; a könyv 5. oldalán): {\rm Moore-nim.} A nim szabályait úgy módosítjuk, hogy legfeljebb $k$ halomból lehet egyszerre elvenni, és az veszít, aki nem tud lépni $(k=1$-re ez természetesen az eredeti nim játék$)$.
• 1.6. probléma* (ld. még 1.1; a könyv 5. oldalán): {\rm Hatgyalog.} Egy $3\times 3$-as táblának két átellenes oldalán $3$ világos, illetve $3$ sötét gyalogot helyezünk el. A gyalogok a sakkban szokásos lépéseket tehetik, tehát egyet előre, vagy ha ferdén előre van egy ellentétes színű gyalog, akkor annak a helyére léphet miközben az ott álló gyalogot levesszük a tábláról. Az veszít, aki nem tud lépni.
• 1.7. probléma** (ld. még 1.6, 1.1; a könyv 7. oldalán): {\rm $2k$-gyalog.} A hatgyalog általánosítása egy $3\times k$-s táblára: a gyalogok a tábla $k$ hosszú oldalán állnak, és gyalog módjára lépnek. Az veszít, aki nem tud lépni.
• 1.8. probléma** (ld. még 1.1, 1.6; a könyv 8. oldalán): Van-e a sakkban nyerő stratégia?
• 1.9. probléma* (ld. még 1.1; a könyv 10. oldalán): Két játékos felváltva húzza be egy szabályos $n$-szög átlóit úgy, hogy azok ne metsszék egymást. Az veszít, aki nem tud újabb átlót behúzni. Melyik játékosnak van nyerő stratégiája, és mi az?
• 1.10. probléma* (ld. még 1.6; a könyv 10. oldalán): A kezdő játékos elhelyez egy huszárt egy sakktábla valamelyik mezőjére. Ezek után a játékosok felváltva lépnek a huszárral a sakk szabályainak megfelelően úgy, hogy olyan mezőre nem lehet lépni, ahol a huszár már járt. Az veszít, aki nem tud lépni. Melyik játékosnak van nyerő stratégiája és mi az?
• 1.11. probléma* (ld. még 1.1; a könyv 10. oldalán): Két játékos felváltva lép egy $n\times n$-es táblán egy bábuval olyan oldalszomszédos mezőre, amelyiken eddig a bábu nem járt. Az veszít, aki nem tud lépni. Melyik játékosnak van nyerő stratégiája, és mi az?
• 1.12. probléma** (ld. még 1.6; a könyv 11. oldalán): Két játékos felváltva egy előre adott $L>0$ számnál nem nagyobb pozitív egész számot ír le úgy, hogy egy később leírt szám ne legyen egyik előbb leírt számnak sem osztója. Az veszít, aki nem tud egy újabb számot hozzáírni a sorozathoz. Melyik játékosnak van nyerő stratégiája?
• 1.13. probléma* (ld. még 1.6; a könyv 11. oldalán): {\rm Dupla-sakk.} A sakk játék szabályait úgy módosítjuk, hogy mindkét játékos két-két szabályos sakk-lépést tesz meg egyszerre. Melyik játékosnak van nyerő stratégiája?
• 1.14. probléma* (ld. még 1.6; a könyv 12. oldalán): $n$ dobozban rendre $1,2,\ldots,n$ golyó van. A játékos egy lépésben akárhány dobozból elvehet golyót, de minden dobozból csak ugyanannyit. Legfeljebb hány lépés kell az összes doboz kiürítéséhez?
• 1.15. probléma** (ld. még 1.6; a könyv 12. oldalán): Adott bizonyos számú doboz, amelyek mindegyikében van valamennyi golyó. A játékos egy lépésben akárhány dobozból elvehet golyót, de minden dobozból csak ugyanannyit. Legalább és legfeljebb hány lépés kell az összes doboz kiürítéséhez?