Kombinatorické hry

Definice: Kombinatorickou hrou budeme rozumět libovolnou hru splǔjící následující pravidla:

  1. Hru hrají dva hráči, kteří se střídají v tazích.
  2. Počet stavů, ve kterých se hra může nacházet, je vždy konečný.
  3. Pravidla hry stanovují pro každého hráče v libovolném stavu hry jaké další tahy může zahrát.
  4. Hra končí vítězně pro hráče, který zahrál naposledy, tedy prohrává ten hráč, který na začátku svého tahu nemá žádný platný tah.
  5. Hraje se s úplnou informací a bez náhody.
Pokud narazíme na hru, která nesplňuje výše uvedená pravidla, tak se nelekněte. Tato definice strikně vymezuje typy her, jež jsou naším primárním cílem se naučit řešit (hrát optimálně).
V některých níže uvedených hrách naschvál uvádím něco na způsob: Zjistěte, pro které N, byste chtěli začínat.. Tím bych chtěl trochu napovědět, že pokud hráči hrájí optimálně, stavy hry se budou dělit na (V)yhrávající a (P)rohrávající z pohledu začínajícího hráče. Zkuste při řešení nalézt pravidlo, podle kterého se jednotlivé stavy hry dělí na V a P a tím se nakonec dopracovat k odpovědi.

Hra #1: Odečítání dělitelů

Hráči si zvolí přirozené číslo N. Ve hře se střídají a při svém tahu hráč může od aktuální hodnoty N odečíst jeho libovolný vlastní dělitel. Zjistěte, pro která N byste chtěli hrát jako první.

Hra #2: Lámání čokolády I

Hra se točí okolo lámání čokolády o rozměrech MxN kostiček. Při svém tahu smí hráč rozlomit libovolný dílek čokolády podél vyznačených linií (však to znáte). Prohrává ten hráč, který nemůže žádný dílek rozlomit. Zjistěte, při jakých velikostech čokolády byste chtěli začínat.

Hra #3: Přičítání dělitelů

V této hře je počáteční číslo pevně dáno a je rovné 2. Hráči se střídají a při svém tahu mohou k aktuální hodnotě N přičíst jeho libovolný vlastní dělitel. Hráč, po jehož tahu hodnota N překročí 2016, vítězí. Dokážete říci, zda existuje vyhrávající strategie pro začínajícího hráče?

Hra #4: Čísla v lahvi

V láhvi jsou lístečky s čísly od 1 do 16. Hráč, který je na tahu, vyndá z lahve nějaké číslo a všechny jeho dělitele. Prohrává hráč, nemůže táhnout. Může si začínající hráč vynutit výhru?

Hra #5: Lámání čokolády II

Hra se točí okolo lámání čokolády o rozměrech 2MxN kostiček. Při svém tahu smí hráč rozlomit libovolný dílek čokolády podél vyznačených linií (však to znáte), ALE nikdy nesmí vzniknout dílek o velikosti 1×1. Prohrává ten hráč, který nemůže žádný dílek rozlomit. Zjistěte, při jakých velikostech čokolády byste chtěli začínat.

Hra #6: Odečítání prvočísel

Hráči si zvolí přirozené číslo N. Ve hře se střídají a při svém tahu hráč může od aktuální hodnoty N odečíst libovolné prvočíslo (včetně 1) menší než N. Zjistěte, pro která N byste chtěli hrát jako první.

Hra #7: Lámání čokolády III (Chomp)

Opět se hra točí kolem lámání čokolády, ale v tomto případě jde o život! Tabulka čokolády leží na stole, rozlámaná na jednotlivé kostičky. Hráč si při svém tahu zvolí libovolný dílek čokolády a zbaští všechny dílky, které se od dané kostičky vyskytují nahoru a napravo (odebraný kus čokolády vždy tvoří obdélník o jednom či více dílků). Problém je, že dílek úplně vlevo dole je otrávený. Zkuste zjistit, zdali se jako začínající hráč můžete vyhnout otravě, pokud má tabulka čokolády tvar A) čtverce či B) obdélníku.

Hra #8: Odebírání sirek

Na stole leží N sirek. Hrači se postupně střídají v odebírání sirek, přičemž mohou při svém tahu odebrat 1, 2, nebo 3 sirky. Vyhrává ten hráč, po jehož tahu na stole nezbude žádná sirka.

Následující 2 hry jsou zde uvedeny pro zajímavost, proto se je prosím nesnažte řešit, pokud neznáte odpovědi pro všechny hry uvedené výše.

Hra #9: Odebírání sirek II

Na stole leží N sirek. Hrači se postupně střídají v jejich odebírání, přičemž hráč při svém tahu nesmí odebrat více sirek než kolik bylo odebráno v předchozím tahu. Začínající hráč musí odebrat alespoň jednu sirku, ale nesmí odebrat všechny (jinak by to byla pěkně nudná hra). Vyhrává ten hráč, po jehož tahu na stole nezbude žádná sirka.

Hra #10: Odebírání sirek III (Fibonacci Nim)

Na stole leží N sirek. Hrači se postupně střídají v jejich odebírání, přičemž hráč při svém tahu nesmí odebrat více sirek než kolik bylo odebráno v předchozím tahu. Začínající hráč musí odebrat alespoň jednu sirku, ale nesmí odebrat všechny (jinak by to byla pěkně nudná hra). Vyhrává ten hráč, po jehož tahu na stole nezbude žádná sirka.

Hra #11: Odebírání z hromádek

Na stole leží 3 hromádky se 4, 2 a 1 kamenem. Hráč při svém tahu může odebrat 1 nebo 2 kameny. Hráč, který zvedne poslední kámen vyhrává.

Hra #12: Klasický NIM

Na stole leží M hromádek s kameny. i-tá hromádka obsahuje N[i] kamenů. Hráč si při svém tahu vybere hromádku a odebere z ní libovolný počet kamenů (klidně odebere celou hromádku). Vyhrává ten, který ze stolu zvedne poslední kámen. Určete v závislosti na počtu hromádek a kamenů v nich, zdali začínající hráč vyhraje, bude-li hrát optimálně.

Hra #13: Upravený NIM

Na stole leží M hromádek s kameny. i-tá hromádka obsahuje N[i] kamenů. Hráč si při svém tahu vybere hromádku a odebere z ní libovolný počet kamenů, ale vždy alespoň jeden. Vyhrává ten, který ze stolu zvedne poslední kámen. Určete v závislosti na počtu hromádek a kamenů v nich, zdali začínající hráč vyhraje, bude-li hrát optimálně.

Hra #14: Otáčení mincí

Je dána řada N mincí, kde některé jsou pannou a jiné orlem vzhůru. Hráč si při svém tahu může zvolit libovolnou minci, která je pannou vzhůru, a otočit ji. Navíc, si může zvolit libovolnou minci nalevo od té první a otočit ji (ať byla orientovaná jakkoliv). Ukažte, že tato hra je ekvivalentní s předchozí hrou NIM (klasický).

Hra #15: Krájení koláče

Hrači stojí nad koláčem, který má na svém okraji N zářezů. Hráč, který je na tahu, si zvolí dvojici zářezů na libovolném kusu koláče a jedním tahem ho napříč těmito zářezy rozřízne. Hráč, který nemůže provést žádný řez, prohrává.

Hra #16: Odebírání sirek IV

Na stole leží N hromádek sirek. i-tá hromádka obsahuje N[i] sirek. Hráč na tahu si zvolí libovolnou hromádku a odebere z ní 1, 2, nebo 3 sirky. Hráč, který odebere poslední sirku, vyhrává.

Zdroje

courses/a4b36acm2/kombinatoricke_hry.txt · Last modified: 2018/02/21 22:30 (external edit)