Pith. sign in

REVIEW 3 major objections 4 minor 25 references

Nim on Integer Partitions and Hyperrectangles

T0 review · 3 major / 4 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 The paper proves exact Sprague–Grundy formulas for two Nim variants on partitions and hyperrectangles, and it characterizes all positions of value one in the partition game.

desk verdict Nice new games and solid rectangle/hyperrectangle formulas, but the proof of Theorem 2 has a real gap that needs fixing before I'd trust the paper. read the letter →

arxiv 2506.04991 v1 pith:5AQ7PZAW submitted 2025-06-05 math.CO

Eric Gottlieb , Matjaž Krnc , Peter Muršič This is my paper
classification math.CO MSC 91A4605A17
keywords impartialcombinatorialgameSprague–GrundyvalueintegerpartitionYoungdiagramhyperrectangleNimmisèreplayConway–Gurvich–Hoclassification
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

This paper introduces two impartial games: PNim, where a position is a Young diagram of an integer partition and a move deletes rows or columns (merging what remains), and RNim, where a move shortens one side of a hyperrectangle. The main result is a complete formula for RNim: a single box $\langle k_1,\ldots,k_d\rangle$ has Sprague–Grundy value $((k_1-1)\oplus\cdots\oplus(k_d-1))+1$, so any disjunctive sum of boxes is solved by XORing these values. For rectangular Young diagrams $Jc^rK$ in PNim the same shifted-XOR formula holds, and the paper proves a tight upper bound $\lambda_1+r-1$ on the value of any partition. It also characterizes the partitions of value one: exactly $J1K$ and the partitions lying between $Jr,r,r-1,\ldots,2K$ and $Jr^rK$ in Young's lattice for some $r\ge 2$. These formulas and the placement of the games in the Conway–Gurvich–Ho hierarchy make optimal normal and misère play computable.

What carries the argument

The argument runs through the mex recursion for Sprague–Grundy values, where mex is the least nonnegative integer not appearing among the values of reachable positions. The key identity is Lemma 5, $k+\operatorname{mex}(S)=\operatorname{mex}(\{0,\ldots,k-1\}\cup\{s+k:s\in S\})$, which lets a shift by $1$ commute with taking the mex of reachable values. Applied to rectangles, whose moves are indexed by reducing one side, this produces $((r-1)\oplus(c-1))+1$; Corollary 11 generalizes the same shifted-XOR mex identity to any number of dimensions and yields Theorem 3. For the value-one characterization, the load-bearing object is the family $S=\{J1K\}\cup\bigcup_{r\ge2}\{\lambda: Jr,r,r-1,\ldots,2K\le\lambda\le Jr^rK\}$; the proof uses the rank of a partition, the difference between its largest part and its number of parts, to show that no member of $S$ can move to another member. For heavy rectangles, Lucas's theorem on binomial coefficients modulo a prime decides when the upper bound is attained.

What would settle it

Run an exhaustive recursive computation of $G_R$ on the box $\langle 2,3,4\rangle$: the formula predicts the value $1$, so any other value would refute Theorem 3. For Theorem 2, enumerate all partitions up to $n=26$, the range of the paper's appendix, by recursion and check whether any partition outside the stated intervals has value $1$, or any partition inside the intervals has a value different from $1$.

Watch

Extended reading notes

Core claim

The central claim, stated as Theorem 3, is that RNim has a closed form: for positive side lengths $k_1,\ldots,k_d$, $G_R(\langle k_1,\ldots,k_d\rangle)=((k_1-1)\oplus\cdots\oplus(k_d-1))+1$. Theorem 1 gives the same formula for a rectangular partition $Jc^rK$ in PNim, namely $G_P(Jc^rK)=((r-1)\oplus(c-1))+1$. For general partitions, Proposition 1 bounds $G_P(\lambda)$ by $\lambda_1+r-1$, and Theorem 2 says the value is exactly $1$ precisely for $J1K$ and for the partitions in the Young-lattice interval $Jr,r,r-1,\ldots,2K\le\lambda\le Jr^rK$ with $r\ge2$. The paper also shows that $1$-PNim and $1$-RNim are pet and returnable but not forced, that PNim and RNim are miserable and returnable but not pet, and that these classifications make misère play follow from normal-play values through the tame-game theorem.

Load-bearing premise

Theorem 2 rests on an unstated induction: the proof shows that every partition outside the candidate family can move into it and no member can move to another member, but it does not spell out the induction on partition size that would make those two facts force the Sprague–Grundy value to be exactly 1 for members and different from 1 for all other partitions.

Editorial extensions

If this is right

  • Every position of RNim, including sums of boxes of different dimensions, has a Sprague–Grundy value computed by XORing one expression per box, so optimal moves can be read off directly from the side lengths.
  • Rectangular PNim is completely solved: the value of $Jc^rK$ is $((r-1)\oplus(c-1))+1$, and the rectangle is heavy exactly when $\binom{c+r-2}{r-1}$ is odd.
  • The value-$1$ partitions of Theorem 2 are exactly the losing positions of misère $1$-PNim, and the proof of the theorem supplies a concrete move into that set from every winning position.
  • Because PNim and RNim are pet and returnable, and their sum games are miserable and returnable, the tame-game theorem gives misère Grundy values of sums from the normal-play formulas.
  • Resolving PNim under normal play is equivalent to resolving it under misère play, so the same formulas govern both conventions.

Reading between the lines

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

  • The shifted-XOR formula for RNim is likely a special case of a general principle: any impartial game whose positions are tuples, whose terminal positions are those with a zero coordinate, and whose moves reduce exactly one coordinate will have Sprague–Grundy value $1+\bigoplus(k_i-1)$; checking other move sets, such as constrained reductions, would show where the principle breaks.
  • The value-$1$ partitions of Theorem 2 form intervals in Young's lattice, so the number of such partitions of each integer $n$ should have a generating function; the appendix data up to $n=26$ are a natural testbed for guessing and proving such a formula.
  • The rectangle-value matrix's stated property of being lexicographically first with no repeated row or column entry suggests that the XOR-plus-one array can be characterized purely order-theoretically, independent of game theory.
  • The conjectures on heavy partitions suggest that heavy positions may also form lattice intervals, analogous to the value-$1$ family; testing Conjecture 2 on the smallest non-heavy rectangles would either confirm the interval pattern or expose a sharper boundary.
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.

Referee Report

3 major / 4 minor

Summary. The paper introduces PNim, a game on Young diagrams where a move removes a positive number of rows or columns, and RNim, a game on hyperrectangles where a move reduces one side length. The main results are: Proposition 1/2 giving a tight longest-play upper bound for PNim; Theorem 1 giving G_P(Jc^rK) = ((r-1) XOR (c-1)) + 1 for rectangles; Theorem 2 characterizing partitions with Sprague-Grundy value one; Theorem 3 giving G_R(<k_1,...,k_d>) = ((k_1-1) XOR ... XOR (k_d-1)) + 1 for hyperrectangles; and a Conway-Gurvich-Ho classification together with misere-play consequences. The paper also contains computational data in appendices and formulates several conjectures.

Significance. The closed-form formulas for rectangles and hyperrectangles are elegant and connect the games to XOR arithmetic and Lucas's theorem in a way that does not arise from the disjunctive-sum structure. The CGH classification and the explicit misere strategy are useful additions to the study of impartial games on partitions. The paper is generally clearly written and includes concrete data supporting its conjectures. However, the proof of Theorem 2 currently contains a concrete false step in part (i), and Corollary 11, which is used in the proof of Theorem 3, is stated without proof. These issues must be repaired before the central claims can be regarded as established.

major comments (3)
  1. [Section 3, proof of Theorem 2(i)] The construction claimed to produce a move into S is incorrect. For lambda = J5,5,4K, we have lambda_1 = 5; after padding lambda_4 = 0, the smallest violation is i = 4, so the prescribed move removes the first lambda_1 - i + 1 = 2 columns. The remaining columns have heights 3, 2, 2, giving the conjugate partition J3,3,1K, which is not in S: for r = 3 the S-interval is J3,3,2K <= . <= J3,3,3K, and S contains no partition J3,3,1K. A different move (removing the first three columns) does reach J2,2K in S, so the theorem may still be true, but the proof of (i) as written fails.
  2. [Section 3, proof of Theorem 2] Even if part (i) were corrected, the two assertions (i) and (ii) are not by themselves sufficient to conclude the characterization. They do not force the mex to be exactly 1 for positions in S, nor do they show that positions outside S have mex different from 1. One needs a simultaneous induction on, say, lambda_1 + length(lambda) or the longest-play measure f, proving that every lambda in S has an option set containing 0 and avoiding 1, while every mu outside S has an option with Sprague-Grundy value 1. The manuscript should state this induction explicitly; the current proof omits it.
  3. [Section 4, Corollary 11] Corollary 11 is stated with the proof omitted, but it is exactly the equality used in the final display of the proof of Theorem 3. Since Theorem 3 is a central result, this gap is load-bearing. The corollary follows from Lemma 5 and Observation 10, so it is not a false assertion, but the proof should be included rather than left as 'the proof, which we omit'.
minor comments (4)
  1. [Section 3, proof of Theorem 2] The reduction 'Without loss of generality assume lambda_1 >= r' should explicitly cite Observation 4 (conjugate invariance), since it is not otherwise clear why one may assume this inequality.
  2. [Section 3, proof of Theorem 2] The sentence 'Notice that for 2 <= i <= lambda_1 we have Jlambda_1,...,lambda_rK in S <=> lambda_i >= lambda_1 - i + 2' is misquantified: membership in S is a conjunction over all i in that range, together with the length constraint, and should be written with a universal quantifier.
  3. [Section 3, proof of Proposition 3] The expression 'G_P(J1K])' contains a stray closing bracket; it should read 'G_P(J1K)'.
  4. [Section 6, paragraph after Question 1] The phrase 'all partitions with of order at most 15' should read 'all partitions of order at most 15'.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the main theorems are derived from mex definitions, induction, and standard external results; the authors' self-citations are contextual and not load-bearing.

full rationale

The paper's central claims (Theorem 1, Proposition 1, Theorem 2, Theorem 3, and the CGH classification) are derived from first principles: the definition of Sprague-Grundy values as mex sets, induction on rectangle size or minimal counterexample, Lemma 5 and Lemma 6, and the standard Nim-sum mex identity. No fitted parameters are used, and no quantity is renamed as a prediction. The paper does cite prior work by the same authors (LCTR [8] and Impartial Chess [13]), but these citations appear only in the related-work discussion and in the CGH classification figure as contextual labels; they are not premises of any theorem. The CGH classification of PNim and RNim is obtained by applying Gurvich and Ho's external theorem that pet games are exactly those without (0,0)-positions, together with the terminal-position facts. One omitted proof (Corollary 11) is explicitly labeled as similar to Lemma 6 and is a routine corollary, not a circular step. A possible correctness gap in the constructive part of Theorem 2's proof, such as the move from J5,5,4K not landing in S, and the missing explicit induction tying assertions (i) and (ii) to the mex conclusion, would be a mathematical flaw, not circularity: the characterization is not assumed as an input. Overall, the derivation chain is self-contained and the score is 0.

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

The paper introduces no new physical entities; the new games PNim and RNim are definitions, not postulates. No parameters are fitted to data.

assumptions (5)
  • standard math Sprague-Grundy theorem and mex characterization of impartial games
    Used throughout to define SG values and to analyze game sums; stated in Section 2.
  • standard math Lucas's theorem on binomial coefficients modulo a prime
    Used in Observation 9 to characterize heavy rectangles; stated as Theorem 7 in Section 3.
  • domain assumption Conway-Gurvich-Ho classification theorems, including that a game is pet iff it has no (0,0)-position and the closure properties of miserable and returnable games under disjunctive sum
    Used in Section 5, Proposition 6 and Corollary 13, to classify PNim and RNim; cited to [22].
  • domain assumption Conway's theorem computing misère Grundy values of disjunctive sums of tame games
    Used as Theorem 14 in Section 5.1 to compute misère values; cited to [18, 22].
  • ad hoc to paper Corollary 11, a shifted mex formula for Nim-sum, is stated without proof
    The proof is omitted as 'similar to Lemma 6'; it is needed in the proof of Theorem 3.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Nim on Integer Partitions and Hyperrectangles." pith.science (2026). https://pith.science/paper/5AQ7PZAW

@misc{pith2026250604991,
  author       = {Pith},
  title        = {Pith review of: Nim on Integer Partitions and Hyperrectangles},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/5AQ7PZAW}},
  note         = {Machine review of arXiv:2506.04991}
}
read the original abstract

We describe PNim and RNim, two variants of Nim in which piles of tokens are replaced with integer partitions or hyperrectangles. In PNim, the players choose one of the integer partitions and remove a positive number of rows or a positive number of columns from the Young diagram of that partition. In RNim, players choose one of the hyperrectangles and reduce one of its side lengths. For PNim, we find a tight upper bound for the Sprague-Grundy values of partitions and characterize partitions with Sprague-Grundy value one. For RNim, we provide a formula for the Sprague-Grundy value of any position. We classify both games in the Conway-Gurvich-Ho hierarchy.

Figures

Figures reproduced from arXiv: 2506.04991 by the authors.

Figure 1
Figure 1. The CGH classifications of 1-PNim, 1-RNim, PNim, RNim, and some known games; see [8, 13, 19, 23]. The domestic class is not relevant for this paper so we omit it. Corollary 13. The games PNim and RNim are miserable, but not pet. They are also returnable, but not forced. Proof. The property of being both miserable and returnable is closed under disjunctive sum, thus PNim and RNim are miserable and returnable; see [22… view at source ↗

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

25 extracted references · 23 canonical work pages

  1. [1]

    C. L. Bouton, Nim, a game with a complete mathematical theory, Annals of Mathematics 3 (1/4) (1901) 35–39. URLhttp://www.jstor.org/stable/1967631

    work page arXiv 1901

  2. [2]

    R. P. Sprague, Über mathematische kampfspiele, Tohoku Mathematical Journal, First Series 41 (1935) 438–444

    work page 1935

  3. [3]

    P. M. Grundy, Mathematics of games, Eureka 2 (1939) 6–8

    work page 1939

  4. [4]

    Sato, On maya game (notes by h

    M. Sato, On maya game (notes by h. enomoto), Sugaku no Ayumi 15 (1) (1970) 73–84

    work page 1970

  5. [5]

    Irie, p-saturations of welter’s game and the irreducible representations of symmetric groups, Journal of Algebraic Combinatorics 48 (2018) 247–287

    Y. Irie, p-saturations of welter’s game and the irreducible representations of symmetric groups, Journal of Algebraic Combinatorics 48 (2018) 247–287. 14

    work page 2018

  6. [6]

    Abuku, M

    T. Abuku, M. Tada, A multiple hook removing game whose starting po- sition is a rectangular Young diagram with unimodal numbering, Integers 23 (2023) Paper No. G1, 37

    work page 2023

  7. [7]

    Game positions of Multiple Hook Removing Game

    Y. Motegi, Game positions of multiple hook removing game (2021).arXiv: 2112.14200. URLhttps://arxiv.org/abs/2112.14200

    work page Pith review arXiv 2021

  8. [8]

    Gottlieb, M

    E. Gottlieb, M. Krnc, P. Muršič, Sprague–Grundy values and complexity for LCTR, Discrete Applied Mathematics 346 (2024) 154–169.doi:10. 1016/j.dam.2023.11.036

    work page 2024

Show all 25 references
  1. [9]

    Gottlieb, J

    E. Gottlieb, J. Ilić, M. Krnc, Some results on LCTR, an impartial game on partitions, Involve, a Journal of Mathematics 16 (3) (2023) 529–546. doi:10.2140/involve.2023.16.529

    2023 doi

  2. [10]

    Bašić, E

    I. Bašić, E. Gottlieb, M. Krnc, Some observations on the Column-Row game, in: Proceedings of the 9th Student Computing Research Symposium (SCORES’23), 2022.doi:10.26493/scores23

    2022 doi

  3. [11]

    Bašić, Column-Row game, Master’s thesis (2023)

    I. Bašić, Column-Row game, Master’s thesis (2023). URLhttps://repozitorij.upr.si/IzpisGradiva.php?id=19707

    2023

  4. [12]

    E.R.Berlekamp, ImpartialChess,https://math.berkeley.edu/˜berlek/ (2017)

    2017

  5. [13]

    Gottlieb, M

    E. Gottlieb, M. Krnc, P. Muršič, Impartial chess on integer partitions (2025).arXiv:2501.14640. URLhttps://arxiv.org/abs/2501.14640

    2025 arXiv

  6. [14]

    Meit, Two partizan games on integer partition, Master’s thesis, Rhodes College (2025)

    H. Meit, Two partizan games on integer partition, Master’s thesis, Rhodes College (2025)

    2025

  7. [15]

    F. J. Dyson, Some guesses in the theory of partitions, Eureka (Cambridge) 8 (10) (1944) 10–15

    1944

  8. [16]

    G. E. Andrews, The theory of partitions, Cambridge Mathematical Library, Cambridge University Press, Cambridge, 1998, reprint of the 1976 original

    1998

  9. [17]

    A. N. Siegel, Combinatorial game theory, Vol. 146 of Graduate Studies in Mathematics, American Mathematical Society, Providence, RI, 2013. doi:10.1090/gsm/146

    2013 doi

  10. [18]

    J. H. Conway, On numbers and games, 2nd Edition, A K Peters, Ltd., Natick, MA, 2001

    2001

  11. [19]

    Berlekamp, J

    E. Berlekamp, J. Conway, R. Guy, Winning Ways for Your Mathematical Plays: Volume1-4, AKPeters/CRCRecreationalMathematicsSeries, CRC Press, 2018. URLhttps://books.google.si/books?id=-0laDwAAQBAJ 15

    2018

  12. [20]

    N. J. Fine, Binomial coefficients modulo a prime, The American Mathe- matical Monthly 54 (10) (1947) 589–592. URLhttp://www.jstor.org/stable/2304500

    1947

  13. [21]

    arXiv:1001.1783

    E.Rowland, Thenumberofnonzerobinomialcoefficientsmodulop α (2011). arXiv:1001.1783. URLhttps://arxiv.org/abs/1001.1783

    2011 arXiv

  14. [22]

    V. A. Gurvich, N. B. Ho, On tame, pet, domestic, and miserable impartial games, Discrete Applied Mathematics 243 (2018) 54–72.doi:10.1016/j. dam.2017.12.006

    2018 doi

  15. [23]

    W. A. Wythoff, A modification of the game of Nim, Nieuw Archiefvoor Wiskunde (1907-1908) 199–202

    1907

  16. [24]

    OEIS Foundation Inc., The on-line encyclopedia of integer sequences, https://oeis.org/A103889(2005)

    2005

  17. [25]

    OEIS Foundation Inc., The on-line encyclopedia of integer sequences, https://oeis.org/A280172(2016). 16 A. Small partitions withGP value2 All partitionsλwithG P(λ) = 2of order at mostn= 26, up to conjugation: 17 B. Small heavy partitions underPNim All heavy partitions underPNi...

    2016

Pith tools

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