1001 Bowls and 1001 Marbles

1001 empty bowls are positioned so that they are equally spaced around the perimeter of a circle. 1001 marbles are then placed into one of the bowls. The marbles are then redistributed as follows:

1. A bowl is randomly selected from the bowls that contain at least two marbles.

2. Two marbles are removed from the selected bowl.

3. One of these two marbles is placed in the bowl that is one position clockwise from the selected bowl.

4. The other marble is placed in the bowl that is one position counter-clockwise from the selected bowl.

How many times must these steps be performed in order to end up with exactly one marble in each bowl?

Carl G.

S

P

O

I

L

E

R

S

P

A

C

E

At first I thought the question was ambiguous: it's not clear whether you want the minimum number of moves or the expected number of moves. But a few experiments (with N < 1001 marbles and bowls) showed that the number of moves was always the same...

Suppose there are N marbles and N bowls, where N is odd. Let f(j) be the number of times bowl number j is chosen in some sequence of moves. Then the change in the number of balls in bowl j is f(j-1) + f(j+1) - 2 f(j) (where the j+1 and j-1 are taken mod N). If bowl #0 is the one that starts with N marbles, we want f(j-1) + f(j+1) - 2 f(j) = 1 for 1<=j<=N-1. Writing this as f(j+1) - f(j) = 1 + f(j) - f(j-1), we see that f(j+1) - f(j) = a + j for some constant a, and then f(j) = j^2/2 + (a-1/2) j + f(0). In order to have f(N) = f(0), we need a = (1-N)/2, and then f(j) = (j-N/2)^2/2 - N^2/8+ f(0). The minimum value is at j=(N-1)/2: f((N-1)/2) = f(0) - (N^2-1)/8. Since f(j) can't be negative, we need f(0) >= (N^2-1)/8. Then the total number of moves is sum_{j=0}^{N-1} f(j) = f(0) N - N^3/12 + N/12 >= (N^3 - N)/24.

Now it seems that f((N-1)/2) must be 0, so that the total number of moves is exactly (N^3-N)/24. This means that it is impossible to get more than one ball to bowl number (N-1)/2.

Consider a minimal sequence of moves that ends with two balls in bowl M = (N-1)/2 or M+1. Without loss of generality we may assume it is M. It's convenient here to regard the bowls as numbered -M to M. Let f(j) be the number of moves where bowl j is chosen, and x(j) the final number of balls in bowl j. Note that S(i) = sum_{j=i}^M (j-i) x(j) = f(i) for i >= 0 (this sum started at 0, stayed the same on any move except from i or -M, increased by 1 on every move from j, and there were no moves from -M), while for i < 0 the sum started at -Ni so f(i) = S(i)+Ni. Let k+1 be the lowest-numbered bowl (of -M to M) that balls were taken from. Of course k <= -1. The last move was taking balls from M-1 to M and M-2, so x(M-2) >= 1. By minimality, the last move from bowl j (for k+1 <= j < M-2) came before the last move from bowl j+1, so the ball moved from j+1 to j in that last move is still there, i.e. x(j) >= 1 for k <= j <= M-1. So f(k) = Nk + S(i) >= Nk + sum_{j=k+1}^{M-2} (j-k) + 2(M-k) = (N+2k)^2/8 + 7/8 >= 1 contradicting the assumption that balls were never taken from bowl k.

This is still not completely satisfying because I don't have a proof that the process will ever end (as indeed it doesn't if N is even). But if it does, the number of moves is (N^3-N)/24 = 41791750.

Department of Mathematics http://www.math.ubc.ca/~israel University of British Columbia Vancouver, BC, Canada V6T 1Z2

Spoiler follows

Each step increases the variance of the marbles' positions by 2.

The initial variance is 0, the final variance is 2*(1^2 + 2^2 + 3^2 + ... + 500^2) = 2*500*501*1001/6 = 2*41,791,760.

Answer: 41,791,760 steps.

(Warning: I am aware that this proof has a gap in it. I claim that the conclusion is still valid.)

S

P

O

I

L

E

R

S

P

A

C

E

With the help of Nick Wedd's insight, the proof can be completed. Taking the bowls as numbered from -M to M where M = (N-1)/2, the variance increases by 2/N in each step, as long as bowls M and -M are never chosen. And since I proved that no balls will do that, and the variance is bounded above, the process must end.

Department of Mathematics http://www.math.ubc.ca/~israel University of British Columbia Vancouver, BC, Canada V6T 1Z2

Here's a puzzle based on this. How does one solve the following initial state?

Suppose all the bowls have one marble, except for one that has two and another nearby that has none, like this:

1 1 .... 1 1 0 1 2 1 1 .... 1 1

The only move available results in this:

1 1 .... 1 1 0 2 0 2 1 .... 1 1

From which is would seem this might as well happen next:

1 1 .... 1 1 1 0 1 2 1 .... 1 1

and now we are in the same situation we began with, shifted by one round the circle.

How can this be solved?

Bob H