Teória hier (ťažká)

Autor: Jozef Rajník
Letná škola matematiky, 19. 7. 2022
PDF s celou prednáškou

Úloha 1

Baška a Miško sa hrajú hru. Na začiatku majú kôpku $n$ zápaliek. Začína Baška a striedajú sa s Miškom v ťahoch. V každom ťahu z nej zoberie hráč

1. $1$, $2$, $3$ alebo $4$ zápalky;

2. $1$, $3$, $4$ alebo $7$ zápaliek.

Prehráva hráč, ktorý nemôže spraviť ťah (teda sa dostane na ťah, keď sa už minuli zápalky). Ktorý hráč má víťaznú stratégiu?

Úloha 2

Gertrúda a Pekelník hrajú hru na šachovnici rozmerov $n \times n$. Gertrúda začína, potom sa s Pekelníkom striedajú v ťahoch. V každom svojom ťahu položí hráč na ľubovoľné voľné políčko kameň. Voľné políčko je také, na ktorom nie je kameň a ktorého (hranou) susedné políčka obsahujú najviac jeden kameň. Hráč, ktorý vo svojom ťahu nemôže položiť kameň, prehráva. V závislosti od prirodzeného čísla $n$ určte, ktorý z hráčov má víťaznú stratégiu.

KMS 16/17-Z3-4

Úloha 3

Rasťo má na záhrade ešte stále vyrytú šachovnicu s $2007\times 2007$ políčkami. So sestrou Slávkou si povedali, že si zmerajú sily. Presne v strede šachovnice sa nachádza obrovský kameň, ktorý najprv Rasťo posunie o jedno políčko (rovnobežne so stranami šachovnice). Slávka ho potom bude musieť posunúť o dve políčka, Rasťo o štyri políčka, Slávka o osem políčok -- v $k$-tom ťahu ho vždy budú musieť posunúť o $2^{k-1}$ políčok. Ten, kto je na ťahu, prehráva, ak už nemôže posunúť kameň. Nájdite víťaznú stratégiu pre Slávku alebo pre Rasťa.

KMS 07/08-Z1-10

Úloha 4

Kubo a Matúš zakopli o prirodzené číslo $n$, a tak sa rozhodli, že si zahrajú hru. V tejto hre budú striedavo písať jednu z číslic $0$ alebo $1$ na rolku toaleťáka (nekonečného). Každý napíše svoju číslicu hneď za poslednú súperovu. Prehráva hráč, ktorý napíše číslicu, po ktorej sa na toaleťáku objavia dve rovnaké $n$-tice za sebou idúcich číslic. Ukážte, že

1. Hra vždy skončí.

2. Ak začína Kubo a $n$ je nepárne, tak Matúš dokáže vyhrať, aj keby Kubo hral najlepšie ako dokáže.

KMS 11/12-L3-10

Úloha 5

Petržlena už prestalo baviť hrať obyčajné piškvorky s CéDečkom. Preto si vymyslel inú hru, podobnú piškvorkám. Hrá sa na nekonečnom štvorčekovom papieri. Petržlen začína a označí nejaké neoznačené políčko krížikom, potom CéDečko označí nejaké neoznačené políčko krúžkom a takto sa ďalej striedajú. Vyhráva hráč, ktorého znak vyplní štvorec $2 \times 2$. Dokáže Petržlen vo svojej hre vždy vyhrať?

KMS 11/12-Z1-10

Úloha 6

Kružnica, rozdelená na $n$ oblúkov bodmi postupne pomenovanými $1,2,3,\dots,n$, reprezentuje hraciu arénu pre dvoch hráčov, ktorí sa striedajú v ťahaní. V jednom ťahu si hráč vyberie dva zatiaľ voľné body (také, ktoré ešte nie sú koncom žiadnej úsečky) s rovnakou paritou a spojí ich úsečkou. Môže ale spojiť iba také body, aby novovzniknutá úsečka nepretínala žiadnu z predchádzajúcich úsečiek. Prehrá ten hráč, ktorý už nemôže spraviť ťah. Ak obaja hráči používajú optimálnu stratégiu, ktorý z nich vyhrá?

KMS 07/08-L1-11

Úloha 7

Ondro a Feráč majú nekonečnú šachovnicu a hrávajú na nej nasledovnú hru. Každý hráč ovláda jedného koňa, Ondrejov začína na políčku $(0,0)$, Feráčov na $(X, Y)$. Hráči sa striedajú v ťahoch, prvý ťahá Feráč. V jednom ťahu je dovolené spraviť ľubovoľný (nenulový) počet normálnych šachových krokov pre koňa, všetky však musia byť presne v tom istom smere a vzájomná euklidovská vzdialenosť medzi oboma koňmi sa musí každým krokom zmenšiť. Hráč prehrá vtedy, keď nemôže spraviť žiadny krok. Predpokladajte, že obaja hráči hrajú optimálne. Kto vyhrá?

KMS 08/09-Z3-14

Úloha 8

Petržlena s CéDečkom už prestalo baviť hrať piškvorky. Preto CéDečko vymyslel novú kartovú hru. V tejto hre je $2n$ kariet položených na stole v rade za sebou. Na každej karte je zhora napísané prirodzené číslo. Jeden ťah spočíva v tom, že si hráč na ťahu zoberie kartu z kraja radu. Prvý ťahá CéDečko a ďalej sa s Petržlenom striedajú. Hra skončí, keď sa minú všetky karty na stole. Skóre hráča je súčet čísel na kartách, ktoré si potiahol. Dokážte, že CéDečko môže mať vždy aspoň také skóre ako Petržlen.

KMS 11/12-Z3-7

Úloha 9

Dvaja hráči začínajú s číslom $2$ a striedajú sa v ťahoch. Hráč na ťahu pripočíta k aktuálnemu číslu niektorého kladného vlastného deliteľa. Hráč, ktorý ako prvý prekročí číslo $4247$, prehral. Ktorý z hráčov má víťaznú stratégiu? A čo v prípade, že hráč, čo prekročí $4247$ vyhrá?

PraSe, Seriál Teorie Her, Hra 10

Úloha 10

Na tabuli je narysovaných $5$ kružníc, $7$ štvorcov a $9$ trojuholníkov, pričom žiadne dva z týchto útvarov nemajú spoločný bod. Marek a Paľo sa hrajú hru, v ktorej striedavo robia ťahy. Urobiť ťah znamená zotrieť ľubovoľné dva obrazce a nahradiť ich jedným novým. Nový útvar sa na tabuľu nakreslí tak, aby so žiadnym iným útvarom na tabuli nemal spoločný bod. V jednom ťahu možno nahradiť

• dve kružnice kružnicou,

• dva trojuholníky štvorcom,

• kružnicu a trojuholník trojuholníkom,

• dva štvorce trojuholníkom,

• kružnicu a štvorec štvorcom,

• štvorec a trojuholník kružnicou.

Paľo vyhrá, ak výsledkom bude štvorec. Marek vyhrá, ak na tabuli zostane trojuholník. Ukážte, pre ktorého hráča existuje víťazná stratégia, ak hru začína Marek. Popíšte túto stratégiu.

KMS 10/11-Z3-5