Hra (úkol)

Hra  je typ olympijských úloh v matematice , ve kterých je nutné analyzovat strategii hry a / nebo jmenovat vítěze této hry. Obvykle končí tradiční otázkou: "Kdo vyhraje, když se hraje správně?"

Charakteristika hry

Zpravidla v úkolech tohoto typu her:

Odchylky od uvedených charakteristik jsou jediné. Část problému spočívá právě v prokázání těchto vlastností.

"Správná hra"

"Správná hra" v problémech této třídy je vítězná strategie z teorie her - strategie, podle které hráč vyhraje v jakýchkoli odvetných akcích soupeře. Správná hra je hra, ve které oba protivníci jednají rozumně a snaží se vyhrát (neustupovat jeden druhému).

Vztah k teorii her

Tyto úlohy zpravidla nevyžadují znalost teorie her . Určitá ustanovení teorie her – intuitivně zřejmá – však lze použít (viz níže).

Typy her

Hry jsou následujících typů:

1. Vtipná hra

V tomto typu her není vítězství závislé na akcích hráčů a je známo předem.

2. Hry se symetrií

K řešení problémů tohoto typu se používá myšlenka symetrie - po určité chvíli hraje jeden hráč symetricky s druhým.

3. Hry o vítězné a prohrané pozice

V procesu řešení problémů tohoto typu jsou nalézány pozice, do kterých si hráč může zajistit vítězství - výhra, a ze kterých nemůže vyhrát žádnou svou akcí - prohra.

Použité nápady

Problémové hry používají různé metody řešení , nicméně existuje několik nápadů, které se často opakují:

  1. invariant  — jeden z hráčů každým tahem uvede stav hry do nějakého stavu (například součet zbývajících neobsazených polí) a takový stav je vítězný. A hra je konečná
  2. výhra je dokázána „od konce“ pomocí myšlenek dynamického programování : nejprve je dokázáno, že na jedné z „předposledních pozic“ se můžete dostat na „poslední“ (vítězství), pak – že z určité množiny z „předposlední“ se můžete dostat pouze na „předposlední“ a tak dále, dokud neprokážeme, že pozice „předchozí ... předposlední“ je výchozí. (Viz funkce Grandi ).
  3. k prokázání její existence není nutné vyvíjet strategii (v tomto případě stačí prokázat tzv. „čistou existenci“ strategie, aniž bychom ji explicitně konstruovali).
  4. pokud se v konečné deterministické hře se dvěma účastníky prokáže, že jeden z účastníků nemůže vyhrát, vyhraje ten druhý.
  5. tzv. přihrávka: pokud v nějaké situaci může hráč A předat tah soupeři, pak A není v horší pozici než jeho soupeř.
  6. tzv. půjčování strategie : předpokládejme, že druhý hráč má strategii; ukazujeme, že ten první se může chopit iniciativy a sám tuto strategii použít.