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... 
  • 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$ .