Irregularities of distribution

☆ Save On Wikipedia ↗

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 , … , x N {\displaystyle x_{1},\ldots ,x_{N}} {\displaystyle x_{1},\ldots ,x_{N}}, all between 0 and 1, for which the following conditions hold:

  • The first two numbers must be in different halves (one less than 1/2, one greater than 1/2).
  • The first 3 numbers must be in different thirds (one less than 1/3, one between 1/3 and 2/3, one greater than 2/3).
  • The first 4 numbers must be in different fourths.
  • The first 5 numbers must be in different fifths.
  • etc.

Mathematically, we are looking for a sequence of real numbers

x 1 , … , x N {\displaystyle x_{1},\ldots ,x_{N}} {\displaystyle x_{1},\ldots ,x_{N}}

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

k − 1 n ≤ x i < k n . {\displaystyle {\frac {k-1}{n}}\leq x_{i}<{\frac {k}{n}}.} {\displaystyle {\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.
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.777 x 12 = 0.1 x 13 = 0.485 x 14 = 0.905 x 15 = 0.218 x 16 = 0.667 x 17 = 0.324 {\displaystyle {\begin{aligned}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.777\\x_{12}&=0.1\\x_{13}&=0.485\\x_{14}&=0.905\\x_{15}&=0.218\\x_{16}&=0.667\\x_{17}&=0.324\end{aligned}}} {\displaystyle {\begin{aligned}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.777\\x_{12}&=0.1\\x_{13}&=0.485\\x_{14}&=0.905\\x_{15}&=0.218\\x_{16}&=0.667\\x_{17}&=0.324\end{aligned}}}

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

0 < x 1 < 1 5 < x 5 < 2 5 < x 3 < 3 5 < x 4 < 4 5 < x 2 < 1. {\displaystyle 0<x_{1}<{\frac {1}{5}}<x_{5}<{\frac {2}{5}}<x_{3}<{\frac {3}{5}}<x_{4}<{\frac {4}{5}}<x_{2}<1.} {\displaystyle 0<x_{1}<{\frac {1}{5}}<x_{5}<{\frac {2}{5}}<x_{3}<{\frac {3}{5}}<x_{4}<{\frac {4}{5}}<x_{2}<1.}

Mieczysław Warmus concluded that 768 (1536, counting symmetric solutions separately) distinct sets of intervals satisfy the conditions for N = 17.

References