Teorie grafů

Diplomová práce, MFF UK
Lukáš Jirovský
Matematika - MIUZV


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ý?

Řešení úlohy č. 1

Graf s vyznačeným jádrem:
Graf ke hře NIM

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)?

Řešení úlohy č. 2

Graf s vyznačeným jádrem:
Graf ke hře NIM

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)?

Řešení úlohy č. 3

Graf s vyznačeným jádrem:
Graf ke hře NIM

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.


Úvod

Základní pojmy

Vybrané problémy

Procvičování