Irregularity of distributions

The irregularity of distributions problem, stated first by Hugo Steinhaus, is a numerical problem with a surprising result. The problem is to find N numbers, x_1,\ldots,x_N, all between 0 and 1, for which the following conditions hold:

Mathematically, we are looking for a sequence of real numbers

x_1,\ldots,x_N

such that for every n ∈ {1, ..., N} and every k ∈ {1, ..., n} there is some i ∈ {1, ..., n} such that

\frac{k-1}{n} \leq x_i < \frac{k}{n}.

Solution

The surprising result is that there is a solution up to N = 17, but starting at N = 18 and above it is impossible. A possible solution for N ≤ 17 is shown diagrammatically on the right; numerically it is as follows:

A possible solution for N = 17 shown diagrammatically. In each row n, there are n “vines” which are all in different nths. For example, looking at row 5, it can be seen that 0 < x1 < 1/5 < x5 < 2/5 < x3 < 3/5 < x4 < 4/5 < x2 < 1. The numerical values are printed in the article text.
\begin{align} x_{1} & = 0.029 \\ x_{2} & = 0.971 \\ x_{3} & = 0.423 \\ x_{4} & = 0.71 \\ x_{5} & = 0.27 \\ x_{6} & = 0.542 \\ x_{7} & = 0.852 \\ x_{8} & = 0.172 \\ x_{9} & = 0.62 \\ x_{10} & = 0.355 \\ x_{11} & = 0.774 \\ x_{12} & = 0.114 \\ x_{13} & = 0.485 \\ x_{14} & = 0.926 \\ x_{15} & = 0.207 \\ x_{16} & = 0.677 \\ x_{17} & = 0.297 \end{align}

In this example, considering for instance the first 5 numbers, we have

0 < x_1 < \frac{1}{5} < x_5 < \frac{2}{5} < x_3 < \frac{3}{5} < x_4 < \frac{4}{5} < x_2 < 1.

References