Неравномерность распределений

Математическая задача

Проблема нерегулярности распределений , впервые сформулированная Гуго Штейнхаусом , является численной проблемой с удивительным результатом. Задача состоит в том, чтобы найти N чисел, все от 0 до 1, для которых выполняются следующие условия: ${\displaystyle x_{1},\ldots ,x_{N}}$

• Первые два числа должны быть в разных половинах (одно меньше 1/2, другое больше 1/2).
• Первые три числа должны быть в разных третях (одно меньше 1/3, одно между 1/3 и 2/3, одно больше 2/3).
• Первые 4 цифры должны находиться в разных четвертях.
• Первые 5 цифр должны быть в разных квинтах.
• и т. д.

Математически мы ищем последовательность действительных чисел

${\displaystyle x_{1},\ldots ,x_{N}}$

такой, что для каждого n  ∈ {1, ...,  N } и каждого k  ∈ {1, ...,  n } существует некоторый i  ∈ {1, ...,  k } такой, что

${\displaystyle {\frac {k-1}{n}}\leq x_{i}<{\frac {k}{n}}.}$

Решение

Удивительный результат заключается в том, что решение существует до N  = 17, но начиная с N  = 18 и выше оно невозможно. Возможное решение для N  ≤ 17 показано диаграммой справа; численно оно выглядит следующим образом:

Возможное решение для N  = 17 показано схематически. В каждой строке n есть n «виноградных лоз», которые все находятся в разных n ^th s. Например, глядя на строку 5, можно увидеть, что 0 <  x ₁  < 1/5 <  x ₅  < 2/5 <  x ₃  < 3/5 <  x ₄  < 4/5 <  x ₂  < 1. Числовые значения напечатаны в тексте статьи.

${\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}}}$

В этом примере, если рассмотреть первые 5 чисел, то мы имеем

${\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.}$

Мечислав Вармус пришел к выводу, что 768 (1536, если считать симметричные решения отдельно) различных наборов интервалов удовлетворяют условиям для N = 17.

Ссылки

• Г. Штейнхаус, Сто задач по элементарной математике , Basic Books , Нью-Йорк, 1964, стр. 12
• Berlekamp, ​​ER ; Graham, RL (1970). "Нерегулярности в распределениях конечных последовательностей". Journal of Number Theory . 2 (2): 152–161. Bibcode :1970JNT.....2..152B. doi : 10.1016/0022-314X(70)90015-6 . MR  0269605.
• М. Уормус, «Дополнительное примечание о нерегулярностях распределений», Журнал теории чисел 8, 260–263, 1976.