A variation on Bulgarian solitare

Question

It appears that a variation on Bulgarian solitare has a fixed point regardless of the starting $n$.

For example, let $n=69$, and consider this partition: $$ (8,8,7,7,5,5,5,5,5,4,3,3,2,2) $$ In Bulgarian solitare, $1$ would be removed from each "stack/pile" to form another stack. In the variation, I remove $1$ just from the $k=9=3^2$ largest stacks, $(8,8,7,7,5,5,5,5,5)$. That reduces those stacks to $(7,7,6,6,4,4,4,4,4)$ and adds a stack of size $9$.

I find it easier to visualize this process with the stacks organized in an array with the largest stacks surrounding the upperleft corner. (Added: I just learned these are known as plane partitions.) Then $1$ is removed from the $3 \times 3$ square of stacks including the upperleft corner. The numbers are resorted and the same process applied again, always gathering from the largest $k=9$ stacks: $$ \left( \begin{array}{cccc} 8 & 8 & 5 & 4 \\ 7 & 7 & 5 & 3 \\ 5 & 5 & 5 & 3 \\ 0 & 0 & 2 & 2 \\ \end{array} \right) \;\rightarrow\; \left( \begin{array}{cccc} 9 & 7 & 6 & 4 \\ 6 & 7 & 4 & 4 \\ 4 & 4 & 4 & 3 \\ 0 & 2 & 2 & 3 \\ \end{array} \right) \;\rightarrow\; \left( \begin{array}{cccc} 9 & 8 & 5 & 3 \\ 6 & 6 & 5 & 3 \\ 3 & 4 & 4 & 3 \\ 2 & 2 & 3 & 3 \\ \end{array} \right) \;\rightarrow\; \cdots $$ The endpoint of this process, after $20$ steps, is: $$ \left( \begin{array}{cccccc} 9 & 8 & 5 & 1 & 1 & 1 \\ 6 & 7 & 4 & 1 & 1 & 1 \\ 1 & 2 & 3 & 1 & 1 & 1 \\ 1 & 1 & 1 & 1 & 1 & 1 \\ 1 & 1 & 1 & 1 & 1 & 1 \\ 0 & 0 & 0 & 1 & 1 & 1 \\ \end{array} \right) $$ This seems to be a fixed point regardless of $n$, as long as the list of stacks is longer than the largest $k$ being reduced at each step. (If $k$ encompasses the entire list of stacks, this just reduces to Bulgarian solitare, and cycles rather than fixed points can occur.)

My question is: Is this true, that the process described leads to the fixed point $$(k, k{-}1, k{-}2, \ldots, 3,2,1,1,1,\ldots,1)$$ under those conditions? It's a bit surprising to me that it doesn't lead to cycles for non-triangular $n$. Perhaps it does? I have not explored extensively (and I've only looked at $k$ which are squares).

Answer 1

Yes, that is what happens if there are at least $k$ stacks at each step.

It is quite clear that all stacks will be eventually bounded by $k$, since either the highest number of cards or the number of stacks with the highest number of cards reduces at every iteration if there is a stack of strictly more than $k$ cards. When we have reached this state, the biggest stack always has $k$ cards.

Let $N_m$ denote the number of stacks of size $m$ and define the function $\phi_a(i)=1+\max\{0,i-a\}$, $a\in\mathbb N$. Suppose we have already reached the state when $N_m=0$ for $m>k$. At every iteration $N_k\mapsto\phi_k(N_k)$. (One stack of size $k$ is created, up to $k$ become smaller.) This map is strictly decreasing as long as $N_k>1$, so eventually $N_k=1$.

Then suppose $N_k\equiv1$ and consider $N_{k-1}$. If $N_{k-1}=0$, then it will be one on the next turn, so we can assume $N_{k-1}\geq1$. At every iteration $N_{k-1}\mapsto\phi_{k-1}(N_{k-1})$. Again $\phi_{k-1}$ is strictly decreasing until it hits its fixed point $1$, so eventually $N_{k-1}=1$.

This argument can be continued inductively, using $\phi_m$ for $N_m$. Eventually $N_k=N_{k-1}=\dots=N_2=1$. But $\phi_1$ is the identity map, so $N_1$ does not tend to $1$; it just stays where it happens to end up.

Clarification: As the OP's example demonstrates, not every $N_i$ is always strictly decreasing. When we have reached the state where all stacks are bounded by $k$, the number $N_k$ is strictly decreasing (until it hits one). When $N_k$ has stabilized to one, $N_{k-1}$ is strictly decreasing (until it hits one), and so on. If $N_{k-1}$ happens to be zero, it will become one in one turn and stay there. So each $N_m$ will only start its monotone decay towards one when $N_i=0$ for $i>k$ and $N_i=1$ for $k\geq i>m$ (again with the exception when it grows one step).

Assuming no zeros occur for $N_m$, $m\leq k$, the sequence $(N_i)_{i=1}^\infty$ is strictly decreasing in lexicographical order: if $m$ is the highest index for which $N_m$ changes, then $N_m$ decreases (strictly, unless we are at the final fixed point).