Vad är Wythoffs spel?
Wythoffs spel spelas med två högar. I ditt drag tar du antingen valfritt antal föremål från en hög, som i Nim, eller lika många från båda högarna på en gång. Den som tar det sista föremålet vinner: det här spelet spelas alltid på normalt sätt, så misèreinställningen och starthögarna i standardspelet gäller inte.
Högarnas storlek kommer från storleksinställningen i bordsinställningarna: 5 och 7 (liten), 9 och 12 (mellan, standard) eller 14 och 20 (stor). Ett välkänt sätt att se spelet framför sig är en schackdam som bara får flytta åt vänster, nedåt eller snett nedåt vänster: de två högarna är hennes avstånd till brädets två kanter, och den som flyttar henne in i hörnet vinner.
Regeländringar
| Regel | Nim (standard) | Wythoffs spel |
|---|---|---|
| Högar | Nim (standard)Flera högar: 1, 3, 5 och 7 föremål som standard, eller en annan uppsättning vald i bordsinställningarna. | Wythoffs spelTvå högar: 5 och 7, 9 och 12 (standard) eller 14 och 20, valda som storlek i bordsinställningarna. |
| Drag | Nim (standard)Ta ett eller flera föremål från en hög. | Wythoffs spelTa antingen ett eller flera föremål från en hög, eller lika många från båda högarna. |
| Mål | Nim (standard)Misèrespel som standard: den som tar det sista föremålet förlorar. Inställningarna kan växla till normalt spel, där den som tar det sista föremålet vinner. | Wythoffs spelAlltid normalt spel: den som tar det sista föremålet vinner. |
| Vinnande spel | Nim (standard)Lämna högarna med nimsumman (den bitvisa XOR:en av deras storlekar) noll, med en twist i misèreslutspelet. | Wythoffs spelStällningarna som förlorar för spelaren vid draget är paren 1 och 2, 3 och 5, 4 och 7, 6 och 10, 8 och 13 och så vidare: det k:te paret är heltalsdelarna av k × φ och k × φ², där φ är gyllene snittet. Ingen utgångsställning här är ett sådant par, så den första spelaren kan vinna. |
Historia
Den nederländske matematikern Willem Abraham Wythoff publicerade spelet och dess lösning 1907, i artikeln ”A modification of the game of nim” i Nieuw Archief voor Wiskunde. Han visade att de förlorande ställningarna följer gyllene snittet. De mindre och större talen i de förlorande paren bildar två Beattyföljder som tillsammans räknar upp varje positivt heltal exakt en gång, vilket är skälet till att spelet dyker upp i texter om talteori lika väl som om spel.
Martin Gardner skrev om spelet i sin tidskriftsspalt Mathematical Games i mars 1977 och sade där att det spelades i Kina under namnet jiǎn shízǐ, ”att plocka stenar”. Vi känner inte till någon annan källa för det påståendet.