Skip to main content
MathOverflow

Return to Question

Cite "plane partitions."
Source Link
Joseph O'Rourke
Joseph O'Rourke
  • 150.8k
  • 36
  • 358
  • 958

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. Then (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).

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. 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).

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).

Source Link
Joseph O'Rourke
Joseph O'Rourke
  • 150.8k
  • 36
  • 358
  • 958

A variation on Bulgarian solitare

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. 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).