А ещё можно посмотреть на то, как будут устроены графики перестановок (при фиксированном моменте времени, какой чемодан на каком месте стоит). Вот, к примеру (опять из той же статьи) график перестановки, которая наблюдается после половины всех операций:
Явно проглядывает круг — но при этом плотность ближе к краям, так, как если бы это была равномерная мера на сфере в трёхмерном пространстве (x,y,z) — которую спроецировали на плоскость (x,y).
А что будет в другие моменты времени? Естественно считать параметром t долю от общего числа N выполненных операций; и вот картинка опять же из их работы —
Начальный и конечный момент времени это начальное и итоговое расположение чемоданов, у которых графики — прямые. А в промежуточные моменты времени видны эллипсы — а синим показаны полученные уже тогда (11 лет назад, препринт ещё 2006-го — https://arxiv.org/abs/math/0609538v1 ) оценки.
Математические байки
Правда ведь, напоминает синусоиды?
Собственно — вот гипотезы из той работы, как раз это и утверждающие:
Кстати — если рисовать гистограмму того, сколько операций было произведено в такое-то время в таком-то месте, то тоже получается красивая картина:
Но ещё интересная история тут — это появление перестановочного многогранника, или пермутоэдра. А именно, давайте посмотрим на обратное отображение после m операций, то есть на набор "на каком месте стоит первый чемодан, на каком второй, ..., как каком n-й".
Это — перестановка, так что в этом векторе каждое из чисел 1,2,...,n встречается по одному разу. При этом одна операция меняет два соседних чемодана — так что какие-то два числа m и m+1 в этом векторе поменяются местами.
Это — перестановка, так что в этом векторе каждое из чисел 1,2,...,n встречается по одному разу. При этом одна операция меняет два соседних чемодана — так что какие-то два числа m и m+1 в этом векторе поменяются местами.
И это — переход из одной перестановки в другую на наименьшее возможное расстояние (корень из двух).
Так вот — выпуклый многогранник, вершины которого это всевозможные перестановки вектора (1,2,...,n), называется пермутоэдром, или перестановочным многогранником. Очевидно, что все эти точки лежат в одной плоскости "сумма координат равна 1+...+n", и на одной сфере "сумма квадратов координат равна 1^2+...+n^2".
Так вот — выпуклый многогранник, вершины которого это всевозможные перестановки вектора (1,2,...,n), называется пермутоэдром, или перестановочным многогранником. Очевидно, что все эти точки лежат в одной плоскости "сумма координат равна 1+...+n", и на одной сфере "сумма квадратов координат равна 1^2+...+n^2".
А синусоиды, что всплыли выше, оказываются связанными с дугами большого круга — но это тот момент, когда я хочу сделать паузу до следующего раза.
Раз уж всё равно сделана пауза — давайте я расскажу пару коротких баек.