Wythoffs spel

Wythoffs spel spelas med två högar av räknare

Wythoffs spel är ett matematiskt subtraktionsspel för två spelare som spelas med två högar med räknare. Spelare turas om att ta bort räknare från en eller båda högarna; när du tar bort räknare från båda högarna måste antalet räknare som tas bort från varje hög vara lika. Spelet slutar när en spelare tar bort den eller de sista räknaren och därmed vinner.

En likvärdig beskrivning av spelet är att en enda schackdrottning placeras någonstans på ett stort rutnät av rutor, och varje spelare kan flytta damen mot det nedre vänstra hörnet av rutnätet: söder, väster eller sydväst, valfritt antal steg. Vinnaren är spelaren som flyttar drottningen in i hörnet. De två kartesiska koordinaterna för drottningen motsvarar storleken på två högar i utformningen av spelet som involverar att ta bort räknare från högar.

Martin Gardner hävdar i sin " Matematical Games-kolumn " i mars 1977 i Scientific American att spelet spelades i Kina under namnet 捡石子 jiǎn shízǐ ("plocka stenar"). Den holländska matematikern WA Wythoff publicerade en matematisk analys av spelet 1907.

Optimal strategi

En visualisering av Wythoffs spel Nim. Den nedre rutan längst till vänster är position (1,1) och de röda rutorna är kalla positioner. Observera att den vinnande rutten inte finns med på bilden.

Vilken position som helst i spelet kan beskrivas med ett par heltal ( n , m ) med n ≤ m , som beskriver storleken på båda högarna i positionen eller koordinaterna för drottningen. Strategin i spelet kretsar kring kalla positioner och heta positioner : i en kall position kommer spelaren vars tur det är att röra sig att förlora med bäst spel, medan i en varm position vinner spelaren vars tur det är att flytta med bäst spela. Den optimala strategin från en varm position är att flytta till valfri nåbar kall position.

Klassificeringen av positioner i varmt och kallt kan utföras rekursivt med följande tre regler:

1. (0,0) är en kall position.
2. Varje position från vilken en kall position kan nås i ett enda drag är en varm position.
3. Om varje drag leder till en varm position, då är en position kall.

Till exempel är alla positioner i formen (0, m ) och ( m , m ) med m > 0 varma enligt regel 2. Positionen (1,2) är dock kall, eftersom de enda positionerna som kan nås från den är (0,1), (0,2), (1,0) och (1,1), alla heta. De kalla 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). (sekvens A066096 och A090909 i OEIS ) (Se även OEIS : A072061 )

För misère-spel i detta spel är (0, 1) och (2, 2) kalla positioner, och en position ( n , m ) med m , n > 2 är kall om och endast om ( n , m ) i normalt spel är kallt.

Formel för kalla positioner

Wythoff upptäckte att de kalla positionerna följer ett regelbundet mönster som bestäms av det gyllene snittet . Specifikt, om k är ett naturligt tal och

$n_{k}=\lfloor k\phi \rfloor =\lfloor m_{k}\phi \rfloor -m_{k}\,$

$m_{k}=\lfloor k\phi ^{2}\rfloor =\lceil n_{k}\phi \rceil = n_{k}+k\,$

där φ är det gyllene snittet och vi använder golvfunktionen , då är ( n _k , m _{k ) den} k: ^te kalla positionen. Dessa : A001950 . två nummersekvenser är registrerade i Online Encyclopedia of Integer Sequences som OEIS : A000201 respektive OEIS

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

${\frac {1}{\phi }}+{\frac {1}{\phi ^{2}}}=1\,.$

Som är sant i allmänhet för par av Beatty-sekvenser, är dessa två sekvenser komplementära : varje positivt heltal visas exakt en gång i endera sekvensen.

Se även

• Nim
• Grundys spel
• Subtrahera en kvadrat
• Wythoff array

externa länkar

• Weisstein, Eric W. "Wythoffs spel" . MathWorld .
• Grime, James. "Wythoff's Game (Get Home)" (video) . YouTube . Brady Haran . Arkiverad från originalet 2021-12-15 . Hämtad 21 augusti 2017 .