Παιχνίδι αφαίρεσης: τι είναι;
Το παιχνίδι αφαίρεσης είναι Νιμ με όριο σε κάθε κίνηση. Παίρνετε ακόμη αντικείμενα από έναν σωρό της επιλογής σας, αλλά τουλάχιστον ένα και το πολύ k, όπου το k είναι 2, 3, 4 ή 5 και επιλέγεται στη ρύθμιση του τραπεζιού (3 από προεπιλογή). Μπορείτε να πάρετε ολόκληρο σωρό μόνο όταν έχει k ή λιγότερα αντικείμενα.
Όλα τα άλλα είναι όπως στο τυπικό παιχνίδι: οι αρχικοί σωροί προέρχονται από την ίδια επιλογή (1, 3, 5 και 7 από προεπιλογή), και ο διακόπτης μιζέρ ορίζει αν η λήψη του τελευταίου αντικειμένου χάνει (η προεπιλογή εδώ) ή κερδίζει. Το όριο αλλάζει την αριθμητική του παιχνιδιού. Ένας μεγάλος σωρός δεν αδειάζει πια με μία κίνηση, οπότε δεν μπορεί να διορθώσει τη θέση με μια κίνηση, και αυτό που μετράει σε κάθε σωρό είναι το μέγεθός του διαιρεμένο με k + 1: το υπόλοιπο.
Αλλαγές κανόνων
| Κανόνας | Νιμ: τυπικοί κανόνες | Παιχνίδι αφαίρεσης |
|---|---|---|
| Κινήσεις | Νιμ: τυπικοί κανόνεςΠάρτε ένα ή περισσότερα αντικείμενα από έναν σωρό, όσα θέλετε, μέχρι ολόκληρο τον σωρό. | Παιχνίδι αφαίρεσηςΠάρτε τουλάχιστον 1 και το πολύ k αντικείμενα από έναν σωρό· το k είναι 2, 3, 4 ή 5, επιλογή στη ρύθμιση του τραπεζιού (3 από προεπιλογή). |
| Σωροί | Νιμ: τυπικοί κανόνεςΑρκετοί σωροί: 1, 3, 5 και 7 αντικείμενα από προεπιλογή, ή άλλο σύνολο από τη ρύθμιση του τραπεζιού. | Παιχνίδι αφαίρεσηςΟι ίδιοι σωροί, με την ίδια επιλογή. |
| Στόχος | Νιμ: τυπικοί κανόνεςΜιζέρ από προεπιλογή: όποιος πάρει το τελευταίο αντικείμενο χάνει. Η ρύθμιση μπορεί να αλλάξει σε κανονικό παιχνίδι, όπου η λήψη του τελευταίου αντικειμένου κερδίζει. | Παιχνίδι αφαίρεσηςΤο ίδιο, με τον ίδιο διακόπτη μιζέρ. |
| Νικηφόρο παιχνίδι | Νιμ: τυπικοί κανόνεςΚανονικό παιχνίδι: αφήστε τους σωρούς με νιμ-άθροισμα (το bitwise XOR των μεγεθών τους) μηδέν. Μιζέρ: το ίδιο, μέχρι να έμεναν μόνο σωροί του ενός αντικειμένου· τότε αφήστε περιττό πλήθος από αυτούς. | Παιχνίδι αφαίρεσηςΚανονικό παιχνίδι: κάθε σωρός μετράει ως το υπόλοιπο του μεγέθους του διά k + 1, και αφήνετε αυτά τα υπόλοιπα με νιμ-άθροισμα μηδέν· ένας μόνος σωρός είναι χαμένος για τον παίκτη που παίζει ακριβώς όταν το μέγεθός του είναι πολλαπλάσιο του k + 1. Μιζέρ: ένας μόνος σωρός είναι χαμένος για τον παίκτη που παίζει ακριβώς όταν το μέγεθός του είναι κατά ένα μεγαλύτερο από πολλαπλάσιο του k + 1. |
Ιστορία
Τα παιχνίδια μέτρησης με όριο σε κάθε κίνηση είναι παλιά. Το Problèmes plaisants et délectables του Claude-Gaspard Bachet de Méziriac, μια συλλογή μαθηματικών ψυχαγωγιών που πρωτοεκδόθηκε στο Παρίσι το 1612, περιγράφει ένα παιχνίδι στο οποίο δύο παίκτες προσθέτουν εναλλάξ έναν αριθμό από 1 έως 10 σε ένα τρέχον άθροισμα, και κερδίζει όποιος φτάσει πρώτος στο 100. Το νικηφόρο σχέδιο είναι να φτάσετε στα αθροίσματα 12, 23, 34 και ούτω καθεξής μέχρι το 89, με βήματα του 11: η ίδια αριθμητική με έναν μόνο σωρό 100 από τον οποίο κάθε κίνηση παίρνει 1 έως 10.
Το ίδιο το Νιμ πήρε το όνομα και την πλήρη θεωρία του από τον Charles L. Bouton το 1901. Οι εργασίες των Roland Sprague (1935) και Patrick Grundy (1939) έδειξαν ότι κάθε παιχνίδι αυτού του είδους, και το παιχνίδι αφαίρεσης, συμπεριφέρεται σαν σωρός Νιμ ορισμένου μεγέθους, και έτσι λύνεται η εκδοχή με πολλούς σωρούς. Τα παιχνίδια αφαίρεσης είναι κλασικό παράδειγμα στη θεωρία συνδυαστικών παιγνίων, για παράδειγμα στο Winning Ways for your Mathematical Plays των Elwyn Berlekamp, John Conway και Richard Guy.