1
$\begingroup$

Suppose you want to line up $2^n$ balls of which $x$ are black the rest are white. Find a general method to do this so that the black balls are as dispersed as possible, assuming that the pattern will repeat itself ad infinitum. The solution can be in closed form, iterative, or algorithmic.

For example, if $n=3$, where $0$ is a white ball and $1$ is a black ball, a solution is:

x=0: 00000000...
x=1: 10000000...
x=2: 10001000...
x=3: 10010010...
x=4: 10101010...
x=5: 01101101...
x=6: 01110111...
x=7: 01111111...
x=8: 11111111...
  • 2
    What is the precise meaning of "as dispersed as possible"?2011-01-21
  • 0
    Perhaps average distance between adjacent $1$s?2011-01-21
  • 0
    For now let me define dispersion as follows: If 0 means move to the left a distance of d0 and 1 means move to the right d1, and d0 and d1 are chosen so that after moving 2^n-x times to the left and x times to the right you end up in the same position, minimal dispersion is the same as minimizing maximum excursion from origin over time, if the pattern is repeated endlessly.2011-01-21
  • 0
    I.e. if the sequence is $s_i$ then we want to minimize $\max_{m \geq 0} \left| \sum_{k=0}^m (2^n s_k - x) \right|$.2011-01-21

1 Answers 1

3

Let $\theta = x/2^n$. For each $m$, put a (black) ball at $$\min \{ k \in \mathbb{N} : k\theta \geq m \}.$$ In other words, look at the sequence $\lfloor k \theta \rfloor$, and put a ball in each position where the sequence increases.

For example, if $n=3$ and $x = 3$ then $\theta = 3/8$ and the sequence of floors is $$0, 0, 0, 1, 1, 1, 2, 2, 3, 3, 3, 4, 4, 4, 5, 5, \ldots,$$ and so the sequence of balls is $10010010\ldots$ .