Klick

"Klick" [1] :407 (från engelskan.  Chomp ) - ett matematiskt spel , som består i att två spelare äta en chokladkaka enligt vissa regler.

Den moderna geometriska formuleringen av spelet myntades av David Gale 1974, och den tidigare aritmetiska formuleringen  av Frederick Schuch 1952. Det engelska namnet Chomp  - som bokstavligen betyder "Chawk" (från "slurp") - myntades av Martin Gardner .

Geometrisk version

Fältet för spelet "Klick" - en rektangulär chokladkaka; två spelare turas om att välja en skiva och äta tillsammans med alla skivorna ovanför och till höger om den [2] . Spelaren som äter den "förgiftade" nedre vänstra skivan [3] [1] :407 förlorar .

Nedan är ett exempel på ett spel på en 5 × 3-bräda: den "förgiftade" skivan är markerad med rött, och skivorna som spelaren äter är prickade.

I det här exemplet tvingas den första spelaren äta den "förgiftade" skivan och förlorar därför.

Aritmetisk version

Spelet "Klick" kan omformuleras aritmetiskt: initialt gissar man ett naturligt tal ; två spelare turas om att namnge divisorer för ett tal som inte är multiplar av de som redan har nämnts . Spelaren som tvingas namnge nummer 1 [4] förlorar .

För tal med faktorisering , d.v.s. har bara två primtalsdelare , reduceras den aritmetiska versionen till den geometriska i rektangeln (k+1) × (l+1). Samtidigt motsvarar skivor delare, uppätna skivor motsvarar förbjudna avdelare, den "förgiftade" skivan motsvarar siffran 1, se tabellen nedan.

Spelanalys

Ur spelteoretisk synvinkel är Click ett opartiskt , deterministiskt spel med perfekt information . Dessutom har spelet ett ändligt antal tillstånd, och därför följer det av spelteorins allmänna uttalanden att en av spelarna måste ha en vinnande strategi.

Genom att låna en strategi kan man visa att den första spelaren har en vinnande strategi (förutom i fallet med ett 1 × 1-fält), men beviset är inte konstruktivt . Anta särskilt att den andra spelaren har en vinnande strategi och bevisa att den första spelaren också har en, förutsatt att den första spelaren bara åt den övre högra skivan [5] i det första draget och ansåg att den andra spelarens drag ledde till den vinnande strategin [6] ; då kan den första spelaren själv göra ett sådant första drag och därigenom "låna" strategin för den andra spelaren. Detta betyder att den andra spelaren inte kan ha en vinnande strategi, och därför gör den första [1] :410 .

Från och med 1974 är de vinnande strategierna för de första kända endast för partiella former av fältet [1] :408 :

1. Fältet är fyrkantigt. Vid det första draget måste den första spelaren bita av en ruta med en sida mindre; det kommer att finnas två remsor med bredd 1, anslutna en efter en i form av en inverterad bokstav "G". Därefter måste den första spelaren symmetriskt upprepa dragen från den andra [1] :408 .
2. Fältet har formen 2 × n. Vid första draget måste den första spelaren bita av den övre högra skivan. Vidare, efter varje drag av den andra spelaren, måste han återställa situationen så att det på den nedersta raden finns en skiva till [1] :410 .

Även vinnande strategier för små fältstorlekar hittades på datorn. Den minsta kända fältstorleken för vilken den vinnande strategin inte är unik är (8, 10) [7] .

Anteckningar

1. ↑ 1 2 3 4 5 6 Gardner M. Matematiska romaner . Per. från engelska. Yu. A. Danilova. Ed. Ja. A. Smorodinsky. M., Mir, 1974. 456 sid. från ill.; sid. 407-412
2. ↑ I en annan version - nedan och till höger.
3. ↑ I en annan version, respektive - uppe till vänster.
4. ↑ Vinnande sätt för dina matematiska pjäser , Volym 3 (2nd edn), av ER Berlekamp, ​​​​JH Conway och RK Guy. pp. 275. 2018. ISBN 9780429945618 . CRC Press, 2018. S. 39
5. ↑ Skiva, mitt emot den "förgiftade"; i en annan version - nedre höger.
6. ↑ Förutom när kvadraten är 1 × 1 och den andra spelaren inte rör sig eftersom den första spelaren redan har förlorat.
7. ↑ Elwyn R. Berlekamp et al.: Gewinnen - Strategien für mathematische Spiele , Band 3. Vieweg, Braunschweig/Wiesbaden 1986, ISBN 3-528-08533-9 , S. 172f

Länkar

• Chomp  - diverse information om spelet  (engelska)