4. Procvičování / Výhra NIMu (teorie her)
Teorie
Úloha č. 1
Který hráč má vyhrávající strategii ve hře NIM(1,1)? První nebo druhý?
Nápověda k úloze č. 1
Graf ke hře:
Řešení úlohy č. 1
Graf s vyznačeným jádrem:
Vidíme, že vrchol (1,1), kterým hra začíná, je v jádru grafu - vyhrávající strategii má proto druhý hráč.
U této hry ani nemá jinou možnost, než vyhrát (nemá šanci udělat chybu).
Úloha č. 2
Který hráč má vyhrávající strategii u hry NIM(2,1)?
Nápověda k úloze č. 2
Graf ke hře:
Řešení úlohy č. 2
Graf s vyznačeným jádrem:
Vidíme, že vrchol (2,1) není součástí jádra grafu - vyhrávající strategii má proto první hráč.
Odpovídá to hře - odebere-li první hráč jednu sirku z hromádky, kde byly dvě, druhému nezbyde, než vybrat jednu z dvou hromádek po jedné sirce a první hráč pak odebere zbývající.
Úloha č. 3
Který hráč má vyhrávající strategii u hry NIM(3,1)?
Nápověda k úloze č. 3
Graf ke hře:
Řešení úlohy č. 3
Graf s vyznačeným jádrem:
Vidíme, že vrchol (3,1) není v jádru grafu - vyhrávající strategii má první hráč.
Prohlédněte si graf - potřebuje druhého hráče přimět, aby již ve svém prvním kroku mohl vzít právě jednu sirku.