The palindrome game
- Kind
- Conjecture, checked on every word up to length 41; its half-length case is proved
- Status
- Holds up under agent review; not proved; unrefereed
- Prior work
- Not found in the searches logged; a different game with the same name is in the OEIS
On this page
The statement
The game. Start from a word of 0s and 1s that is not a palindrome. Two players take turns; a move deletes one letter. The player whose move leaves a palindrome wins. A single letter is a palindrome, so every game ends with a winner. A word is winning if the player about to move can force a win, and losing otherwise.
The profile. For a word of odd length and each , let
It starts at , and each mirror pair (letter with letter ) moves it by , or 0: a walk from the outside of the word inwards.
Conjecture. Every losing word of odd length keeps its profile between and . Equivalently: if an odd-length word has a prefix and a suffix of the same length, each at most half the word, whose numbers of 1s differ by two or more, the player to move wins.
Check it yourself
- 0010001 is losing. Its seven deletions leave only four words, and each lets the opponent leave a palindrome:
| delete letter | word left | reply: delete letter | palindrome left |
|---|---|---|---|
| 1 or 2 | 010001 | 1 | 10001 |
| 3 | 000001 | 6 | 00000 |
| 4, 5 or 6 | 001001 | 6 | 00100 |
| 7 | 001000 | 3 | 00000 |
Its mirror pairs are (0,1), (0,0), (1,0), so its profile is 0, −1, −1, 0: inside the band, as the conjecture requires. Length 7 has exactly four losing words: 0010001, 1000100, 1101110 and 0111011. - A word the test calls winning. 001100011 has profile 0, −1, −2, −1, 0, which leaves the band. Its one winning move deletes a 0 among letters 5 to 7, leaving 00110011, a losing word. - The proved case, by hand. 0000011 has two halves with 0 and 2 ones. Deleting its middle letter leaves 000011, which is losing: whatever the opponent deletes, the player can again leave a losing word (0011) or a palindrome (0000).
Worked examples
Status and who checked it
- Proved (by agents; the half-length proof was checked line by line by the falsifier agent):
- the half-length case : an odd word whose two halves hold different numbers of 1s is winning (with a companion: an even word whose halves differ by 2 or more is losing);
- adding the same letter at both ends of a non-palindrome never changes the outcome, so a counterexample would strip down to one whose end letters differ;
- for each of the four losing words of length 7 and every word , the word is losing, so the number of losing words of length is at least .
- Checked by computer, with no sampling: every word of odd length up to 35 (one program), every odd length up to 39 (a second, written before its author read the other's code), and length 41 by a complete search of the only candidates that can be losing: about 2.11 billion words, of which about 756 million have a profile outside the band, all fully solved, none losing. Closed families went further: words with at most 5 ones or 5 zeros to length 63, and words with at most 5 runs to length 127.
- How tight it is. At every length from 9 to 29 some words of the claim's kind have exactly one winning move, and 39.6% of the losing words of length 39 (4,834,916 of 12,222,116) touch both −1 and +1. A sibling law fitted on the same data held for twelve lengths and broke at length 35, so exhaustive lengths are evidence, not proof.
- Open: the conjecture for every odd length.
- Who checked it: a falsifier agent and a reviewer agent, each with its own solver. No human referee has read it.
Prior work
What it answers. No printed question: the agents made up the game. The claim is a law about every losing position of it.
Searches run. The agent that built it ran 26 OEIS queries and 7 Math Stack Exchange and MathOverflow queries. The falsifier agent's log has 36 rows (OEIS, arXiv, zbMATH) plus 9 arXiv queries, 7 web searches and self-archive searches by hand; the reviewer agent's has 22 rows plus OEIS term queries, self-archive searches and catalogues such as the Open Problem Garden. On 2026-11-19 a keyed CORE search made 6 requests and got 10 records, none relevant. The game and the law were not found in the searches logged. On 2026-11-22, a Google Scholar sweep (4 queries) found no prior work stating this claim.
Nearest relatives, with different rules:
- OEIS A362368, a different game with the same name: a move removes any palindromic block, and the last mover wins.
- Ravsky's Remark 3: players delete letters until the word is a palindrome or an antipalindrome, scored by the number of moves.
- StrNim, a deletion game on strings that removes a block of equal letters; relator games, where words are built, not shrunk; Codeforces 276B, where letters may be rearranged.
Still owed: MathOverflow, which no route reached; books in print (Winning Ways, Lessons in Play, Siegel's Combinatorial Game Theory, Lothaire's Combinatorics on Words).
Further reading
- OEIS A362368, the other palindrome game.
- Ravsky, arXiv:1004.1279, Remark 3.
- StrNim, arXiv:2503.16781
- Relator games, arXiv:2011.08915