The puzzle that cannot be solved
Tonight's idea
The fifteen puzzle is a 4 × 4 tray with tiles 1 to 15 and one gap. A move slides a neighbouring tile into the gap. Lift tiles 14 and 15 out of the solved tray and put them back swapped. Now slide your way home. Nobody ever has. Here is why nobody will.
Read the tiles row by row as one list, skipping the gap. An inversion is a pair in the wrong order: a bigger tile somewhere before a smaller one. Let \(T\) be the number of inversions plus the row number of the gap.
A sideways move changes neither the list nor the gap's row. A move up or down carries one tile past exactly three others in the list. Each of those three pairs flips between right and wrong order, so the inversions change by an odd number. The gap's row changes by 1. Odd plus odd is even.
Every move changes \(T\) by an even number. Even stays even, and odd stays odd.
Something no move can change is an invariant. Here it is whether \(T\) is odd or even.
Watch one: three trays
Solved: no inversions, gap in row 4, so \(T = 4\).
Slide 12 down. The list now ends 11, 13, 14, 15, 12. Tile 12 sits after three bigger tiles: 3 inversions. The gap is in row 3, so \(T = 6\). Still even.
Swap 14 and 15 instead: one inversion, gap in row 4, so \(T = 5\). Odd. Sliding can never join an odd tray to an even one, so this tray cannot be solved.
Your turn
- Count the inversions in each list: (a) 3, 1, 2, 5, 4; (b) 4, 3, 2, 1.
- Find \(T\) for each tray. Which one can be solved? For that one, give the moves.
(a)
(b)1 2 3 4 5 6 7 8 9 10 12 13 14 11 15 1 2 3 4 5 6 7 8 9 10 11 13 14 12 15 - In some tray, tile 9 moves up. In the list it jumps over three tiles: … 4, 12, 6, 9 … becomes … 9, 4, 12, 6 …. (a) By how much does the number of inversions change? (b) Name three tiles for the 9 to jump over that would change it by 3.
- All fifteen tiles are tipped out and put back in reverse order: 15, 14, 13, …, 1, reading row by row. (a) With the gap in the last place, can the tray be solved? (b) With the gap in the first place instead? You will need the number of pairs that can be chosen from 15 tiles.
Stretch: the eight puzzle
On a 3 × 3 tray, with tiles 1 to 8, a move up or down carries a tile past two others, not three. What is the invariant now? Does the gap's row still matter? Decide whether the tray reading 8, 7, 6, 5, 4, 3, 2, 1 with the gap last could be solved.
Answers
- (a) 3: the pairs (3, 1), (3, 2) and (5, 4). (b) 6: every one of the six pairs is in the wrong order.
- (a) The list ends 10, 12, 13, 14, 11, 15. Tile 11 sits after 12, 13 and 14: 3 inversions. Gap in row 3, so \(T = 6\), even. Solve it by sliding 11 up, then 15 left. (b) The list ends 11, 13, 14, 12, 15: 2 inversions. Gap in row 3, so \(T = 5\), odd. It cannot be solved, although it looks only a move or two from home.
- (a) Before the move only the pair (12, 9) is out of order. After it, (9, 4) and (9, 6) are. The count goes from 1 to 2: a change of \(+1\). (b) Any three tiles smaller than 9, such as 1, 2, 3. All three pairs go from right to wrong.
- In reverse order every pair is an inversion, and there are \(\dfrac{15 \times 14}{2} = 105\) pairs. (a) \(T = 105 + 4 = 109\), odd: impossible. (b) \(T = 105 + 1 = 106\), even, the same kind as the solved tray. The invariant does not stop it, and in fact it can be solved (see below).
Stretch. Two pairs flip, so the inversions change by \(-2\), 0 or \(+2\): always even. The invariant is whether the number of inversions alone is odd or even, and the gap's row is not needed. The reversed tray has \(\dfrac{8 \times 7}{2} = 28\) inversions, even like the solved tray, so nothing forbids it. A computer search of all \(9! = 362{,}880\) arrangements finds that exactly half, 181,440, can be reached from the solved tray: every arrangement that passes the test, this one included. The same holds for the fifteen puzzle: half of its 20,922,789,888,000 arrangements can be solved, the ones with \(T\) even.