Nim Wythoff

Den aktuella versionen av sidan har ännu inte granskats av erfarna bidragsgivare och kan skilja sig väsentligt från versionen som granskades den 23 oktober 2017; kontroller kräver 2 redigeringar .

Wythoff 's nim , eller Wythoffs spel , är ett strategiskt matematikspel för två spelare med två högar med marker. Spelare turas om att ta marker från en eller båda högarna; i det senare fallet tas lika stora marker från båda högarna. Den som tar de sista eller sista markerna vinner.

Martin Gardner , i From Penrose Mosaics to Secure Chiphers (kapitel 8), säger att spelet är känt i Kina som 捡石子jianshizi [1] [2] ("att ta stenar"). [3] Den holländska matematikern Willem Wiethoff publicerade en matematisk analys av spelet 1907.

Optimal strategi

Vilken position som helst i spelet kan beskrivas med ett par nummer ( n , m ), med n ≤, där n och m  är antalet marker i högar. Spelets strategi är baserad på definitionen av bra och dåliga positioner : dålig position (eng.: cold position ) - en förlorande position även med optimala handlingar av spelaren som är i den; en bra ( het ) position är en från vilken spelaren vinner med optimala åtgärder. Den optimala strategin för en spelare i en bra position är att flytta spelet till någon av de dåliga positionerna, vilket ger rätten att flytta till motståndaren, som i sin tur kommer att flytta spelet till en bra position för den första spelaren.

Klassificeringen av positioner i bra och dåliga kan göras rekursivt med hjälp av följande tre regler:

  1. (0,0) - dålig position (förlust).
  2. Varje position från vilken en dålig position kan nås i ett drag är en bra position.
  3. En position från vilken varje drag leder till en bra position är en dålig position.

Till exempel är alla positioner i formen (0, m ) och ( m , m ) för m > 0 bra (enligt regel 2). Samtidigt är position (1,2) dålig, för från den kan du bara komma till positionerna (0,1), (0,2) och (1,1), och de är alla bra, som indikeras i föregående mening. De första dåliga positionerna ( n , m ) med de minsta värdena på n och m  är (0, 0), (1, 2), (3, 5), (4, 7), (6,10) och (8, 13).

Formel för dåliga positioner

Wythoff bevisade att dåliga positioner följer ett mönster som definieras av det gyllene snittet . I synnerhet om k  är ett godtyckligt naturligt tal, och

,

där φ är det gyllene snittet, då ( n k , m k ) är den k -: te dåliga positionen. Dessa två sekvenser kallas de nedre och övre Wythoff-sekvenserna och är numrerade A000201 respektive A001950 i Encyclopedia of Integer Sequences .OEISicon light.svg OEISicon light.svg

De två sekvenserna nk och mk är Beatty -sekvenserna associerade med ekvationen

De två sekvenserna är komplementära : varje positivt heltal visas exakt en gång i vilken sekvens som helst.

Se även

Referenser

  1. ↑ Nikolaj Nikolajevitj Vorobyov. Fibonacci-siffror. M.: Nauka, 1978
  2. ↑ Matulis A., Savukinas A., Queen - in i hörnet, "jianshizi" och Fibonacci-nummer, Kvant, 1984
  3. ↑ Wythoffs spel på Cut-the-knot Arkiverad 9 februari 2021 på Wayback Machine , citerar Martin Gardners bok Penrose Tiles to Trapdoor Ciphers

Länkar