Vad är Subtraktionsspel?
Subtraktionsspelet är Nim med en gräns för varje drag. Du tar fortfarande föremål från valfri hög, men minst ett och högst k, där k är 2, 3, 4 eller 5, valt i bordsinställningarna (3 som standard). Du får ta en hel hög bara när den innehåller k föremål eller färre.
Allt annat är som i standardspelet: starthögarna kommer från samma inställning (1, 3, 5 och 7 som standard), och misèreinställningen avgör om den som tar det sista föremålet förlorar (standard här) eller vinner. Taket ändrar spelets aritmetik. En stor hög kan inte längre tömmas i ett drag, så den kan inte användas för att rätta till ställningen i ett enda slag, och det som spelar roll för varje hög är dess storlek delad med k + 1: resten.
Regeländringar
| Regel | Nim (standard) | Subtraktionsspel |
|---|---|---|
| Drag | Nim (standard)Ta ett eller flera föremål från en hög, så många du vill, upp till hela högen. | SubtraktionsspelTa minst 1 och högst k föremål från en hög; k är 2, 3, 4 eller 5, valt i bordsinställningarna (3 som standard). |
| 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. | SubtraktionsspelSamma högar, valda med samma inställning. |
| 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. | SubtraktionsspelSamma, med samma misèreinställning. |
| Vinnande spel | Nim (standard)Normalt spel: lämna högarna med nimsumman (den bitvisa XOR:en av deras storlekar) noll. Misèrespel: samma sak, tills bara högar med ett föremål skulle bli kvar; lämna då ett udda antal av dem. | SubtraktionsspelNormalt spel: varje hög räknas som resten av dess storlek delad med k + 1, och du lämnar de resterna med nimsumman noll; en ensam hög är förlorad för spelaren vid draget precis när dess storlek är en multipel av k + 1. Misèrespel: en ensam hög är förlorad för spelaren vid draget precis när dess storlek är ett mer än en multipel av k + 1. |
Historia
Räknespel med ett tak för varje drag är gamla. Claude-Gaspard Bachet de Méziriacs Problèmes plaisants et délectables, en samling matematiska förströelser som först gavs ut i Paris 1612, beskriver ett spel där två spelare i tur och ordning lägger till ett tal från 1 till 10 till en löpande summa, och den som först når 100 vinner. Den vinnande planen är att nå summorna 12, 23, 34 och så vidare upp till 89, i steg om 11: samma aritmetik som en ensam hög på 100 där varje drag tar 1 till 10.
Nim självt fick sitt namn och sin fullständiga teori av Charles L. Bouton 1901. Roland Spragues (1935) och Patrick Grundys (1939) arbeten visade att varje spel av det här slaget, subtraktionsspelet inräknat, beter sig som en Nimhög av en viss storlek, och det är så versionen med flera högar löses. Subtraktionsspel är ett standardexempel i teorin om kombinatoriska spel, till exempel i Winning Ways for your Mathematical Plays av Elwyn Berlekamp, John Conway och Richard Guy.