[seqfan] Re: pebbles sequence

Max Alekseyev maxale at gmail.com
Thu Nov 19 15:56:15 CET 2009

On Wed, Nov 18, 2009 at 2:47 PM, Tanya Khovanova
<mathoflove-seqfan at yahoo.com> wrote:

> You have 45 pebbles arranged in several piles. Each turn you take one pebble from each pile and put them into a new pile. What is an asymptotic behavior for this process?
>
> For example, if you start with one pile of 6, next step will be two piles: {1,5}, then {2,4} and so on. Eventually the sequence of partitions will start repeating itself.

There is an interesting variant of this problem: Suppose we have k
(nonempty) piles with pebbles arranged in a row. Each turn one take
all, say, m pebbles from the leftmost pile and spread them equally
among the other k-1 piles (i.e., each pile gets [m/(k-1)] new
pebbles), putting the remaining m mod (k-1) pebbles (if any) into a
new rightmost pile. The process stop when we either encounter a cycle
or a single pile.

E.g.: (5,5,5,5) -> (6,6,6,2) -> (8,8,4) -> (12,8) -> (20)   (a single pile)

E.g.: (5,3,1) -> (5,3,1) -> ...  (a cycle of length 1)

Other variant: Each turn distribute m pebbles from the leftmost pile
over the other piles from left to right, putting one pebble into each
pile (i.e., each pile gets at most one new pebble), and the remainder
m-(k-1) (if it's nonnegative) into a new rightmost pile.

E.g.: (5,5,5,5) -> (6,6,6,2) -> (7,7,3,3) -> (8,4,4,4) -> (5,5,5,5)
(a cycle of length 4)

Somewhat similar game is described in
http://www.research.att.com/~njas/sequences/A161135

Regards,
Max