Mis\`ere Greedy Nim and Mis\`ere Bounded Greedy Nim

Ayumi Shinohara; Nanako Omiya; Ryo Yoshinaka

Mis\`ere Greedy Nim and Mis\`ere Bounded Greedy Nim

T0 review · 0 major / 6 minor · reviewed 2026-08-07 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read This paper proves exactly which positions are losing in misère k-Bounded Greedy Nim and in misère Greedy Nim.

desk verdict Solid misère classification for two Nim variants; the induction checks out on inspection, with only minor presentation defects. read the letter →

arxiv 2506.04657 v1 pith:N3QDPJR4 submitted 2025-06-05 cs.GT cs.DM

Nanako Omiya , Ryo Yoshinaka , Ayumi Shinohara This is my paper

classification cs.GTcs.DM MSC 91A46

keywords misèreplayGreedyNimk-BoundedP-positionsimpartialcombinatorialgamessingularpositionsk-nicepairsstablemoves

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper analyzes two misère-play variants of Greedy Nim, where players must remove stones from the largest heap and the player who cannot move wins. It establishes a full characterization of P-positions—the positions from which the previous player can force a win—for both k-Bounded Greedy Nim and ordinary Greedy Nim. The conditions are simple remainder checks modulo k+1, so they classify any position in linear time and indicate a winning move from every N-position. This matters because misère rules are generally harder than normal play, and greedy restrictions block the usual misère-quotient decomposition.

What carries the argument

The argument runs on three named objects. R(a) is the remainder of a modulo k+1. A pair (x1,x2) is k-nice if it satisfies one of three remainder conditions, and a triple (x1,x2,x3) is k-good if it satisfies one of three analogous conditions; these residues are exactly what make a move land on a P-position or avoid doing so. β(S) counts how many heaps equal the third heap, which controls whether the normal-play criterion still applies. A stable move removes t stones without dropping the first heap below the second, so it preserves β and the lower heaps; Lemma 1 then guarantees no stable move from a claimed P-position lands on another claimed P-position, and the two state-transition diagrams enumerate the remaining unstable moves.

What would settle it

Brute-force the games for small k and small total stones: enumerate all reachable positions by retrograde analysis and compare the computed P-positions with the four conditions of Theorem 3 and the two conditions of Theorem 5. The first mismatch—a position satisfying the stated conditions with a move to another such position, or a position failing the conditions with no move to one—would refute the characterization.

Watch

Extended reading notes

Core claim

On the paper's own terms, the contribution is Theorem 3 and Theorem 5. For misère k-Bounded Greedy Nim, a position S=(x1,...,xn) is a P-position exactly when its third-heap size and the parity of β(S), the repeat count of x3, select one of four cases: with x3≤1 and β even the pair (x1,x2) must be k-nice; with x3≤1 and β odd the remainder R(x1−x2) must be 0; with x3≥2 and β even R(x1−x2)=0; and with x3≥2 and β odd the triple (x1,x2,x3) must be k-good. For misère Greedy Nim, S is a P-position exactly when x1≤1 and the multiplicity α(S) of the largest heap is odd, or x1≥2 and α(S) is even. The proof is inductive and proceeds through state-transition diagrams, treating moves that keep the first heap above the second as stable and handling all other moves case by case.

Load-bearing premise

The proof's induction assumes the state-transition diagrams and the numbered case analyses cover every legal move from every position; if some transition is omitted or mislabeled, the induction step would not establish all P-positions.

Editorial extensions

If this is right

Every position in either game can be classified as N or P by reading a few heap sizes and counting repeats, so no recursive search is needed.
The constructive necessity proofs give an explicit winning move from every N-position: remove r1, r1+1, or R(r1−1) stones according to which k-nice or k-good condition fails.
For misère Greedy Nim, positions with largest heap at least 2 are standard, meaning their outcome agrees with normal play, while positions with largest heap 0 or 1 are singular, meaning it disagrees.
Because Greedy Nim coincides with k-Bounded Greedy Nim when k is at least the largest heap, Theorem 3 yields an alternative derivation of Theorem 5, as the paper notes.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

Extension: the same remainder grammar may extend to allied greedy rules, since the proof isolates the role of the second- and third-largest heaps and the parity of equal heaps.
Extension: the linear-time classification could serve as a stepping stone toward fast Grundy-value computation for Greedy Nim, which the paper leaves open.
Extension: the sharp behavior change at x3≤1 versus x3≥2 suggests a general pattern for misère versions of solved normal-play games: the misère rule only bites when few large heaps remain.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

Good to know about this paper: it closes two open misère classification problems cleanly, and the math holds up under inspection. The main result, Theorem 3, gives a four-case P-position characterization for misère k-Bounded Greedy Nim; Theorem 5 does the same for misère Greedy Nim. The proofs are a long induction with heavy residue arithmetic, but the case splits are exhaustive and internally consistent. I independently checked a few k=2 positions by hand and they match the theorem.

What's genuinely new: the k-nice predicate and the stable-move lemma. The stable-move device lets the authors dispatch a large fraction of the induction uniformly, and the misère conditions differ nontrivially from the normal-play conditions of Xu and Zhu. Theorem 5 is a nice direct argument using singular/standard positions, and it also shows the Greedy Nim result follows as a consequence of the k-bounded one. The literature is cited appropriately; the reliance on established normal-play results is legitimate.

The soft spots are minor. Definition 4 says x1 and x2 are positive, but the proof later uses x2=0 for single-heap positions; that should be non-negative. Theorem 5's induction doesn't explicitly state the x1=0 base case, though it's trivial and the induction handles it. The proof of Theorem 3 is organized around the numbered arrows in Figures 1 and 2. The text does enumerate the cases in the prose, but a reader has to work to verify that every legal move falls into one of the arrows. It would help to add an explicit sentence (or a short paragraph) claiming exhaustiveness of the diagram. I don't think this is a real gap; I couldn't find a missing transition.

Who will get value: anyone working on impartial games, especially Nim variants and misère play. The paper is a solid reference for these two games and introduces proof techniques that could transfer to other greedy removal games. It deserves a serious referee. The revisions needed are all local: fix the positive/non-negative slip, state the zero-heap base cases explicitly, and add the exhaustiveness remark. I'd send it to referee without desk rejection, and expect it to be accepted after minor revisions.

Referee Report

0 major / 6 minor

Summary. This paper solves the misère play counterparts of two impartial stone-removal games. For misère k-Bounded Greedy Nim, Theorem 3 gives a complete four-case characterization of P-positions in terms of x3, β(S), R(x1-x2), and the k-nice/k-good conditions, proved by induction on the total number of stones with an extensive residue-class case analysis. For misère Greedy Nim, Theorem 5 characterizes P-positions by the largest heap value x1 and the multiplicity α(S), with a direct induction proof and a remark that the result also follows from Theorem 3 by taking k at least x1. The paper also explains why the misère quotient framework is not directly applicable to these games.

Significance. If correct, the paper provides the first complete misère outcome classification for both games, extending the normal-play theorems of Xu and Zhu and of Albert and Nowakowski. The proofs are self-contained, the characterizations are linear-time checkable, and the Greedy Nim result gives a clean singular/standard position dichotomy. The k-Bounded result is the main technical contribution; Greedy Nim is a comparatively short corollary. The manuscript does not rely on numerical fitting or computation, and the case analysis is internally consistent on the portions I checked.

minor comments (6)

[Definition 4 and Section 3.2.1] Definition 4 says x1 and x2 are positive integers, but the base cases evaluate k-nice at (0,0) for the empty position and at (1,0) for a one-stone position. The definition should allow non-negative integers, or the base cases should be handled without invoking k-nice for x2=0.
[Section 3.2.1] For the one-stone position, the text states 'since R(x1)=0 and R(x2)=1, (x1,x2) satisfies (3) of the definition of k-nice'; this is backwards. For S=(1,0,...,0), the relevant values are R(x1)=1 and R(x2)=0, which is condition (3). The current sentence describes condition (1).
[Theorem 5 proof] The induction in the proof of Theorem 5 does not explicitly state the base case for the empty position and compresses the parity argument for positions with x1=1. Please state the base cases and explicitly justify that for α(S)>1 odd the unique move reaches a position with α even, which is not a P-position under the stated condition.
[Sections 3.2.3 and 3.2.4] The proof organization relies on the state-transition diagrams in Figures 1 and 2, but the diagrams are not visible in the manuscript text as supplied. A sentence describing the partition of legal moves into the enumerated arrow cases, independent of the figures, would make the exhaustiveness of the induction self-contained.
[Section 3.2.4, Sufficiency, Case 2] In the sentence 'We will show that S' is not in P if (x1,x2) satisfies (1), (2) or (3) of the definition of k-good', the pair should be the triple (x1,x2,x3), consistent with the rest of the paragraph.
[Section 4.2] The remark that Theorem 5 can be derived from Theorem 3 by assuming k is at least x1 would benefit from an explicit note that positions of Greedy Nim are padded with zero heaps to satisfy the n≥4 convention used in Theorem 3.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: the misère classifications are derived by induction from move rules and use external normal-play theorems only as benchmarks.

full rationale

The paper's derivation chain is self-contained and non-circular. Theorem 3 is proved by induction on the total number of stones, with explicit case splits for x3 ≤ 1 and x3 ≥ 2. Each necessity direction constructs a legal move (t = r1, r1 + 1, or R(r1 − 1)) and verifies, by the induction hypothesis, that the follower satisfies the stated P-position conditions; each sufficiency direction shows that every follower fails those conditions, using stable-move Lemma 1 and the relevant residue definitions. The definitions of k-nice and k-good are independent of the misère P-position set, and the normal-play classification of Xu and Zhu [14] is used only as an external result, not as the misère conclusion. Theorem 5 has an independent direct induction proof in Section 4.2, explicitly proving that positions with x1 ≤ 1 are singular and positions with x1 ≥ 2 are standard, with a separate argument for x2 ≥ 2; the note that Theorem 5 can also be derived from Theorem 3 is a consistency observation, not a load-bearing citation. No fitted parameters are renamed as predictions, and the cited external theorems (Xu–Zhu, Albert–Nowakowski) are not authored by the present paper's authors, so no self-citation chain is load-bearing. Minor presentational issues, such as Definition 4 saying positive integers while the base case uses x2 = 0, do not affect the logical dependency structure.

Assumptions & free parameters 0 free parameters · 4 assumptions · 0 invented entities

No free parameters are fitted: k is a game parameter and the modulus k+1 is forced by the move cap. No invented entities are introduced; k-nice, α, β, and stable moves are definitions used in the proof, not postulates. The only external assumptions are the cited normal-play theorems and the standard induction framework.

assumptions (4)

domain assumption Normal-play Greedy Nim outcome is determined by the parity of α(S), as stated in Theorem 4 of Albert and Nowakowski.
Used in the proof of Theorem 5 to identify standard positions and to conclude that positions with x1≥2 and x2≤1 are normal-play N-positions.
domain assumption Positions may be padded with zero heaps to assume n≥4 without changing game outcomes.
Section 2.1 states this without proof. Zero heaps are never chosen except when all heaps are zero, so the move set is unchanged.
standard math The misère terminal position with no stones is an N-position, and induction on total stones is well-founded from totals 0 and 1.
Used throughout Sections 3.2 and 4.2. It follows directly from the misère rule that the player who cannot move wins.
domain assumption The k-good condition is imported from Xu and Zhu's normal-play solution of k-Bounded Greedy Nim.
Theorem 3 uses the same k-good definition as Theorem 2 from Xu and Zhu. Although the proof of Theorem 3 is largely self-contained, the definition is external.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Mis\`ere Greedy Nim and Mis\`ere Bounded Greedy Nim." pith.science (2026). https://pith.science/paper/N3QDPJR4

@misc{pith2026250604657,
  author       = {Pith},
  title        = {Pith review of: Mis\`ere Greedy Nim and Mis\`ere Bounded Greedy Nim},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/N3QDPJR4}},
  note         = {Machine review of arXiv:2506.04657}
}

read the original abstract

In this paper, we analyze the mis\`ere versions of two impartial combinatorial games: k-Bounded Greedy Nim and Greedy Nim. We present a complete solution to both games by showing necessary and sufficient conditions for a position to be P-positions.

Figures

Figures reproduced from arXiv: 2506.04657 by the authors.

**Figure 1.** The state transition diagram when x3 ≤ 1 Necessity. (The position S is a P-position =⇒ The position S satisfies one of the conditions of Theorem 3) Case 1: β(S) is even. We first consider the case where β(S) is even. We will prove that (x1, x2) is k-nice if the position S is a P-position, using contraposition. We will show that removing t stones from a position S that is not k-nice is a winning strategy where t is d… view at source ↗

**Figure 2.** The state transition diagram when x3 ≥ 2 Necessity. (The position S is a P-position =⇒ The position S satisfies one 9 [PITH_FULL_IMAGE:figures/full_fig_p009_2.png] view at source ↗

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

15 extracted references · 14 canonical work pages

[1]

Albert and Richard J

Michael H. Albert and Richard J. Nowakowski. Nim restrictions. Integers: Electronic Journal of Combinatorial Number Theory , 4(G01):G01, 2004

work page 2004
[2]

Berlekamp, John H

Elwyn R. Berlekamp, John H. Conway, and Richard K. Guy. Winning ways for your mathematical plays, volume 4 . AK Peters/CRC Press, 2004

work page 2004
[3]

Charles L. Bouton. Nim, a game with a complete mathematical theory. Annals of mathematics , 3(1/4):35–39, 1901

work page 1901
[4]

Caissa’s Wild Roses

Thomas Rayner Dawson. Caissa’s Wild Roses . Number 1. TR Dawson, 1935

work page 1935
[5]

The Canterbury Puzzles

Henry Ernest Dudeney. The Canterbury Puzzles . Courier Corporation, 2002

2002
[6]

P. M. Grundy. Mathematics and games. Eureka, 2:6–8, 1939

work page 1939
[7]

P. M. Grundy and C. A. B. Smith. Disjunctive games with the last player losing. Mathematical Proceedings of the Cambridge Philosophical Society , 52(3):527–533, 1956

work page 1956
[8]

S. C. Locke and B. Handley. Amalgamation Nim. Integers: Electronic Journal of Combinatorial Number Theory , 21, 2021

work page 2021

Show all 15 references

[9]

Plambeck and Aaron N

Thane E. Plambeck and Aaron N. Siegel. Mis` ere quotients for impartial games. Journal of Combinatorial Theory, Series A , 115(4):593–622, 2008

2008
[10]

Schwartz

Benjamin L. Schwartz. Some extensions of Nim. Mathematics Magazine , 44(5):252–257, 1971

1971
[11]

R. Sprague. ¨Uber mathematische kampfspiele. Tohoku Mathematical Jour- nal, First Series , 41:438–444, 1935

1935
[12]

C. P. Welter. The advancing operation in a special abelian group. In Inda- gationes Mathematicae (Proceedings), volume 55, pages 304–314. Elsevier, 1952

1952
[13]

W. A. Wythoff. A modification of the game of Nim. Nieuw Archief voor Wiskunde, 7(2):199–202, 1907

1907
[14]

Bounded greedy Nim

Rongxing Xu and Xuding Zhu. Bounded greedy Nim. Theoretical Computer Science, 746:1–5, 2018

2018
[15]

On misere Nim-type games

Yohei Yamasaki. On misere Nim-type games. Journal of the Mathematical Society of Japan , 32(3):461–475, 1980. 15

1980

Pith tools

Reviewed August 7, 2026 · model on record in the stance chip above.

[1] [1]

Albert and Richard J

Michael H. Albert and Richard J. Nowakowski. Nim restrictions. Integers: Electronic Journal of Combinatorial Number Theory , 4(G01):G01, 2004

work page 2004

[2] [2]

Berlekamp, John H

Elwyn R. Berlekamp, John H. Conway, and Richard K. Guy. Winning ways for your mathematical plays, volume 4 . AK Peters/CRC Press, 2004

work page 2004

[3] [3]

Charles L. Bouton. Nim, a game with a complete mathematical theory. Annals of mathematics , 3(1/4):35–39, 1901

work page 1901

[4] [4]

Caissa’s Wild Roses

Thomas Rayner Dawson. Caissa’s Wild Roses . Number 1. TR Dawson, 1935

work page 1935

[5] [5]

The Canterbury Puzzles

Henry Ernest Dudeney. The Canterbury Puzzles . Courier Corporation, 2002

2002

[6] [6]

P. M. Grundy. Mathematics and games. Eureka, 2:6–8, 1939

work page 1939

[7] [7]

P. M. Grundy and C. A. B. Smith. Disjunctive games with the last player losing. Mathematical Proceedings of the Cambridge Philosophical Society , 52(3):527–533, 1956

work page 1956

[8] [8]

S. C. Locke and B. Handley. Amalgamation Nim. Integers: Electronic Journal of Combinatorial Number Theory , 21, 2021

work page 2021