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. A 15-ös játék és a Rubik-kocka kapcsolata, rontom-bontom játékok

A 15-ös játék és a Rubik-kocka kapcsolata (Mágori Marcell előadása). Rontom-bontom játékok: Dawson-sakk és madzagvágó játék.

november 26. Elővizsga
december 3. Játékok különféle kompozíciói

Játékok összege, szorzata és szelektív kompozíciója, Kalmár–Steinhaus-függvény. A LEGO játék különféle változatai.

december 10. Szoliter, sejtautomaták

Conway-féle életjáték, sejtautomaták, édenkert-tétel, Langton hangyája. Szoliter, szoliterhadsereg.