An elegant proof that the pairity of a permutation is well-defined

Question

I want to explain to non-mathematicians a very nice proof that the 15-puzzle with 14 and 15 replaced is not solvable.

For that, one crucial argument is the fact that:

If we can write the same permutation as a product of transpositions in two different ways, then the pairity of the number of transpositions is the same.

I know a standrad induction proof to this statement, but it's quite boring, technical and can't be properly explained to "ordinary" people, as all other proofs I know.

I'm looking for a proof as elegant as one can find. Maybe a proof using coloring of some kind (it feels to me like there must be one), or visual graph theory, or binary arithmetic, etc.

I'm curious to hear your answers!

Answer 1

I took this from https://math.stackexchange.com/a/46476/256345

Basically, $\forall \sigma\in S_n$, write in two rows $$1, 2, \cdots, n$$ $$1, 2,\cdots, n$$ Now connect each $k$ in the top to $\sigma(k)$ in the bottom. Require that each curve intersection is simple, that is, no three curves intersect at one point, and no tangency, and finally, no self-intersection (which changes parity!)

Then define the parity of a permutation as the parity of intersections.

This is very geometric and easy to demonstrate. Now you only need to convince the audience that this is a well-defined parity, that is, it does not depend on how you draw the curves.

Step 1: Convince them that any two ways to draw the curves can be turned to each other through two of the three Reidemeister moves. This should be rather intuitive if you draw two diagrams, one with wavy wavy curves, another with straight curves, and ask them to mentally "taut" the wavy curves to the straight curves.

Step 2: Show each of the two Reidemeister moves does not change parity.

Answer 2

The essential point is the following: Multiplying a permutation $\sigma\in {\cal S}_n$ with a transposition $(x,y)$ changes the parity of the number of cycles: The permutation $\sigma':=(x,y)\circ\sigma$ has one cycle more or one cycle less less than $\sigma$.

Proof. Assume that $x\ne y$ are elements of $[n]$, and ${\bf a}$, ${\bf b}$ are disjoint words (maybe empty) over the alphabet $[n]$ not containing $x$ or $y$. Then $$(x,y)\circ(x{\bf a}y{\bf b})= (x{\bf a})\circ(y{\bf b})\ .$$ Since $(x,y)^2={\rm id}$ we then also have $$(x,y)\circ\bigl((x{\bf a})\circ(y{\bf b})\bigr)=(x{\bf a}y{\bf b})\ .\qquad\square$$