Che cos'è Gioco di sottrazione?
Il gioco di sottrazione è il Nim con un limite a ogni mossa. Prendi ancora oggetti da un mucchio a tua scelta, ma almeno uno e al massimo k, dove k è 2, 3, 4 o 5, scelto nelle impostazioni del tavolo (3 di default). Puoi prendere un intero mucchio solo quando contiene k oggetti o meno.
Tutto il resto è come nel gioco standard: i mucchi iniziali vengono dalla stessa opzione (1, 3, 5 e 7 di default), e l'opzione misère decide se prendere l'ultimo oggetto fa perdere (il default qui) o vincere. Il tetto cambia l'aritmetica del gioco. Un mucchio grande non si può più svuotare in una mossa, quindi non serve a sistemare la posizione in un colpo solo, e ciò che conta di ogni mucchio è la sua dimensione divisa per k + 1: il resto.
Regole che cambiano
| Regola | Nim standard | Gioco di sottrazione |
|---|---|---|
| Mosse | Nim standardPrendi uno o più oggetti da un mucchio, quanti vuoi, fino all'intero mucchio. | Gioco di sottrazionePrendi almeno 1 e al massimo k oggetti da un mucchio; k è 2, 3, 4 o 5, scelto nelle impostazioni del tavolo (3 di default). |
| Mucchi | Nim standardDiversi mucchi: 1, 3, 5 e 7 oggetti di default, o un altro insieme scelto nelle impostazioni del tavolo. | Gioco di sottrazioneGli stessi mucchi, scelti con la stessa opzione. |
| Obiettivo | Nim standardDi default si gioca misère: chi prende l'ultimo oggetto perde. Le impostazioni possono passare al gioco normale, in cui prendere l'ultimo oggetto fa vincere. | Gioco di sottrazioneLo stesso, con la stessa opzione misère. |
| Strategia vincente | Nim standardGioco normale: lascia i mucchi con somma nim (lo XOR bit a bit delle loro dimensioni) pari a zero. Misère: lo stesso, finché resterebbero solo mucchi da un oggetto; allora lasciane un numero dispari. | Gioco di sottrazioneGioco normale: ogni mucchio conta come il resto della sua dimensione divisa per k + 1, e lasci quei resti con somma nim pari a zero; un mucchio singolo è perso per chi deve muovere esattamente quando la sua dimensione è un multiplo di k + 1. Misère: un mucchio singolo è perso per chi deve muovere esattamente quando la sua dimensione è un multiplo di k + 1 più uno. |
Storia
I giochi di conteggio con un tetto a ogni mossa sono antichi. Problèmes plaisants et délectables di Claude-Gaspard Bachet de Méziriac, una raccolta di ricreazioni matematiche pubblicata per la prima volta a Parigi nel 1612, descrive un gioco in cui due giocatori a turno aggiungono un numero da 1 a 10 a un totale progressivo, e vince il primo che arriva a 100. Il piano vincente è raggiungere i totali 12, 23, 34 e così via fino a 89, a passi di 11: la stessa aritmetica di un unico mucchio di 100 da cui ogni mossa prende da 1 a 10.
Il Nim stesso ricevette il nome e la teoria completa da Charles L. Bouton nel 1901. I lavori di Roland Sprague (1935) e Patrick Grundy (1939) mostrarono che ogni gioco di questo tipo, gioco di sottrazione compreso, si comporta come un mucchio del Nim di una certa dimensione, ed è così che si risolve la versione con più mucchi. I giochi di sottrazione sono un esempio classico della teoria dei giochi combinatori, per esempio in Winning Ways for your Mathematical Plays di Elwyn Berlekamp, John Conway e Richard Guy.