1
$\begingroup$

Moved from Math StackExchange: The Fifteen Puzzle consists of sliding square tiles numbered $1...15$ held in a $4\times4$ frame with one empty square. Any tile adjacent to the empty square can slide into it. The standard initial position is $$ \begin{array}{|c|c|c|} \hline 1 & 2&3 & 4 \\ \hline 5 & 6 & 7 & 8\\ \hline 9 & 10 & 11 & 12\\ \hline 13 & 14 & 15 \\ \hline \end{array} $$ The target position we would like to reach is: \begin{array}{|c|c|c|} \hline 15 & 14 & 13 & 12 \\ \hline 11 & 10 & 9 & 8\\ \hline 7 & 6 & 5 & 4\\ \hline 3 & 2 & 1 \\ \hline \end{array}

A state machine model of the puzzle has states consisting of a $4 \times 4$ matrix with $16$ entries consisting of the integers $1...15$ as well as one “empty” entry—like each of the two arrays above. The state transitions correspond to exchanging the empty square and an adjacent numbered tile. For example, an empty at position $(2,2)$ can exchange position with tile above it, namely, at position $(1,2)$

Using the method of finding invariants, how can you prove that there is no way to reach the target state starting from the initial state?

$\endgroup$

closed as off-topic by Deusovi, AJL, Cristian Marian, Spencerkatty, Gordon K Oct 11 '15 at 22:53

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "This question is off-topic as it appears to be a mathematics problem, as opposed to a mathematical puzzle. For more info, see "Are math-textbook-style problems on topic?" on meta." – Deusovi, AJL, Cristian Marian, Spencerkatty, Gordon K
If this question can be reworded to fit the rules in the help center, please edit the question.

  • 1
    $\begingroup$ This problem is taken word-for-word from these course notes. You should credit it. $\endgroup$ – xnor Oct 11 '15 at 8:15
  • $\begingroup$ Also, even though you were directed here from Math SE, I think this is standard enough combinatorics that's it's more a math problem than a puzzle. $\endgroup$ – xnor Oct 11 '15 at 8:17