Autor obrázku: Chris Martin http://en.wikipedia.org/wiki/User:BooyabazookaKombinatorické myšlení

Kombinatorika trochu jinak

Hry II

diskuze, ke stažení v PDF: zadání

Úloha č. 1

Radek s Hankou mají proužek papíru skládajích se z n políček. Každý ve svém tahu může proužek na nějaké hranici mezi políčky rozstřihnout. Ten, kdo první ustřihne jediné políčko, prohrál. Určete, zda má první hráč vyhrávající strategii pro

  1. (a) n=6
  2. (b) n=10
  3. (c) n=14
  4. (d) n=7

Výsledek: (skrýt)

(a), (b), (c) vyhraje první hráč, (d) vyhraje druhý hráč.

Výsledek
Řešení: (skrýt)

Úlohu lze úspěšně řešit zkoušením možností. My si ovšem ukážeme, jak hru za prvního hráče vždy vyhrát, je-li n sudé číslo.

Naše strategie za prvního hráče bude následující. Prvním tahem rozstřihneme pásek přesně uprostřed. Jelikož je n sudé, jsou levá a pravá půlka pásku stejné.

Poté soupeř rozstřihne jeden z pásků dále a my jako odpověď rozstřihneme úplně stejným způsobem pásek druhý. Odstřižky z levé půlky budeme dávat na levou hromádku a odstřižky z pravé půlky na pravou. Obě hromádky vypadají po našem tahu stejně.

Následně opět soupeř rozstřihne jeden z pásků a my odpovíme stejným rozstřižením odpovídajícího pásku z druhé hromádky.

Takto budeme postupovat i dále.

Rozhodně platí, že vždy po našem tahu budou obě hromádky vypadat stejně. Co to ale znamená? Pokud náš soupeř našel legální tah v jedné hromádce, my můžeme zcela jistě nalézt legální tah v té druhé. Zatímco soupeř musí vymýšlet, my můžeme jeho nápady jen opakovat. Jelikož hra musí dříve či později skončit a tahy nemohou dojít nám, musí dojít soupeři. Takto tedy první hráč zvítězí.

Řešení

Úloha č. 2

Do kruhu je napsáno n \geq 3 minusů. Dva hráči střídavě provádějí tahy - mohou vždy jeden nebo dva sousední minusy přepsat na plusy. Kdo nemůže táhnout, prohrál. V závislosti na n určete, kdo má vyhrávající strategii.

Výsledek: (skrýt)

Vždy vyhraje druhý hráč.

Výsledek
Řešení: (skrýt)

Za druhého hráče použijeme podobný trik jako v předchozí úloze. Poté co první hráč jeden či dva sousední minusy přepíše na plusy můžeme zbývající minusy napsat do řady místo na kružnici.

Je-li nyní v řadě lichý počet minusů, přepíšeme ten prostřední. Tím vytvoříme dvě stejné půlky a na tahy soupeře pak budeme vždy odpovídat tahy symetrickými v druhé půlce. Podobně jako v první úloze si tím zajistíme výhru.

No a pokud je v řadě sudý počet minusů, pak prostě přepíšeme prostřední dvojici a opět zbudou dvě stejné půlky a my vítězíme.

Řešení

Úloha č. 3

Lukáše s Hankou už přestalo bavit hrát při hodinách obyčejné piškvorky, a tak vymysleli obměnu – hrají na čtverečkovaném papíře 10 \times 10, a pravidelně se střídají v tazích. V každém tahu hráč nakreslí svůj symbol do volného pole. Lukáš vyhraje, pokud vytvoří ze svých symbolů čtverec 2 \times 2, a Hanka vyhraje, když se jí podaří mu v tom zabránit. Lukáš začíná. Kdo z nich má vyhrávající strategii?

Výsledek: (skrýt)

Vždy vyhraje Hanka.

Výsledek
Řešení: (skrýt)

K tomu, abychom za Hanku vždy zvítězili opět využijeme symetrii, tentokrát ji ovšem budeme muset vytvořit.

Rozdělíme políčka našeho plánu do dvojic. Na obrázku jsou spolu ve dvojici buďto políčka ve společném obdélníku 2\times 1 (říkejme mu dlaždice), anebo ta označená stejným písmenem.

Hanka vždy svým tahem zahraje do druhého políčka z dvojice, do níž Lukáš právě zahrál. Jelikož pak bude tato dvojice již plná, musí Lukáš „načít“ novou a Hanka pak svůj postup opakovat.

Tím Hanka docílí toho, že v žádné dlaždici nebudou dva Lukášovy symboly. Jelikož jakýkoliv čtverec 2 \times 2 zakrývá alespoň jednu celou dlaždici, nemůže být celý složen z Lukášových symbolů.

Tato strategie tedy vede k výhře Hanky.

Řešení