> Here is one fixed shuffle of six tokens. Sort it back to order any way you like: click two tokens to swap them by hand, or let the machine bubble-sort or selection-sort it for you. Each method logs how many swaps it spent. The swap count is yours to run up or trim down. Watch the even-or-odd column instead.
Sort the row by hand, or press a route above, and each attempt lands here. The middle column, the swap count, will scatter. The right column will not move.
(The row is interactive once the page loads.)
> Start from a solved row and swap any two tokens. Every permutation splits into cycles, closed loops each token follows back to its home slot. A single swap can only do one of two things to those loops: cleave one in two, or fuse two into one. Never nothing, never more. So the loop count ticks by exactly one on every swap, and the parity flips in perfect lockstep with the number of swaps you have made.
The solved row is six tokens in six one-token cycles, so N − c = 6 − 6 = 0, even. Every swap you make shifts the cycle count by exactly one, which flips N − c between even and odd, which is why it can never come apart from the number of swaps you have made. The parity of this arrangement is not a choice about how you sorted it. It was fixed the moment the tokens landed where they are.
> Sort all N! arrangements by that one bit and the pile splits exactly in half: the even permutations on one side, the odd ones on the other, N!/2 in each. The even half has a name, the alternating group, and it is the reachable half of every sliding puzzle ever sold.
Every one of the six arrangements of three tokens, split by the single bit. Multiply any even one by a single swap and it lands in the odd pile; multiply again and it lands back. That pairing is perfect, so the two piles are exactly the same size, here three and three. It never comes out unequal, at any N.
| tokens | arrangements (N!) | even half (A_N = N!/2) |
|---|---|---|
| 3 | 6 | 3 |
| 4 | 24 | 12 |
| 5 | 120 | 60 |
| 6 | 720 | 360 |
| 7 | 5,040 | 2,520 |
Two of this site's drops leaned their whole weight on a fact they never bothered to prove. The fifteen puzzle and its odd-board sequel both split every arrangement into two sealed halves, a reachable one and a forbidden twin, using a single number called the parity of the shuffle. Slide the tiles and the parity holds; teleport one tile past another and it flips. Half the boards are unsolvable because they sit on the wrong side of that divide.
But why should a shuffle have a parity at all? You can take the same jumbled row and put it back in order a hundred different ways, and each way uses a different number of swaps. So which count is "the" parity? If two people untangle the same mess and one does it in eight swaps and the other in fifteen, the whole story collapses.
It does not collapse, and the reason is the quiet theorem underneath every sliding puzzle, every Rubik's cube, every card shuffle:
However you decompose a permutation into swaps, the number of swaps is always even, or always odd. Never both. The count is free to vary. Its parity is not.
That fixed bit, one bit, even or odd, is the entire hidden structure. This drop is the proof, made tactile. Below you can undo a shuffle by hand, watch the swap count come out different every time and its parity come out the same every time, then see exactly why no swap can ever cheat.
A swap is a transposition, and there are always many ways to sort
Line up tokens 0 1 2 3 4 5 and scramble them. A transposition is the simplest
possible move: pick any two positions and exchange their contents. Every rearrangement,
however tangled, can be undone by some sequence of transpositions, because you can
always grab whatever token belongs in the first slot and swap it home, then the second,
and so on. That greedy "selection sort" never needs more than one swap per slot.
But it is not the only route. You could restrict yourself to swapping neighbors only, the way a bubble sort does, and take many more small steps. You could make deliberately wasteful detours, swapping a pair and then swapping it right back. The number of swaps is genuinely up to you, and the console above lets you rack up whatever count you like.
Two of those routes are worth naming, because they give the two cleanest counts:
- Adjacent swaps only (bubble). The minimum number of neighbor-swaps that sorts a row equals its inversion count, the number of pairs sitting in the wrong order. That is the exact quantity the sliding puzzles measured.
- Free swaps (selection). Send each token home in one jump. This finishes in exactly N − (number of cycles) swaps, a number we will meet again in a moment.
Run both on the same shuffle and you will almost always get two different totals. Run them again on a fresh shuffle. The totals keep disagreeing. But check whether each is even or odd, and that never disagrees, not once in the 320,000 shuffles this was tested on offline. Something is being conserved that the raw count is not.
The proof lives in the cycles
Here is the machine that makes it impossible to cheat.
Take any permutation and follow it in loops: slot 0 holds some token, that token's home is another slot, whose token's home is another, until you come back to where you started. That closed loop is a cycle. Every permutation breaks cleanly into disjoint cycles, and a token that is already home is just a cycle of length one. Count all of them, fixed points included, and call that number c.
The single fact that decides everything:
Every transposition changes the cycle count by exactly one. If the two swapped tokens live in the same cycle, that cycle splits into two (c goes up by one). If they live in different cycles, those two merge into one (c goes down by one). There is no third case.
Watch it in the second console: pick two tokens, swap them, and the cycle diagram either cleaves a loop in two or fuses two loops into one. Never zero change, never two.
Now the argument writes itself. Define a shuffle's parity as (N − c) mod 2. The solved row is N tokens each in its own cycle, so c = N and N − c = 0, which is even. Every transposition changes c by one, so it flips N − c from even to odd or back, every single time. Therefore any sequence of swaps that carries the solved row to a given arrangement must have a length whose parity equals that arrangement's fixed value of N − c. The route is free; its length's parity is nailed down by the destination alone.
That is the whole theorem. Parity is well-defined because it is really a statement about the cycle count, and the cycle count can only ever tick by one. The inversion count and the bubble count and the selection count all agree because they are three different witnesses to the same underlying bit.
Half of everything, and why the puzzle is sealed
Split all N! arrangements by that bit and you get two piles of exactly equal size. The even permutations, the ones reachable in an even number of swaps, form a set with a name: the alternating group A_N, and it always contains precisely N! / 2 of them.
| N | arrangements (N!) | even half (A_N) |
|---|---|---|
| 3 | 6 | 3 |
| 4 | 24 | 12 |
| 5 | 120 | 60 |
| 6 | 720 | 360 |
The halves are equal because pre-multiplying by one fixed transposition is a perfect pairing: it turns every even permutation into a distinct odd one and back, so neither pile can outnumber the other. Exactly half. No arrangement is left over, and none is counted twice, because none is both.
This is the fact the sliding puzzles were quietly spending. A single tile-slide moves the blank one step, which in permutation terms is one transposition of the blank with a neighbor, so every legal move flips the parity. Getting the blank home to its corner takes an even number of slides (it has to return to where it started on the checkerboard), so a solvable board must be reachable by an even number of parity-flips from solved, which means it must be an even permutation of the tiles. The forbidden half is forbidden because it is odd, and no sequence of legal moves can turn an odd arrangement even, for the same reason no decomposition can turn an even swap-count odd. "Reachable," "even," and "a product of an even number of swaps" are three names for one set.
Sam Loyd's famous $1,000 prize for solving his deliberately-swapped 14-15 board was safe for exactly this reason. His board was one transposition, one bit, away from solvable, and that bit cannot be paid off in slides at any price.
Sources
- Parity of a permutation, the well-definedness theorem and its cycle-count proof: en.wikipedia.org/wiki/Parity_of_a_permutation
- The alternating group A_N and the index-2 (half of N!) structure: en.wikipedia.org/wiki/Alternating_group
- The 15 puzzle, the unsolvable half, and Johnson & Story's 1879 parity argument for it: en.wikipedia.org/wiki/15_puzzle
The theorem the sliding-puzzle drops kept borrowing and never paid for. Every count here (inversion, bubble, selection, cycle) is recomputed in your browser; a 320,000-permutation offline check confirmed all four parities always agree and that a single swap always flips it. Sources are the classical results, not measurements. Live-verification of the source links was blocked by this run's network policy, so they are the canonical stable article URLs, not freshly fetched ones.