И это — переход из одной перестановки в другую на наименьшее возможное расстояние (корень из двух).

Так вот — выпуклый многогранник, вершины которого это всевозможные перестановки вектора (1,2,...,n), называется пермутоэдром, или перестановочным многогранником. Очевидно, что все эти точки лежат в одной плоскости "сумма координат равна 1+...+n", и на одной сфере "сумма квадратов координат равна 1^2+...+n^2".

А синусоиды, что всплыли выше, оказываются связанными с дугами большого круга — но это тот момент, когда я хочу сделать паузу до следующего раза.

Раз уж всё равно сделана пауза — давайте я расскажу пару коротких баек.

Первая — более стандартная, но кажется, не совсем общеизвестная, про чётности перестановок.

Обычно определение чётности перестановки f даётся как чётность числа беспорядков (т.е. пар i<j, для которых f(i)>f(j)) — после чего проверяется, что это же чётность числа транспозиций, в произведение которых f раскладывается.

Что можно проверить напрямую (взять транспозицию, посмотреть, какие беспорядки она добавляет, какие убирает, и что чётность в итоге всегда меняется), но это немного муторно.

А гораздо проще будет сначала рассмотреть разложение f в произведение не абы каких транспозиций, а только транспозиций соседних элементов (i,i+1).
Тогда умножение на такую транспозицию меняет число беспорядков ровно на 1 — как раз на пару (i,i+1).

И поэтому чётность числа беспорядков у f совпадает с чётностью числу транспозиций вида (i,i+1), в произведение которых f раскладывается.

Значит, есть отображение sign(f) из перестановок в {1,-1}, которое корректно определено (ибо определение через беспорядки) и при этом гомоморфизм (ибо определение через чётность числа сомножителей).

Остаётся проверить, что любая транспозиция нечётна — что проще всего увидеть, сказав, что любая транспозиция сопряжена транспозиции (1,2):
(i,j)=g*(1,2)*g^{-1},
где g — любая перестановка, такая, что g(i)=1, g(j)=2.

(Кстати: вот понимание, что "сопряжение отображением g это просто замена координат y=g(x)", каюсь, до меня в своё время тоже довольно медленно доходило...)

Ну а в g и в g^{-1} чётность числа транспозиций (i,i+1) одинаковая — так что всего число таких транспозиций в (i,j) нечётно. (Да, конечно, можно просто посчитать беспорядки. Но хотелось рассуждения "без единой выкладки".)

Всё!

===
Вторая байка — про теорию вероятностей. Вот тут — https://avva.livejournal.com/3242116.html , https://blog.tanyakhovanova.com/2019/11/my-new-favorite-probability-puzzle/ — обсуждается такая задача. Пусть два игрока, Алиса и Боб, одновременно и независимо играют на деньги с одинаковой начальной суммой в $100, каждую минуту ставя по доллару. Но у Алисы вероятность выигрыша 51%, а у Боба 49%. Известно, что в итоге оба разорились (остались без денег и прекратили игру); _при этом условии_ про кого более вероятно, что он разорился первым?

Spoiler alert: я собираюсь обсуждать (неожиданный) ответ, если вдруг вы эту задачу не решали, она очень стоит того, чтобы над ней подумать.

Ответ — равновероятно. Более того, оказывается, что процесс игры Алисы _при условии_ того, что она в конце концов разоряется, такой же, как процесс игры Боба. И это, мне кажется, удивительно!

Давайте посмотрим, как этот процесс устроен. Для начала найдём вероятности r_n того, что Алиса разоряется, имея в начале n долларов.

r_0=1 (ибо тут уже всё).
Достаточно естественно (хотя это и надо доказывать — но мы в это поверим), что r_n<1 при всех n>0: шанс не разориться (а получить асимптотически-линейный рост) у Алисы есть, если у неё ещё осталось, на что играть.

Теперь, если Алиса начинает играть с n долларами, её шанс разориться складывается из вероятности выиграть первую ставку и разориться после того, и проиграть и разориться после того:
r_n = p r_{n+1} + q r_{n-1},
где p=0.51 — её вероятность выигрыша.

Это — линейное рекуррентное соотношение, и его решениями оказываются линейные комбинации геометрических прогрессий со знаменателями — корнями характеристического уравнения*; в данном случае — это уравнение px^2-x+q=0.

*) когда кратных корней нет; иначе там (в общей науке линейных рекуррентных соотношений) появляются "квазимногочлены" — произведения многочленов на экспоненты.

Один корень у этого уравнения — 1, отвечающего решению-константе. Собственно, если бы p было меньше 1/2 (а мы ещё нигде p>1/2 не использовали), то мы этот корень и должны увидеть: вероятность разорения в этом случае — тождественная единица.

А второй (например, из теоремы Виета, чтобы долго не считать) x=q/p.

Кстати, в качестве ответвления: случай честной монеты, p=q=1/2, это как раз случай кратного корня, и решения уравнения r_{n+1}-2r_n+r_{n-1}=0 это в точности все арифметические прогрессии. Но поскольку r_n это вероятности, такая арифметическая прогрессия остаётся на [0,1] при всех n>0, а ограниченная арифметическая прогрессия — константа. Значит, r_n=1 — игрок с честной монетой тоже разоряется с вероятностью 1 ("случайное блуждание на прямой возвратно"), и такое рассуждение — один из способов это увидеть.

В нашем случае p>1/2 — не очень сложно поверить, что r_n будет стремиться к 0 с ростом n: чем больше у Алисы начальный запас денег, тем меньше её шанс разориться.

Но раз r_n=a*1+b*x^n, то a=0, а из r_0=1 тогда следует b=1.
Так что вероятность разорения Алисы — это просто геометрическая прогрессия: r_n=x^n=(q/p)^n.

Осталось понять, как при условии "Алиса разорилась" выглядит процесс её игры. Если в какой-то момент у неё n долларов, то шансы перейти в (n+1) и в (n-1) за один шаг равны соответственно p*r_{n+1}/r_n и q*r_{n-1}/r_n (а то, что их сумма равна 1 — это и было наше уравнение).

Но у нас геометрическая прогрессия — поэтому r_{n+1}/r_n=x=q/p, а r_{n-1}/r_n=p/q.