Dvanáctá sada domácích úloh k přednášce Matematika III
Příklad 1. Uvažujme hru nim se třemi hromádkami, jedna s pěti, jedna se šesti sirkami a jedna
se sedmi sirkami. Můžeme odebírat jednu až tři sirky (z jedné hromádky). Určete SpragueovuGrundyuovu
hodnotu počátečního stavu hry. Pro kterého hráče existuje výherní strategie?
Příklad 2. Uvažme následující hru dvou hráčů: na tabuli jsou napsána přirozená čísla od jedné
do sedmi. 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?
Příklad 3. (nepovinné, stačí spočítat předchozí dva příklady k uznání sady) Napište program, který
pro libovolné přirozené n realizuje vítěznou strategii za hráče, který ji má, ve hře z předchozího
příkladu, kde číslo osm nahradíme obecným n (tj. program, který umožní hrát danou hru, člověk
proti počítači, počítač hraje za toho hráče, který má vítěznou strategii).