The following game was made popular by Martin Gardner in the early 1980's. Begin with a fixed number of pennies and arrange them into piles in any way you like. A move in the game consists of taking one penny from each pile and forming a new pile with them. Keep repeating the process until you encounter an arrangment of (unordered) piles that you have seen before.

For example, if you started with piles of size (2,2,1,1), the first move would have you to piles of size (4,1,1), the next to (3,3), the next to (2,2,2), the next to (3,1,1,1), the next to (4,2), the next to (3,2,1), and then finally to (3,2,1) again when the game stops because you have seen (3,2,1) twice.

A moment's thought shows that the game always stops. There are, after all, only a finite number of configurations of piles. If the number of moves exceeds the number of possible configurations, the pigeon hole principle guarantees that you must have already met the same configuration of piles somewhere along the way.

There are a few obvious questions: What at the possible ending configurations of piles? How many moves does it take to get to them? What if we changed the game and kept track of the order of the piles?

One nice approach to these questions is based on a way to visualize the move operation. I learned this is in an article by Griggs and Ho titled "The Cycling of Partitions and Compositions under Repeated Shifts", which is a little dense and abstract, but might make for the starting point of a nice independent study project. (Let me know if you're interested.)

This week we want to prove (using the visual interpretation of the Bulgarian solitaire move) the main conjecture we formulated last time. Write n uniquely as a sum of a triangular "core" plus a deviation from being triangular:

n = 1+2+...+ k + t

(where t is greater than or equatl to 0 and less than or equal to k). The conjecture is as follows: the only ending configurations are of the form (1,2,...,k) with 1's added to t distinct piles, and all of these configurations are indeed ending configurations. For example, if n is itself triangular (and so t=0), the only ending configuration is (1,2,...,k).

We then want to find the maximum number of moves required (at least if t is 0) to land on one of these ending configurations.

Finally, we will move on to related games of this nature, including a problem from an IMO in the 1960s.

Last time we mostly went in a different direction and tried to determine the configurations which could only arise as starting confirgurations; that is, the ones which do not come from a move applied to another configuration. One of the participants suggested calling such configurations a Garden of Eden (or GE for short), following terminology that arises in a similar situation in the Game of Life. We proved that a initial configuration is a GE if and only if the number of piles is greater than equal or equal to two plus the number of objects in the largest pile.

It turns out that it is possible to write down all GEs, but this is a little bit tricky. You can find more details here: An Exact Enumeration of Garden of Eden Partitions by B. Hopkins and J. Sellers.

This time, tacked away from Bulgarian Solitaire into other seemingly unrelated questions that can be answered by the kind of analysis we developed for Bulgarian Solitaire. The main problem we discussed (but did not solve) is discussed in notes here. (Spoiler alert: don't read past page 10 until we meet next time.)