The arithmetic-progression partition heaviness conjecture

A stronger theorem: every partition with distinct parts is heavy

Let $\mathcal G(\lambda)$ denote the Sprague–Grundy value of a single partition in PNim, and write $\lambda'$ for its conjugate. The rules are invariant under interchanging rows and columns, so

$$\mathcal G(\lambda)=\mathcal G(\lambda').$$

We prove the following statement, which strictly strengthens the conjecture.

Theorem. If

$$\lambda=(\lambda_1>\lambda_2>\cdots>\lambda_r>0)$$

has distinct parts, then

$$\boxed{\mathcal G(\lambda)=\lambda_1+r-1.}$$

In particular, every partition with distinct parts is heavy.

The source already proves the special staircase case

$$\lambda=(c,c-1,\ldots,c-r+1)$$

in Proposition 4. The argument below extends its three-range minimum-excluded-value strategy to arbitrary distinct-part partitions by using the full multiplicity profile of the column heights.

Upper bound. Set $w=\lambda_1$. Every move between nonempty partitions decreases the sum of the numbers of rows and columns by at least one, while the final move to the empty partition decreases this sum by at least two. Consequently, a play beginning at $\lambda$ has at most $w+r-1$ moves. The Sprague–Grundy value of any finite impartial-game position is bounded by its maximum play length. Therefore,

$$\mathcal G(\lambda)\leq w+r-1.$$

This is also the general upper bound established in the source.

Column-height structure. Since the parts of $\lambda$ are distinct, its Young diagram has at least one column of every height

$$1,2,\ldots,r.$$

More precisely, if $c_h$ denotes the number of columns of height $h$, then

$$c_h= \begin{cases} \lambda_h-\lambda_{h+1},&1\leq h<r,\\ \lambda_r,&h=r, \end{cases} \qquad c_h\geq1, \qquad \sum_{h=1}^{r}c_h=w.$$

A column move retains any proper submultiset of these column heights. If the retained heights, written in decreasing order, form the partition $\nu$, the resulting position is $\nu'$. Hence its Sprague–Grundy value is $\mathcal G(\nu)$.

Induction. We proceed by strong induction on $w+r$. The partition $(1)$ has Sprague–Grundy value $1$, giving the base case. Assume the theorem holds for every strict partition with a smaller value of $w+r$.

It suffices to realize every integer

$$0\leq t\leq w+r-2$$

as the Sprague–Grundy value of a position reachable from $\lambda$. The value $t=0$ is obtained by deleting all columns. For $t>0$, there are three cases.

Case 1: $1\leq t\leq r$. Retain exactly one column of height $t$. The resulting position is conjugate to the strict one-part partition $(t)$, whose Sprague–Grundy value is

$$\mathcal G((t))=t.$$

Whenever this case occurs in the required target range, the retained column is a proper subset of the original columns. The induction parameter of $(t)$ is $t+1<w+r$.

Case 2: $r<t\leq2r-2$. Put

$$k=t-r+1, \qquad 2\leq k\leq r-1.$$

Retain one column of height $r$ and one column of each height

$$1,2,\ldots,k-1.$$

The retained column-height partition is

$$\nu=(r,k-1,k-2,\ldots,1),$$

which has distinct parts, largest part $r$, and exactly $k$ parts. Since

$$r+k\leq2r-1<w+r,$$

the induction hypothesis and conjugacy give

$$\mathcal G(\nu') =\mathcal G(\nu) =r+k-1 =t.$$

Case 3: $2r-1\leq t\leq w+r-2$. Put

$$K=t-r+1, \qquad r\leq K\leq w-1.$$

Because every height $1,\ldots,r$ occurs at least once and the total number of columns is $w$, we can retain exactly $K$ columns while retaining at least one column of each height. Indeed, begin with one column of each height and distribute the remaining $K-r$ choices among the available

$$\sum_{h=1}^{r}(c_h-1)=w-r$$

additional columns.

Let $d_h$ denote the number of retained columns of height $h$. Then

$$1\leq d_h\leq c_h, \qquad \sum_{h=1}^{r}d_h=K.$$

The resulting partition $\mu$ has row lengths

$$\mu_j=\sum_{h=j}^{r}d_h \qquad (1\leq j\leq r).$$

Therefore,

$$\mu_j-\mu_{j+1}=d_j>0 \qquad(1\leq j<r), \qquad \mu_r=d_r>0.$$

Thus $\mu$ itself has distinct parts, exactly $r$ rows, and largest part

$$\mu_1=K<w.$$

The move is proper, and its induction parameter satisfies $K+r<w+r$. Applying the induction hypothesis yields

$$\mathcal G(\mu)=K+r-1=t.$$

The three cases cover every required positive value, with empty intervals simply omitted. Consequently, the option values contain

$$\{0,1,\ldots,w+r-2\}.$$

By the minimum-excluded-value rule,

$$\mathcal G(\lambda) \geq w+r-1.$$

Together with the upper bound, this proves

$$\mathcal G(\lambda)=w+r-1.$$

Application to the conjecture. For positive integers $i,s,k$, consider

$$\lambda= \bigl(i+(k-1)s,\ i+(k-2)s,\ \ldots,\ i+s,\ i\bigr).$$

Since $s>0$, its parts are distinct. Its largest part is $i+(k-1)s$, and it has $k$ parts. The theorem therefore gives

$$\boxed{ \mathcal G(\lambda) =i+(k-1)s+k-1 =i+(k-1)(s+1). }$$

This equals the maximal possible play length, proving the conjecture for every positive $i,s,k$. The argument establishes the stronger distinct-part theorem but makes no claim that all heavy partitions must have distinct parts.

Source: E. Gottlieb, M. Krnc, and P. Muršič, Nim on Integer Partitions and Hyperrectangles, Conjecture 3, Proposition 4, and the general PNim upper bound.