Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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...
share|improve this question
2  
What is the precise meaning of "as dispersed as possible"? –  mjqxxxx Jan 21 '11 at 3:48
    
Perhaps average distance between adjacent $1$s? –  Yuval Filmus Jan 21 '11 at 3:50
    
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. –  apalopohapa Jan 21 '11 at 4:26
    
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|$. –  Yuval Filmus Jan 21 '11 at 4:47
add comment

1 Answer 1

up vote 3 down vote accepted

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

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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