Sada domácích úloh k přednášce Matematika III
k odevzdání v týdnu 11. ­ 15. prosince 2006
Příklad 1. Uvažujme hru nim dvou hráčů s jednou hromádkou s devíti sirkami: hráči se střídají
v tazích, tah je odebrání jedné až tří sirek. Kdo nemůže odebrat žádnou sirku prohrává. Vyjád-
řete tuto hru ve tvaru acyklického grafu a spočítejte Spragueovu-Grundyovu hodnotu všech jeho
vrcholů. Pro kterého hráče existuje výherní strategie?
Příklad 2. Uvažujme hru nim se dvěma hromádkami, jedna s čtyřmi, jedna se šesti sirkami. Opět
můžeme odebírat jednu až tři sirky (z jedné hromádky). Vyjádřete tuto hru ve tvaru acyklického
grafu a spočítejte Spragueovu-Grundyovu hodnotu všech jeho vrcholů. Využijte toho, že tato hra
je součtem dvou her. Pro kterého hráče existuje výherní strategie?
Příklad 3. Uvažme následující hru dvou hráčů: na tabuli jsou napsána přirozená čísla od jedné
do deseti. Hráči se střídají v tazích, tah spočívá ve smazání nějakého čísla na tabuli a také všech
jeho dělitelů. Vyjádřete tuto hru ve tvaru acyklického grafu a spočítejte Spragueovu-Grundyovu
hodnotu všech jeho vrcholů. Pro kterého hráče existuje výherní strategie?