Hva er Subtraksjonsspill?
Subtraksjonsspillet er Nim med en grense for hvert trekk. Du tar fortsatt gjenstander fra en haug du velger, men minst én og høyst k, der k er 2, 3, 4 eller 5, valgt i bordoppsettet (3 som standard). Du kan bare ta en hel haug når den har k gjenstander eller færre.
Alt annet er som i standardspillet: starthaugene kommer fra det samme valget i oppsettet (1, 3, 5 og 7 som standard), og misère-bryteren avgjør om det å ta den siste gjenstanden taper (standard her) eller vinner. Taket endrer aritmetikken i spillet. En stor haug kan ikke lenger tømmes i ett trekk, så den kan ikke brukes til å rette opp stillingen med ett slag, og det som betyr noe for hver haug, er størrelsen delt på k + 1: resten.
Regelendringer
| Regel | Vanlig Nim | Subtraksjonsspill |
|---|---|---|
| Trekk | Vanlig NimTa én eller flere gjenstander fra én haug, så mange du vil, opptil hele haugen. | SubtraksjonsspillTa minst 1 og høyst k gjenstander fra én haug; k er 2, 3, 4 eller 5, valgt i bordoppsettet (3 som standard). |
| Hauger | Vanlig NimFlere hauger: 1, 3, 5 og 7 gjenstander som standard, eller et annet sett valgt i bordoppsettet. | SubtraksjonsspillDe samme haugene, valgt med det samme valget. |
| Mål | Vanlig NimMisère som standard: den som tar den siste gjenstanden, taper. Oppsettet kan bytte til normalspill, der den som tar den siste gjenstanden, vinner. | SubtraksjonsspillDet samme, med den samme misère-bryteren. |
| Vinnende spill | Vanlig NimNormalspill: etterlat haugene med en nim-sum (bitvis XOR av størrelsene) på null. Misère: det samme, til bare hauger med én gjenstand ville vært igjen; etterlat da et oddetall av dem. | SubtraksjonsspillNormalspill: hver haug teller som resten av størrelsen delt på k + 1, og du etterlater disse restene med en nim-sum på null; én enkelt haug er tapt for den som står for tur, nøyaktig når størrelsen er et multiplum av k + 1. Misère: én enkelt haug er tapt for den som står for tur, nøyaktig når størrelsen er én mer enn et multiplum av k + 1. |
Historie
Tellespill med et tak på hvert trekk er gamle. Claude-Gaspard Bachet de Méziriacs Problèmes plaisants et délectables, en samling matematiske fornøyelser først utgitt i Paris i 1612, beskriver et spill der to spillere annenhver gang legger et tall fra 1 til 10 til en løpende sum, og den første som når 100, vinner. Den vinnende planen er å nå summene 12, 23, 34 og så videre opp til 89, i steg på 11: den samme aritmetikken som én haug på 100 der hvert trekk tar fra 1 til 10.
Selve Nim fikk navnet og den fullstendige teorien sin av Charles L. Bouton i 1901. Arbeidet til Roland Sprague (1935) og Patrick Grundy (1939) viste at hvert spill av denne typen, subtraksjonsspillet inkludert, oppfører seg som en Nim-haug av en viss størrelse, og det er slik versjonen med flere hauger løses. Subtraksjonsspill er et standardeksempel i teorien om kombinatoriske spill, for eksempel i Winning Ways for your Mathematical Plays av Elwyn Berlekamp, John Conway og Richard Guy.