сортировка транспозициями

[maxal]

Напомню, что транспозицией называется перестановка переставляющая местами два элемента. Таким образом, на множестве $\{1,2,\dots,n\}$ существует $\frac{n(n-1)}2$ различных транспозиций.

Докажите, что для любую перестановку множества $\{1,2,\dots,n\}$ той же чётности что и $\frac{n(n-1)}2$ можно отсортировать к тождественной, применив (в некотором порядке) каждую из $\frac{n(n-1)}2$ транспозиций ровно по одному разу.

[iifat]

Я чего-то не понял в условии? Никак не могу доказать, что перестановку $\{1,2\}$ можно привести к тождественной, применив в любом порядке каждую из одной перестановки.

[maxal]

iifat, конечно не любую, а любую чётную. Спасибо за бдительность. Исправлено.

[nnosipov]

Число $n(n-1)/2$ может быть как четным, так и нечетным. "Любую подстановку, четность которой совпадает с четностью $n(n-1)/2$, можно ..." --- видимо, такая формулировка должна быть.

[maxal]

nnosipov, конечно! Исправил. Теперь вроде все чисто.