Christopher Janjigian

Outreach module (grades 9-12)

Fifteen Puzzle Explorer

Part 2: The power of parity

Module Sequence

1. Play the puzzle 2. Parity 3. Permutations 4. Length and parity 5. Solvability 6. Solution guide

Loyd's challenge

In the late 1870s, Samuel Loyd popularized the fifteen puzzle: a 4-by-4 board with tiles numbered \(1\) through \(15\) and one empty space. A legal move slides a single tile into the empty space.

Loyd's challenge was to start from the solved board, interchange the tiles \(14\) and \(15\), and ask whether the new board could be solved using only legal moves. He offered a cash prize for a solution, and the puzzle spread widely. The question for this page is why that challenge has no solution.

Two 15-puzzle boards are shown. The goal board has rows 1, 2, 3, 4; 5, 6, 7, 8; 9, 10, 11, 12; and 13, 14, 15, blank. Loyd's challenge keeps the first three rows the same and changes the last row to 13, 15, 14, blank.

Goal board
Loyd's challenge

1. The power of parity

A standard way to prove that something cannot happen is to find a quantity that the allowed operations do not change. Such a quantity is called an invariant. Parity is often the simplest useful invariant: instead of tracking an exact number, you only track whether it is even or odd. If one situation has even parity and another has odd parity, and the allowed moves do not change the parity, then no allowed sequence of moves can connect them.

To see how this works, start with a party of five people. We draw one point for each person, and we draw a line whenever two people know each other. The picture below is one possible five-person party.

Claim

In any party with five people, at least one person knows an even number of people. Try to explain why, and then ask whether the same statement is true for any odd-sized party.

Five-person party graph Five people are shown as points connected by lines whenever two people know each other. The numbers 2, 3, 3, 2, and 0 indicate how many people each person knows. A B C D E 2 3 3 2 0
One five-person party drawn as a graph.
Reasoning

Let \(n_i\) be the number of acquaintances of person \(i\). If you add up all the \(n_i\), every line is counted twice, once from each endpoint. So the total \(n_1+n_2+n_3+n_4+n_5\) is even.

If all five people knew an odd number of people, then \(n_1+n_2+n_3+n_4+n_5\) would be a sum of five odd numbers, hence odd. That is impossible.

So at least one person must know an even number of people. The same proof works for any odd number of people.

2. Back to the puzzle

The fifteen puzzle asks the same kind of question. We want to find a notion of parity attached to a board state and show that legal slides preserve it.

If the solved board and Loyd's challenge have different parity, then Loyd's challenge cannot be solved.

The next step is to represent a board state in a way that is easier to work with. A board state is a rearrangement of the numbers, and reshuffling numbers in this way is called permuting them, so we will study the structure of permutations.

1: Play the puzzle

Return to the board and try more starting positions.

3: Permutations

Rewrite board states as permutations and learn the notation.