Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

First of all the puzzle.

A barman's got 15 glasses which are initially somehow divided into several stacks. The barman repeats the following process a thousand times. He takes the top glass from each (nonempty) stack and forms a new stack with these glasses. Which set of stacks (in terms of their heights) will he come up with?

It's a nice one, give it some thought =)

Having toyed with this problem and its obvious generalizations for an arbitrary number of glasses I came up with the (totally intuitive) hypothesis that such a process and its long-term behavior might emerge in some more-or-less advanced field of research (algebra/geometry/mathematical physics). Can anybody comment?

Update. One can also notice that in this special case of 15 glasses both the problem's statement and the answer are pleasantly simple. I'd be very interested and even somewhat surprised to hear an accordingly simple proof.

share|improve this question
    
I did it with 10+3+2 and I know the answer in this case.=) –  Olga May 14 '12 at 21:21
    
Reminds me a little of the card trick inspired by Birhoff's Ergodic theorem. It is described at the end of these lecture notes: maths.manchester.ac.uk/~cwalkden/ergodic-theory/lecture22.pdf –  Edmund Harriss May 14 '12 at 22:38
11  
This is known as Bulgarian solitaire, see en.wikipedia.org/wiki/Bulgarian_solitaire. There is some literature on it, though I don't know whether any of the literature concerns scientific applications. –  Gerry Myerson May 14 '12 at 22:48
    
Wow, thanks! Nice to know. –  Igor Makhlin May 15 '12 at 0:25
1  
Brian Hopkins has written a survey, "30 Years of Bulgarian Solitaire," for the March 2012 issue of The College Mathematics Journal. Among other things, it gives a detailed history of the problem and how it came by its name. –  Barry Cipra May 15 '12 at 15:35

1 Answer 1

I don't know about scientific applications, but you can solve the puzzle as follows (I hope you consider this solution simple):

Look at the Ferrers diagram of the partition of 15 you have, and consider the sum of the Manhattan distances from each dot to the corner of the diagram. At every step of the barman's process, this sum either stays the same or decreases, and it only stays the same if the number of stacks is at least as large as the size of the largest stack minus 1. In this case, we get the new Ferrers diagram by "rotating" the first column of the Ferrers diagram to make it into the first row, and shifting the rest of the diagram diagonally. For example:

x*****      xxxxx
x***        *****
x**     ->  ***
x           **
x

If we assume the existence of a cycle of partitions, then this sum must be constant along the cycle, so the Ferrers diagrams in the cycle can be produced by simply cyclically shifting each diagonal. If there are two adjacent partially filled diagonals, then since adjacent numbers are relatively prime, eventually in this cycle we will get a Ferrers diagram where a hole in the diagonal closer to the corner is next to a dot in the further diagonal, which is not allowed. For instance, if we continue the previous example, we eventually see the hole in the fifth diagonal line up with the dot in the sixth diagonal:

******     *****     ****     *****     *****     *****     ******     ****
****       *****     ****     ***       ****      ****      ****       *****
***    ->  ***   ->  **** ->  ***   ->  **    ->  ***   ->  ***    ->  ***
*          **        **       ***       **        *         **         **
*                    *        *         **        *                    *
                                                  *

Thus, there is at most one partially filled diagonal in any partition that cycles, and the only partition of $15$ satisfying this condition is $15 = 1+2+3+4+5$. Since the number of partitions of $15$ is less than $1000$, the barman enters this cycle before the end of his process.

share|improve this answer
    
Well, actually this is the solution I came up with myself, so I was hoping for something considerably shorter. Something that actually employs the sum being a triangular number. A reduction to something widely known would also be nice. –  Igor Makhlin May 14 '12 at 23:53
    
I was afraid of that... –  zeb May 14 '12 at 23:56
    
If the sum were not a triangular number, there would be several partitions with partially filled diagonals. For instance, 16 has the cycle 6+4+3+2+1, 5+5+3+2+1, 5+4+4+2+1, 5+4+3+3+1, 5+4+3+2+2, 5+4+3+2+1+1, etc. If the number is far from a triangular number, there are multiple cycles. –  Will Sawin May 15 '12 at 3:36
    
Yep, true story. This is what I meant by "in this special case of 15 glasses both the problem's statement and the answer are pleasantly simple". –  Igor Makhlin May 15 '12 at 11:13

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.