Klikněte

"Click" [1] :407 (z angl.  Chomp ) - matematická hra , která spočívá v tom, že dva hráči sní čokoládovou tyčinku podle určitých pravidel.

Moderní geometrická formulace hry byla vytvořena Davidem Galem v roce 1974 a dřívější aritmetická formulace Frederickem Schuchem  [ v roce 1952. Anglické jméno Chomp  - doslovně znamená "Chawk" (od "slurp") - bylo vytvořeno Martinem Gardnerem .

Geometrická verze

Pole hry "Click" - obdélníková tabulka čokolády; dva hráči se střídají ve výběru jednoho plátku a jedí společně se všemi plátky nahoře a napravo od něj [2] . Hráč, který sní „otrávený“ levý spodní plátek [3] [1] :407 prohrává .

Níže je uveden příklad hry na desce 5 × 3: „otrávený“ plátek je označen červeně a plátky, které hráč snědl, jsou tečkované.

Začátek hry První hráč Druhý hráč První hráč Druhý hráč

V tomto příkladu je první hráč nucen sníst „otrávený“ plátek, a proto prohrává.

Aritmetická verze

Hru „Click“ lze přeformulovat aritmeticky: zpočátku je uhodnuto přirozené číslo ; dva hráči se střídají v pojmenovávání dělitelů čísla , které nejsou násobky již pojmenovaných . Hráč, který je nucen jmenovat číslo 1 [4], prohrává .

Pro čísla s rozkladem na rozklad , tj. mající pouze dva prvočíselné dělitele , se aritmetická verze redukuje na geometrickou v obdélníku (k+1) × (l+1). Řezy přitom odpovídají děličkám, snědené řezy zakázaným děličkám, „otrávený“ řez odpovídá číslu 1, viz tabulka níže.

9 osmnáct 36 72 144
3 6 12 24 48
jeden 2 čtyři osm 16

Analýza hry

Z hlediska teorie her je Click nezaujatá , deterministická hra s dokonalými informacemi . Hra má navíc konečný počet stavů, a proto z obecných tvrzení teorie her vyplývá, že jeden z hráčů musí mít vítěznou strategii.

Půjčení strategie umožňuje ukázat, že první hráč má vítěznou strategii (s výjimkou případu pole 1 × 1), ale důkaz není konstruktivní . Konkrétně předpokládejme, že druhý hráč má vítěznou strategii a dokažte, že první hráč ji má také, za předpokladu, že první hráč snědl pouze pravý horní plátek [5] v prvním tahu a považoval tah druhého hráče za vedoucí k vítězná strategie [6] ; pak může první hráč sám provést takový první tah, čímž si „vypůjčí“ strategii druhého hráče. To znamená, že druhý hráč nemůže mít vítěznou strategii, a proto první má [1] :410 .

Od roku 1974 jsou vítězné strategie první známé pouze pro dílčí formy pole [1] :408 :

  1. Pole je čtvercové. V prvním tahu musí první hráč ukousnout pole se stranou o jednu méně; budou dva pruhy šířky 1, spojené jeden po druhém ve tvaru obráceného písmene "G". Dále musí první hráč symetricky opakovat tahy druhého [1] :408 .
  2. Pole má tvar 2 × n. V prvním tahu musí první hráč ukousnout pravý horní plátek. Dále po každém tahu druhého hráče musí obnovit situaci tak, aby ve spodním řádku bylo o jeden plátek více [1] :410 .

V počítači byly také nalezeny vítězné strategie pro malé velikosti polí. Nejmenší známá velikost pole, pro kterou není výherní strategie jedinečná, je (8, 10) [7] .

Poznámky

  1. ↑ 1 2 3 4 5 6 Gardner M. Matematické romány . Za. z angličtiny. Yu. A. Danilova. Ed. Ano, A. Smorodinsky. M., Mir, 1974. 456 s. od nemoc.; str. 407-412
  2. ↑ V jiné verzi - dole a vpravo.
  3. ↑ V jiné verzi - vlevo nahoře.
  4. ↑ Vítězné cesty pro vaše matematické hry , svazek 3 (2. vydání), od ER Berlekamp, ​​​​JH Conway a RK Guy. str. 275. 2018. ISBN 9780429945618 . CRC Press, 2018. Pp. 39
  5. ↑ Plátek, naproti tomu "otrávené"; v jiné verzi - vpravo dole.
  6. ↑ Kromě případů, kdy je pole 1 × 1 a druhý hráč se nehýbe, protože první hráč již prohrál.
  7. ↑ Elwyn R. Berlekamp a kol.: Gewinnen - Strategien für mathematische Spiele , Band 3. Vieweg, Braunschweig/Wiesbaden 1986, ISBN 3-528-08533-9 , S. 172f

Odkazy