3

A friend of mine give me this problem for fun:

Given $\frac {n(n+1)}{2}$ balls, first we divide arbitrarily these balls in baskets, after that we make another basket with one ball of each basket e do this procedure infinitely.

I want to prove that one time this stabilizes with 1 ball in one basket, 2 balls in another basket, ..., n balls in another basket.

It seems easy to solve, he says we can use some concept of energy (???), I'm trying with some concepts of combinatorics without any success.

Thanks in advance.

Steven Stadnicki
  • 51,746
user85493
  • 199
  • Hi, welcome to MSE. You second paragraph where you explain what you do with the balls is unfortunately not clear (at least to me). How many baskets are there? How do you divide the balls into baskets?, etc. – Lord Soth Jul 08 '13 at 16:11
  • 1
    Please give your question a meaningful title. – Chris Eagle Jul 08 '13 at 16:32
  • It sounds like you have $n$ baskets and distribute the balls in any way. Then you have another set of $n$ baskets. Into the first basket of the second set you put one ball from each of the first set of baskets that has one. Then into the second basket of the second set you put one ball from each of the first set that still has one, and keep going. Now repeat the process from the second set into the first. Is that what you are thinking? – Ross Millikan Jul 08 '13 at 16:34
  • 1
    @RossMillikan Then, the problem is, if, in the initial configuration, there were the entire $n(n+1)/2$ balls in the first basket of the first set, and none in the others, we do not run out of all the balls in the first basket of the first set of baskets after only "one pass." In fact, in this case the system will oscillate. – Lord Soth Jul 08 '13 at 16:52
  • 1
    user85493, you're really going to have to explain this better. – dfeuer Jul 08 '13 at 16:53
  • 1
    @LordSoth the number of basket is arbitrary. – user85493 Jul 08 '13 at 17:01
  • 1
    @RossMillikan the initial condition is with an arbitrary number of baskets – user85493 Jul 08 '13 at 17:02
  • Then, as Lord Soth says, if the number of baskets is at least $n(n+1)/2$ and we start with all the balls in one basket, after one move we have one ball each in $n(n+1)/2$ baskets and we oscillate. What you are trying to prove is then false. – Ross Millikan Jul 08 '13 at 17:07
  • I've edited the title to at least slightly reflect the content - 'Interesting Problem' says nothing useful about the question. Feel free to edit it further, obviously, but I definitely recommend giving at least some description of the problem in the title. – Steven Stadnicki Jul 08 '13 at 17:10

1 Answers1

5

I believe what you are discussing is known as Bulgarian solitaire. This is a theorem of Jorgen Brandt, i.e., that the game ends as you have described when the number of balls (or cards) is a triangular number, i.e., of the form $n(n+1)/2$.

Here is a nice source to read over: (paywall)

Solution of the Bulgarian Solitaire Conjecture

Kiyoshi Igusa

Mathematics Magazine

Vol. 58, No. 5 (Nov., 1985), pp. 259-271

Published by: Mathematical Association of America

Article Stable URL: http://www.jstor.org/stable/2690174

Note this is also the subject of a problem in the June/July 2013 AMM: Problem 11712.

Benjamin Dickman
  • 14,451