Irregularity of Distributions

The Irregularity of Distributions problem is a numerical problem first stated by the Polish mathematician Hugo Steinhaus. It's about finding a finite sequence of numbers $a_1, a_2, \dots, a_n$ between $0$ and $1$ such that $a_1$ and $a_2$ are in different halves of the interval $[0,1)$, $a_1$, $a_2$, $a_3$ are in different thirds of the same interval, $a_1$ to $a_4$ are in different fourths, and so on. (A video explanation of the problem can be found here. And if you want to try it yourself first, you might want to look here.)

As an example, consider the following sequence: \[ \color{blue}{a_1 = \frac7{24} \approx 0.292}\quad\quad \color{red}{a_2 = \frac78 = 0.875}\quad\quad \color{green}{a_3 = \frac7{12} \approx 0.583}\quad\quad \color{orange}{a_4 = \frac18 = 0.125} \] $\color{blue}{a_1}$ and $\color{red}{a_2}$ are in different halves, i.e. on different sides of $\frac12$:

$\color{blue}{a_1}$ and $\color{red}{a_2}$ and $\color{green}{a_3}$ are in different thirds:

And all four numbers are in different fourths:

The question now is: How far can you go? What's the longest sequence obeying these rules one can construct? This question has a surprising answer...

Interval Arithmetic

The first thing to note is that this is not really about numbers, but about intervals: Say, you want to construct such a sequence of length seven. Each of your seven numbers must reside in one of the following seven intervals (painted in seven different colors). And each number must be in a different interval, of course.

Now, six of your seven numbers must also be distributed over the six intervals you get if you divide the whole line into sixths. Let's suppose you want these to be the first six of your seven numbers.

So, in the picture above, the first number must be located somewhere in both green intervals. The second number must be in both purplish intervals, and so on. In other words, you need to pair these intervals and look at their intersections:

If you want to find a solution with seven numbers (and if you want the last number to be in the last seventh, as we decided above), then each of the first six numbers must fit into one of the six intersections above. Specifically, one number must fit into the sixth intervall on the right, which is already quite small.

But five of your six numbers must also fit into five different fifths. And you can't just pick any five of them. Suppose, for example, you wanted to leave out the fifth number (the one in the red interval). You'd be confronted with this situation:

If you now look at the intersections, you get this:

The intersection of the two aquamarine intervals is the empty set, so there's no way to position five numbers according to the rules of the game...

But of course, we didn't need to leave out the red interval further above. We could have picked another selection of five of the six numbers, for example by leaving out one of the two numbers in the middle. That would have worked. (Try it!)

An Algorithm

This might have given you an idea for how to solve the problem systematically: you work backwards. To find a sequence with, say, ten elements, start with ten intervals $[0,\frac1{10}), [\frac2{10},\frac3{10}), \dots, [\frac9{10},1)$. Select nine of these ten intervals and pair and intersect them with the intervals $[0, \frac19), [\frac19, \frac29), \dots, [\frac89, 1)$. If none of the intersections is empty, continue by again removing one interval and pairing with eighths. Do this until you end up with only one (non-empty) interval.

If you're stuck at some point, go back and reconsider your previous decision, i.e. pick another interval to leave out and try again. That's a typical backtracking algorithm which is not hard to implement. You might want to try it yourself (or have a look at the JavaScript source code of this page if you're lazy).

And below you can watch the algorithm in action or just check out a couple of possible solutions.

You will probably have noticed that the algorithm easily finds solutions up to $n=17$ but that it has to give up for $n=18$. Once you have convinced yourself that the algorithm is working correctly and that it finds a solution if there is one, it becomes apparent that there is no solution to this problem for $n=18$ or larger values. Isn't that strange?

Well, the short justification for this is that $18$ has too many divisors. To flesh out the details - in case you're not convinced after watching how the computer failed - requires some technicalities, but it's not hard. The first person to give a proof (without using a computer, by the way) was the Polish mathematician Mieczysław Warmus.