# Spread evenly $x$ black balls among a total of $2^n$ balls

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"? – 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

## 1 Answer

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

-
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 17, "mathjax_display_tex": 2, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.8913902640342712, "perplexity_flag": "middle"}