A card game that changes on the integers
- Kind
- Theorem, computer-assisted (exhaustive search)
- Status
- Computer-assisted; values computed exactly by three programs by separate agents, a fourth agreeing; unrefereed
- Prior work
- Not found in the searches logged; answers an expectation printed by Albert et al. (2009)
On this page
The statement
The game. Fix a deck of cards (numbers), a rising length and a falling length . Two players take turns writing an unused card of the deck at the right end of a row. The game ends as soon as the row holds a rising run of cards or a falling run of cards (the cards of a run need not sit next to each other). In normal play the player who completes the run wins; in misère play that player loses. The decks here are the fractions , the whole numbers and the integers .
Albert, Aldred, Atkinson, Handley, Holton, McCaughan and Sagan solved the game on the fractions for falling lengths up to 5, conjectured that the first player wins whenever , and wrote (2009, Section 6):
"We would be surprised (assuming the correctness of these conjectures) if similar results did not also hold for other infinite linear orders (not models of the theory of almost all finite partial orders) such as N or Z."
This is an expectation, not a posed problem, and it is conditional on their two conjectures.
Theorem. The second player wins these games, which the first player wins on the fractions:
| game | fractions (in print) | whole numbers | integers |
|---|---|---|---|
| misère | first player | second player | second player |
| normal | first player | second player | second player |
| normal | first player | first player | second player |
| misère | first player | first player | second player |
So the answer to the printed expectation is no, in both plays and on both decks. For misère , misère and normal , large finite decks also end up wins for the first player, so and differ from them too.
Check it yourself
- The game is short. By Erdős and Szekeres (1935), any row of different numbers holds a rising run of or a falling run of , so misère lasts at most 13 moves.
- The mechanism, by hand: misère on . The first player writes 0, the second player 1, the first player . Now every unused integer above 1 makes the rising run , and every unused integer below makes the falling run ; no integer lies between , 0 and 1. Every move loses. On the fractions, would complete nothing: a safe move.
- The second player's winning replies in misère on , after the opening card 0: the cards (figure 2). In misère they are the far cards, and beyond.
Worked examples
Why the integers differ. Between two fractions there are always unused cards; between two adjacent integers there are none, so a player can close an interval and take away every safe move inside it.
Status and who checked it
- Computer-assisted. Every value on and was found by exhaustive search. Three programs by three agents (the one that found it, a falsifier agent and a reviewer agent), with two different state representations, agree on every value each computed; a fourth program, written separately, agrees on every value it reached. A reviewer agent confirmed the result.
- What the searches rest on. A cap lemma (a gap of unused cards past a certain size behaves like any larger gap): Albert et al.'s Proposition 6, published for finite decks, extended to infinite ends by a falsifier agent and re-derived line by line by a reviewer agent.
- No hand proof of any second-player win on . No human referee has read any of it.
- Open: a pattern beside it, that misère on is a second-player win exactly when or . It fits the 8 exactly computed values to 11 and is not proved.
What is known, and not credited here. The game is Harary, Sagan and West's (1983). That normal and misère have the same winner on a deck with no least or greatest card is Albert et al.'s remark after their Proposition 7. The values on the fractions are theirs.
Prior work
Searches run. A falsifier agent and a reviewer agent each searched (arXiv, CORE, OEIS, OpenAlex and Semantic Scholar cited-by listings of Albert et al., zbMATH), read 9 and 10 candidates, and searched Zenodo, DataCite, HAL, OSF, GitHub, the web and problem lists by hand. Nowakowski's list of unsolved problems (2025) restates the two conjectures for finite decks and the fractions only; Pudwell (2026) solves misère play on the fractions only. A keyed CORE run on 2026-11-20 (6 requests, 5 records; 4 queries returned nothing) found no value on or . The result was not found in the searches logged; these searches were thin.
Still owed: Google Scholar (at its monthly cap until 2026-12-01); the full text of Harary, Sagan and West (1983); theses; books in print (Winning Ways, Siegel); the journal Integers.
Further reading
- Albert, Aldred, Atkinson, Handley, Holton, McCaughan and Sagan, "Monotonic sequence games", in Games of No Chance 3, MSRI Publications 56 (2009); arXiv:math/0602630.
- Harary, Sagan and West, "Computer-aided analysis of monotonic sequence games" (1983).
- Pudwell, "On an Erdős–Szekeres game", DMTCS 27:1 (2026), arXiv:2411.17875.