Diszkrét matematikai játékok

Előadás: szerda 8–10 Farkas terem

Tudnivalók a követelményekkel kapcsolatban

Mintafeladatsor az írásbeli vizsgához

Az előadások anyaga és a könyvből (Csákány Béla: Diszkrét matematikai játékok) elolvasandó (al)fejezetek:

szeptember 10. Kombinatorikai játékok.

Játékok, mint matematikai struktúrák, végességi feltételek, Kőnig-lemma, kombinatorikai játékok. Bachet játéka, pénzfordítós játék, pénzlerakós játék, ω2-játék. A stratégia fogalma, stratégiai játékok, nyerő és biztonságos stratégia, Neumann János alaptétele.

szeptember 17. Egyszerű játék magja és Sprague–Grundy-függvénye, nim-összeadás.

Egyszerű játék magja és Sprague–Grundy-függvénye (egzisztencia, unicitás, zérushelyek), egyszerű példák. Sarokba a bástyát! és nim játék. A nim-összeadás definíciója, kancellativitás és nim-monotonitás, nim-prímek.

szeptember 24. Játékok összege, nim játék.

A nim-összeg kiszámítása kettes számrendszerben, bináris összeadás. Játékok összege, összeg SG-függvénye. A nim játék nyerő stratégiája.

október 1. Rontom-bontom játékok.

Kivonási játékok, a SG-függvény periodicitása véges kivonási halmaz esetén. Rontom-bontom játékok: Grundy-nim, kugli.

október 8. A nim játék változatai.

Northcott-sakk, póker-nim, majdnim, pénzfordítós játék, Lasker-nim.

október 15. Wythoff-nim.

Sarokba a királynőt! és Wythoff-nim, a Wythoff-nim magjának leírása különféle tulajdonságokkal, a jó lépések meghatározása.

  • olvasnivaló: 3.7
október 22. A Wythoff-nim kapcsolata az aranymetszéssel és a Fibonacci-számokkal.

A Wythoff-nim magjának leírása Fibonacci számrendszerben és aranymetszéssel.

október 29. Betli játékok.

Betli játék visszavezetése normál játékra hisztizéssel. Betli nim és betli Wythoff nim. Betli kivonási játékok: Ferguson-párok, Ferguson tétele. A mérgezett csokoládé játék (Gale lefedős játéka).

november 5. Malomszerű játékok.

Fred. Schuh játéka. Malomszerű játékok, stratégialopás, Építő-Romboló játékok, minimalom (tic-tac-toe), amőba. Hex, Nash tétele.

november 12. Permutációs játékok.

Tizenötös játék. Cserélgetős játékok, permutációk paritása, permutaciós játékok és csoportok. A bűvös kocka elérhető állásainak leírása, Isten száma.

november 19.
november 26. Elővizsga.
december 3.
december 10.