Mikä on Vähennyspeli?
Vähennyspeli on Nim, jossa jokaisella siirrolla on raja. Otat yhä nappuloita valitsemastasi kasasta, mutta vähintään yhden ja enintään k, missä k on 2, 3, 4 tai 5 pöydän asetuksista valittuna (oletuksena 3). Koko kasan saat ottaa vain, kun siinä on k nappulaa tai vähemmän.
Kaikki muu on kuten tavallisessa pelissä: aloituskasat tulevat samasta asetuksesta (oletuksena 1, 3, 5 ja 7), ja misère-valinta ratkaisee, häviääkö viimeisen nappulan ottaja (täällä oletus) vai voittaako hän. Yläraja muuttaa pelin aritmetiikkaa. Suurta kasaa ei voi enää tyhjentää yhdellä siirrolla, joten sillä ei voi korjata asemaa yhdellä iskulla, ja kunkin kasan kohdalla ratkaisevaa on sen koon jakojäännös luvulla k + 1.
Sääntömuutokset
| Sääntö | Tavallinen Nim | Vähennyspeli |
|---|---|---|
| Siirrot | Tavallinen NimOta yksi tai useampi nappula yhdestä kasasta, niin monta kuin haluat, koko kasaan asti. | VähennyspeliOta yhdestä kasasta vähintään 1 ja enintään k nappulaa; k on 2, 3, 4 tai 5 pöydän asetuksista valittuna (oletuksena 3). |
| Kasat | Tavallinen NimUseita kasoja: oletuksena 1, 3, 5 ja 7 nappulaa tai jokin muu pöydän asetuksista valittu yhdistelmä. | VähennyspeliSamat kasat, valittuna samalla asetuksella. |
| Tavoite | Tavallinen NimOletuksena misère-peli: viimeisen nappulan ottaja häviää. Asetuksista voi vaihtaa normaaliin peliin, jossa viimeisen nappulan ottaja voittaa. | VähennyspeliSama, samalla misère-valinnalla. |
| Voittava peli | Tavallinen NimNormaali peli: jätä kasoille nim-summa (kokojen bittikohtainen XOR) nolla. Misère-peli: sama, kunnes jäljelle jäisi vain yhden nappulan kasoja; jätä silloin niitä pariton määrä. | VähennyspeliNormaali peli: kukin kasa lasketaan kokonsa ja luvun k + 1 jakojäännöksenä, ja jätät näille jakojäännöksille nim-summan nolla; yksittäinen kasa on vuorossa olevalle häviö täsmälleen silloin, kun sen koko on luvun k + 1 monikerta. Misère-peli: yksittäinen kasa on vuorossa olevalle häviö täsmälleen silloin, kun sen koko on yhtä suurempi kuin luvun k + 1 monikerta. |
Historia
Laskentapelit, joissa jokaisella siirrolla on yläraja, ovat vanhoja. Claude-Gaspard Bachet de Méziriacin Problèmes plaisants et délectables, ensimmäisen kerran Pariisissa vuonna 1612 julkaistu matemaattisten ajanvietteiden kokoelma, kuvaa pelin, jossa kaksi pelaajaa lisää vuorotellen juoksevaan summaan luvun 1–10, ja ensimmäisenä 100:aan päässyt voittaa. Voittava suunnitelma on päästä summiin 12, 23, 34 ja niin edelleen 89:ään asti 11:n välein: sama aritmetiikka kuin yhdellä 100 nappulan kasalla, josta jokainen siirto ottaa 1–10.
Itse Nim sai nimensä ja täydellisen teoriansa Charles L. Boutonilta vuonna 1901. Roland Spraguen (1935) ja Patrick Grundyn (1939) työ osoitti, että jokainen tällainen peli, vähennyspeli mukaan lukien, käyttäytyy kuin tietyn kokoinen Nim-kasa, ja näin useamman kasan versio ratkaistaan. Vähennyspelit ovat kombinatorisen peliteorian vakioesimerkki, esimerkiksi Elwyn Berlekampin, John Conwayn ja Richard Guyn teoksessa Winning Ways for your Mathematical Plays.