Dvanáctá sada domácích úloh k MB103
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 se čtyřmi, jedna se šesti
sirkami. Opět můžeme odebrat 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ů. Prohrává
ten, kdo smaže poslední číslo. Pro kterého hráče existuje výherní strategie?
1