Let us suppose we have slots $n$ slots $1, \ldots, n$ and $k$ pebbles, each of which is initially placed in some slot. Now the pebbles want to space themselves out as evenly as possible, and so they do the following. At each time step $t$, each pebble moves to the slot closest to the halfway point between its neighboring pebbles; if there is a tie, it chooses the slot to the left. The leftmost and rightmost pebbles apply the same procedure, but imagining that there are slots numbered $0$ and $n+1$ with pebbles in them.

Formally, numbering the pebbles $1, \ldots, k$ from left to right, and letting $x_i(t)$ be the slot of the $i$'th pebble at time t, we have $$ x_i(t+1) = \lfloor \frac{x_{i-1}(t)+x_{i+1}(t)}{2} \rfloor, i = 2, \ldots, k-1$$ $\lfloor \cdot \rfloor$ rounds down to the closest integer. Similarly, $$ x_1(t+1) = \lfloor (1/2) x_2(t) \rfloor, x_k(t+1) = \lfloor \frac{x_{k-1}(t) + (n+1)}{2} \rfloor.$$

Now the fixed point of this procedure is the arrangement in which $x_{i+1} - x_i$ and $x_i - x_{i-1}$ differ by $1$. My question: is it true that this fixed point is reached by the above procedure after sufficiently many iterations?

Why I care: no concrete reason really, I am just reading about finite difference methods, and this seemed like a simple problem connected with some of the things which are confusing me.

  • $\begingroup$ You're missing a factor of 1/2 in your expression for $x_1(t+1)$. $\endgroup$ – mjqxxxx Jan 21 '11 at 7:40
  • $\begingroup$ @mjqxxxx - thanks, fixed now. $\endgroup$ – angela o. Jan 21 '11 at 12:38

Start with 8 slots, and pebbles at 3 and 5. The pebbles go to slots 2 and 6, and then back to 3 and 5, indefinitely.

Update Even simpler: 5 slots. $(1,4) \rightarrow (2,3) \rightarrow (1,4)$.


You have a total number of unoccupied spaces $n-k$, divided into $k+1$ intervals between pebbles. Your procedure looks at adjacent pairs of empty intervals and tries to make them more similar. If they differ by more than one, the larger of the two intervals will be reduced and the smaller increased so that their difference becomes zero or one. If they differ by zero, they will be left alone. If they differ by one, they will be swapped if necessary so that the larger of the two intervals is on the right. In short, the only steady states will be those where each interval is the same size or one greater than its neighboring interval on the left -- there are many of these. If the update rules are applied one pebble at a time, a steady state will always be reached, because the total discrepancy, $D \equiv \sum_{i=1}^{k} |x_{i+1} - 2x_i + x_{i-1} - 1/2|$, decreases with each move. But if the update rules are applied simultaneously, it is less clear that you must reach a steady state. I think that you still must, but I don't have as simple a proof.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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