3

Interesting puzzle that I haven't been able to solve or find a solution to.

An ant rearranges a line of stacks of seeds as follows:

With each iteration, the ant goes to each stack in order and grabs a single seed from each; then, when reaching the end of the line, places the seeds it has accumulated at the end of the line as a new stack. [for example: given the following line $(3,4,2,4)$ after one iteration: $(3,4,2,4)\to (2,3,1,3,4)$]

Note that when a stack is reduced to zero, it is considered as removed: $$(4,1,3) \to (3,0,2,3) = (3,2,3)$$

Prove that, given that the sum of seeds in the line is a triangular number (i.e $T_n = 1 + 2 + 3 + \cdots + n$), the ant's infinite rearrangement will ultimately converge to a steady state of $(1,2,3,...,n)$.

Additional example:
$$(4,2) \rightarrow (3,1,2) \rightarrow (2,1,3) \rightarrow (1,2,3)$$

I have been able to accumulate some thoughts on this puzzle but nothing too concrete to hint towards a solution, I would love to discuss possible approaches for this puzzle and find out the solution.

Thanks!

Edit: My thoughts on the puzzle.

Firstly, any permutation on $[n] := \{1,2,...n\}$ will eventually converge to the steady state. This is easy enough to see. So it is sufficient to prove that any initial state of the puzzle (with the sum being a triangular number) will eventually become a permutation on $[n]$.

Second, although it is not a strong indication, it might be a nice direction to ponder in: if the length of the line is $n$ and, the elements are distinct, the line is a permutation on $[n]$. So this is some weaker version of the statement about which might be easier to approach.

Third, I have been trying to model this puzzle as an operator on vectors/matrices/series, but with no success. But thinking of the ant's iterations as an operator $F$, then $F$ is not reversible, since eventually it reaches a steady state. So applying a group-like operation or model on this puzzle might not work.

Fourth, a clear invariant in this puzzle is the sum of seeds, and seems to be almost the only one (if not the only). So thinking of invariant-preserving operators might come in handy, although I'm not familiar with enough and haven't been able to identify useful operators (and respective spaces) to help me model this puzzle efficiently.

Currently, this is about it.

Blue
  • 75,673
Eran723
  • 99
  • On this site, it's considered appropriate, even necessary, to share the thoughts you've had on the puzzle. Please do so by editing the question. – Robert Shore Sep 12 '23 at 08:31
  • We can check that $1,2,3... n$ is a stable configuration ; we can also check that the only stable configurations are $1,2,3...n$ – Lourrran Sep 12 '23 at 08:45
  • 1
    Very nice puzzle! A couple of thoughts on it: the ant is making compositions (partitions where the order matters) of the number of seeds, $N$. If you can find a good way to represent the space of compositions and what the ant's algorithm does to it, that would help a lot... – Chris Lewis Sep 12 '23 at 09:26
  • ...Additional questions that might be helpful to think about are (1) what initial configuration(s) take the longest to settle to a steady state? (2) what happens when the number of seeds isn't a triangular number? – Chris Lewis Sep 12 '23 at 09:26
  • 2
    I believe this is sometimes referred to as Bulgarian solitaire, do a search for that. – Gerry Myerson Sep 12 '23 at 09:58
  • 2
    See, for example, https://math.stackexchange.com/questions/253860/the-pebble-sequence and https://math.stackexchange.com/questions/438970/problem-about-a-process-with-bins-of-balls and https://math.stackexchange.com/questions/1850772/towers-of-coins-puzzle and probably several other discussions on this website. – Gerry Myerson Sep 12 '23 at 10:01
  • I didn't know that this was Bulgarian solitaire! I will look into this game and the referred queries. – Eran723 Sep 12 '23 at 10:40

0 Answers0