KA-0097Parity arguments
5 points, difficulty 3 of 3Level 5–6about 165sThe numbers 1 to 10 stand in a row. A move swaps two neighbours. After exactly 45 moves, can the row be back in its starting order?
Hints
Take them one at a time. The first gives nothing away.
1A nudge
What does one swap change, whatever you swap?
2The strategy
Count the pairs of numbers standing in the wrong order relative to each other. Work out how one swap of neighbours changes that count - it is always by the same amount.
3The full solution
Swapping two neighbours changes the number of out-of-order pairs by exactly one, so the count flips between odd and even every move. It starts at zero.
Solution
The reliable way
Count how many pairs of numbers are in the wrong order relative to each other. A swap of two neighbours changes the order of exactly one pair, so this count goes up or down by exactly 1 every move - flipping between odd and even. In the starting row the count is 0, which is even. After 45 moves, an odd number, the count must be odd, so it cannot be 0. The row cannot be back where it started. The transferable idea: find a quantity that every move changes in the same predictable way, and the answer follows without trying anything.
The elegant way
Each neighbour swap flips the arrangement's parity, so an odd number of swaps can never return to the arrangement you started from.
Why this is on the test: It is the clearest case of a parity argument beating a search, and every distractor is a plausible reason that does not actually work.