problemdata       % Takes 5 *mandatory* arguments
        {computational-processes-2}             % latex-friendly label for the prob.
        {computational-processes}  % The topic(s) of the problem content.
        {}               % Source (if known)
        {S02 PS5} % Usage (list ones you are aware of).
        {Jack Kwok, S02}        % Last revision info (author, date).


\begin{problem} 
The \textbf{Fifteen Puzzle} consists of sliding square tiles numbered
$1,\dots,15$ held in a $4\times4$ frame with one empty square.  Any tile
adjacent to the empty square can slide into it.  The
\href{http://theory.lcs.mit.edu/classes/6.042/spring02/}{6.042 Icon} is
based on this puzzle.

The standard initial position is
\[\begin{array}{|c|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}\]
We would like to reach the target position (known in my youth as ``the
impossible'' --- ARM):
\[\begin{array}{|c|c|c|c|}
\hline 15 & 14 & 13 & 12\\
\hline 11 & 10 & 9 & 8\\
\hline7 & 6 & 5 & 4\\
\hline3 & 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,\dots,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, a empty at position $(2,2)$ can
exchange position with tile above it, namely, at position $(1,2)$:
\[\begin{array}{|c|c|c|c|}
\hline n_1 & n_2 & n_3 & n_4\\
\hline n_5 &  & n_6 & n_7\\
\hline n_8  & n_9 & n_{10} & n_{11}\\
\hline n_{12} & n_{13} & n_{14}  & n_{15}\\
\hline
\end{array} \longrightarrow
\begin{array}{|c|c|c|c|}
\hline n_1 &   & n_3 & n_4\\
\hline n_5 & n_2 & n_6 & n_7\\
\hline n_8  & n_9 & n_{10} & n_{11}\\
\hline n_{12} & n_{13} & n_{14}  & n_{15}\\
\hline
\end{array} 
\]

In this problem you will use the invariant method prove that starting
from the initial state, there is no way to reach the target state.

We begin by noting that a state can also be represented as a pair
consisting of two things:
\begin{enumerate}

\item a list of the numbers $1,\dots,15$ in the order in which they
appear---reading rows left-to-right from the top row down, ignoring the
empty square, and

\item the coordinates of the empty square---where the upper left
square has coordinates $(1,1)$, the lower right $(4,4)$.

\end{enumerate}

Let $L$ be such an ordered list of the numbers $1,\dots,15$.  A pair of
integers is an \emph{out-of-order pair} in $L$ when the first element of
the pair both comes \emph{earlier} in the list \emph{and is larger}, than
the second element of the pair.  For example, the list $1,2,4,5,3$ has two
out-of-order pairs: 4,3 and 5,3.  The increasing list $1,2\dots n$ has no
out-of-order pairs.

Representing a state, $S$, as the pair $(L, (i,j))$ described above,
define the \emph{parity} of $S$ to be the mod 2 sum of the number of
out-of-order pairs in $L$ and the row-number, $i$, of the empty
square.

\begin{problemparts}

\problempart Verify that the parity of the initial state and the parity of the
target state are different.

\solution{The parity of the initial state is $(0+4) \bmod 2 = 0$.
Parity of target is $((15 \cdot 14/ 2) + 4) \bmod 2 = 1$.}

\problempart Show that the parity of a state is invariant under transitions.
Conclude that ``the impossible'' is impossible to reach.

\solution{To show that the parity is constant, let us consider what
types of moves may affect the parity.  The only 4 moves we need to worry
about are the following:  a move to the left, a move to the right, a move
to the row above, or a move to the row below.  

Note that horizontal moves change nothing, and vertical moves both change
$i$ by 1, and move a tile three places forward or back in the list, $L$.
To consider how the parity is changed in this case, we need to consider
only the 3 pairs in $L$ that are between the tile's old and new position.
(The other pairs are not effected by the tile's move).  This reverses the
order of three pairs in $L$, changing the number of inversions by 3 or 1,
but always by an odd amount.

To confirm this last remark, note that if the 3 pairs were all out of
order or all in order before, the amount is changed by 3.  If two pairs
were out of order and 1 pair was in order or if one pair was out of order
and two were in order, this will change the amount by 1.  So the sum of
$i$ and the number of out-of-order pairs changes by an even amount (either
1+3 or 1+1), which implies that its parity remains the same.  Since the
initial state has parity 0 (even), all states reachable from the initial
state must have parity 0, so the target state with parity 1 can't be
reachable.}

\ppart (optional, extra credit) Show that if two states have the same
aprity, then there is a way to get from one to the other.

\end{problemparts}
\end{problem}

