From radcliff@alpha2.csd.uwm.edu Mon Feb 22 16:18:29 CST 1999 Article: 236685 of sci.math Path: news.math.niu.edu!husk.cso.niu.edu!vixen.cso.uiuc.edu!uwm.edu!not-for-mail From: David G Radcliffe Newsgroups: sci.math,rec.puzzles Subject: Bulgarian Solitaire (was Re: Stacks of pennies) Supersedes: <7ajijc$tl6$1@uwm.edu> Date: 19 Feb 1999 11:51:24 GMT Organization: University of Wisconsin - Milwaukee Lines: 82 Message-ID: <7ajj7s$tl6$2@uwm.edu> References: <7a0sr5$6f1$1@uwm.edu> <7a270d$fc5$1@monet.op.net> <36c7c1e3.55503918@news.demon.co.uk> <338.713T1538T5203899@mistral.co.uk> NNTP-Posting-Host: 129.89.169.2 User-Agent: tin/pre-1.4-980117 (UNIX) (OSF1/V4.0 (alpha)) Xref: news.math.niu.edu sci.math:236685 rec.puzzles:119681 Thanks to all who responded to my previous post. I found quite a bit of information about this puzzle, once I learned its proper name, and I would like to share it with the Usenet community. In Bulgarian Solitaire, a player divides a deck of n cards into piles. Each move consists of removing one card from each pile to form a new pile. We are only interested in the number of piles of each size, i.e. the partition of n which the piles represent. If this move is repeated enough times, then a cycle of partitions will be reached. It is possible to describe precisely which partitions can appear in such a cycle. In the case that the number of cards is triangular, say n=1+2+3+...+k, there is a unique cycle (1,2,3,...,k). In other words, if you start with 1+2+3+...+k cards, and repeat the move enough times, then you will eventually have k piles of distinct heights 1, 2, ..., k, and this pattern will persist indefinitely. I shall make some harmless modifications to the game in order to simplify the analysis. Assume that the heights of the piles decrease from left to right. Our move is replaced with the following two moves: STEP 1. We remove cards from the bottom of each pile rather than from the top. Shift all of the piles one space to the right, and insert the new pile to the left. STEP 2. After performing this operation, it may happen that the first pile is shorter than the second pile. We correct this by shifting cards to the left, without changing the height of any card. Below is an example with 10 cards. (please view with fixed width font) A B F A A C G --> J B F --> J B F D H I C G I C G E I J E D H E D H Now we examine the itinerary of each card. Assign coordinates (x,y) to each position, so that (0,0) is the lower left corner. After the first step, a card at position (x,y) moves to (x+1,y-1) unless y=0, while a card at (x,0) moves to (0,x). Therefore the sum x+y remains unchanged for each card. In the second step, a card at position (x,y) will move to (x-1,y) if (0,y) is unoccupied; otherwise it remains at (x,y). If a card undergoes a left shift then the sum x+y of its coordinates is reduced by 1. Consider the quantity S, which defined as the the sum of x+y for all occupied positions (x,y). This quantity is not changed when step 1 is applied, but it is reduced whenever a lift shift occurs. For the remainder of this note we shall only consider partitions which cycle back to themselves. Note that such a cycle cannot involve a left shift. This is because a left shift reduces S, and it is impossible for S to decrease indefinitely. Consequently, each card moves along a diagonal path x+y=k, hopping one space down and to the right after each move, and jumping back to the top of the diagonal after it reaches the bottom. I claim that if a diagonal x+y=k is not full, then the diagonal above it is empty. Suppose that (x,k-x) is empty and (z,k+1-z) is occupied. The diagonal x+y=k has k+1 positions, and the diagonal x+y=k+1 has k+2 positions. After k+2 moves, the card on the upper diagonal returns to its previous position, and the blank space advances one space to the right. If this is repeated enough times, then the blank space will eventually lie directly underneath the card on the upper diagonal. But this is absurd. It follows that if n is a triangular number, say n=k(k+1)/2, then (1,2,3,...,k) is the only partition of n which cycles back to itself. Therefore, any partition of n will eventually be transformed to (1,2,3,...,k). QED The above argument is based on the one given in the following article. "The cycling of partitions and compositions under repeated shifts", by Jerrold R. Griggs and Chih-chang Ho. It is available at http://www.math.sc.edu/~ho/bulgarian.html -- David Radcliffe radcliff@uwm.edu