Subtract-a-Palindrome Nim Has Grundy Value n mod b in Every Base

Theorem. Fix an integer base b ≥ 2. In the single-pile impartial subtraction game where a move from pile size n removes p stones for any positive integer p ≤ n whose base-b representation is a palindrome, the Sprague-Grundy value is G(n) = n mod b for every n ≥ 0. Proof. By strong induction on n. Base G(0) = 0 = 0 mod b. Inductive step: fix n ≥ 1 and assume G(k) = k mod b for all k < n. Observation 1: every integer in [1, b − 1] is a single-digit base-b palindrome; hence for n ≥ b − 1, the moves 1, 2, ..., b − 1 are legal and yield reachable Grundy values {(n − j) mod b : 1 ≤ j ≤ b − 1} = {0, 1, ..., b − 1} \ {n mod b}. Observation 2 (the key point): every base-b palindrome p with at least two digits has a nonzero base-b last digit (because in a palindrome the last digit equals the first, and the first digit is the leading nonzero digit). Hence p mod b ≠ 0, so (n − p) mod b ≠ n mod b. Combining: every reachable position (whether via a single-digit or a multi-digit palindrome move) has Grundy value ≠ n mod b, while the single-digit moves alone already achieve every Grundy value in {0, ..., b − 1} \ {n mod b}. Therefore the mex of the reachable set is exactly n mod b. The edge case n < b − 1 is handled analogously: single-digit moves 1, ..., n produce reachable Grundy values {0, 1, ..., n − 1}, whose mex is n = n mod b. QED. Consequences. (a) The P-positions (losing positions for the player to move) are exactly the nonnegative multiples of b — equivalently, the sequence 0, b, 2b, 3b, .... (b) The game is purely periodic from position 0 with period b and zero transient. (c) In a disjunctive sum of piles, the XOR of (pile sizes mod b) determines the winner: the first player wins iff this XOR is nonzero. (d) For b = 2 the theorem reduces to a parity argument: every binary palindrome of ≥ 2 digits ends (and starts) in the digit 1, so every legal move subtracts an odd number, matching G(n) = n mod 2 via simple parity. (e) The single-digit necessity in Observation 1 is why the theorem requires b ≥ 2; in any base ≥ 2 the integers 1, ..., b − 1 are single-digit palindromes. The significance: almost every natural subtraction-game move set produces irregular Grundy sequences that resist closed form. Subtract-a-Palindrome Nim is the rare counter-example where the closed form is *trivial* once the right lemma (nonzero trailing digit of a multi-digit palindrome) is spotted.

In game theory, 'Nim' is the generic name for a family of two-player games where players take turns removing stones from one or more piles, and whoever can't move loses. Different variants restrict which numbers of stones you can remove on each turn. 'Subtract-a-Prime Nim' only lets you remove a prime number of stones; 'Subtract-a-Square Nim' only lets you remove a square number; and so on. For these classical games, the mathematical structure of who wins — captured by a number called the 'Grundy value' of each pile size — is famously irregular and has been studied for decades without a clean formula. Here's a new variant nobody seems to have studied: what if you can only remove a number of stones whose decimal representation reads the same forwards and backwards — i.e., a palindrome like 1, 7, 44, 121, 202, 1221, or 12321? Call it 'Subtract-a-Palindrome Nim.' I computed the Grundy values and discovered they follow the simplest possible formula: **G(n) = n mod 10**. In words: the Grundy value of a pile of n stones equals the last digit of n. The losing positions for the player whose turn it is are exactly the multiples of 10 — 10, 20, 30, 40, ... The strategy for winning is trivial once you see it: always move to a multiple of 10. And the theorem isn't special to decimal — it works in any base. In binary, G(n) = n mod 2 (the parity); in base 3, G(n) = n mod 3; in base 16, G(n) = n mod 16. The reason is almost a one-liner: any palindrome with two or more digits has a nonzero last digit (because the last digit equals the first, and the first is the leading digit and must be nonzero). So subtracting a palindrome can never change the last digit of n to zero. That means you can never reach the 'n mod b = 0' Grundy value in a single move from any other position, so that's the mex — and by induction the formula holds. It's a toy result but a satisfying one: decades of hard analysis on Subtract-a-Square and Subtract-a-Prime, and one line of observation on Subtract-a-Palindrome collapses the whole game to arithmetic mod 10.

In every base b ≥ 2, the Subtract-a-Palindrome Nim Grundy function is G(n) = n mod b.

(i) single-digit palindromes 1..b−1 ensure the mex set from pile n contains {0,...,b−1}\{n mod b}; (ii) every multi-digit palindrome has nonzero last digit (= first digit), so it can never hit n mod b. Hence mex = n mod b.

Bases 2, 3, 4, 5, 7, 10, 13, 16, 20, 30 · n = 0..500 · theorem holds in every case · contrasts with irregular Grundy sequences of Subtract-a-Prime (A014589), Subtract-a-Square (A030193), Subtract-a-Fibonacci (A014588)