\problemdata                                                             
        {3x3 Puzzle} % latex-friendly label for the prob.
        {State Machines} % The topic(s) of the problem content.  
        {?} % Source (if known)                                          
        {S01 Tutorial 5, 4} % Usage (list ones you are aware of). 
        {Tina Wang, S02} % Last revision info (author, date).   
                                                                         
                                                                         
\begin{problem}           
Over the weekend, your 6.042 TAs came across the following puzzle: a
$3 \times 3$ grid of squares, where each square contains one of the
digits in the set $\set{1, 2, 3, 4, 5, 6, 7, 8, 9}$, each digit
appearing exactly once in the puzzle.  Each row can be rotated right
or left and each column can be rotated up or down.  The effects of
such rotations are demonstrated in the following figure.

\begin{figure}[htbp]
  \begin{center}
    \leavevmode

\[
\begin{array}{|c|c|c|}
\hline
2 & 3 & 6 \\ \hline
7 & 8 & 9 \\ \hline
5 & 4 & 1 \\ \hline
\end{array}
\rightarrow
\begin{array}{|c|c|c|}
\hline
5 & 3 & 6 \\ \hline
2 & 8 & 9 \\ \hline
7 & 4 & 1 \\ \hline
\end{array}
\rightarrow
\begin{array}{|c|c|c|}
\hline
5 & 3 & 6 \\ \hline
8 & 9 & 2 \\ \hline
7 & 4 & 1 \\ \hline
\end{array}
\]

  \end{center}
  \caption{Examples of puzzle row and column rotations.}
  \label{fig:roteg}
\end{figure}

The first picture shows the initial configuration of the puzzle.  The
leftmost column is then rotated downward to give the middle picture.
The $2$ and $7$ move down and the $5$ rotates back up to the top.
Then, the middle row is rotated leftward to produce the final picture.
The $8$ and $9$ move left and the $2$ rotates back around to the
right.

Since discovering the puzzle, your 6.042 TAs have spent hours trying
to obtain the following configuration, starting of course from the
initial configuration of Figure~\ref{fig:roteg} and using legal row
and column rotations.

\[
\begin{array}{|c|c|c|}
\hline
1 & 2 & 3 \\ \hline
4 & 5 & 6 \\ \hline
7 & 8 & 9 \\ \hline
\end{array}
\]

Sad to say, your 6.042 TAs have failed miserably.

Based on prior experience with puzzles, the 6.042 students believe
that the puzzle might be designed in a way that makes this
configuration impossible, no matter what sequence of row and column
rotations one attempts.

\begin{problemparts}

  \problempart Model the puzzle as a state machine.

\solution{
The puzzle can be modeled by the state machine $M$ defined as follows:

\begin{itemize}

\item The set of states $Q$ consists of all arrangements of the digits
  in the set $\set{1, 2, 3, 4, 5, 6, 7, 8, 9}$ on a $3 \times 3$ grid
  where each digit appears exactly once.

\item The set of start states $Q_0$ consists of the single arrangement
  236 789 541.

\item The set $\delta \subseteq Q \times Q$ consists of all pairs of
  states $(q_1, q_2)$ such that $q_2$ can be obtained from $q_1$ by a
  row or column rotation.

\end{itemize}
}

\problempart Given the initial configuration of the puzzle indicated
above, namely 236 789 541, prove that your 6.042 TAs can never obtain
the configuration 123 456 789.

\solution{%

  The idea is to keep track of the number of digit pairs that are out
  of order relative to the desired configuration 123 456 789.  For
  example, in the initial configuration, $2$ appears before $1$; this
  pair of digits is out of order, because $1$ appears before $2$ in
  the desired configuration 123 456 789.  We will refer to an
  out-of-order digit pair as an {\em inversion}.  In the initial
  configuration, there are 17 inversions:

\[
\begin{array}{ccccc}
21 & 31 & 61 & 64 & 61 \\
75 & 74 & 71 & 85 & 84 \\
81 & 95 & 94 & 91 & 54 \\
51 & 41
\end{array}
\]

The key observation is that a rotation always changes the number of
inversions by an even amount.  Since the puzzle initially has an odd
number of inversions, no sequence of rotations can reduce the number
of inversions to 0, an even number.  Consequently, there will always
be at least one pair of digits out of order.

The main challenge is to prove that a rotation always changes the
number of inversions by an even amount.  We will prove this claim in a
sequence of lemmas, and then we will prove the main result as a
theorem.

\begin{lemma}
Swapping an adjacent pair of digits changes the number of inversions
by an odd amount.
\end{lemma}

\begin{proof}
  If the digits were initially in the same order as in 123 456 789,
  then the number of inversions is increased by 1, an odd number.
  Otherwise, the digits were initially in the wrong order, and the
  number of inversions is decreased by 1, also an odd number.
\end{proof}

\begin{lemma}
Swapping any pair of digits changes the number of inversions by an
odd amount.
\end{lemma}

\begin{proof}
  We will show how to swap any pair of digits using an odd number of
  swaps of adjacent digits.  The preceding lemma says that swapping
  adjacent digits changes the number of inversions by an odd amount.
  Therefore, swapping any pair of digits changes the number of
  inversions by an odd amount, because the sum of an odd number of odd
  numbers is odd.

  All that remains is to show how to swap any pair of digits using an
  odd number of swaps of adjacent digits.  Suppose that we are
  swapping digits $x$ and $y$, where $x$ is on the left, $y$ is on the
  right, and there are $k$ stray digits between the two.  First, we
  swap $x$ with its right neighbor $k$ times.  This leaves $x$
  directly left of $y$ and leaves all the stray digits shifted one
  place to the left.  Then we swap $x$ and $y$, putting $x$ into $y$'s
  original positions.  Finally, we swap $y$ with its left neighbor $k$
  times.  This puts $y$ into $x$'s original position and shifts the
  stray digits back to their original position.  The total number of
  swaps of adjacent digits is $k + 1 + k = 2k + 1$, which is odd for
  all $k \geq 0$.
\end{proof}

\begin{lemma}\label{lem:rotate}
  Rotating any row or column changes the number of inversions by an
  even amount.
\end{lemma}

\begin{proof}
  We show below that any row or column rotation can be obtained by two
  swaps.  The preceding lemma says that every swap changes the number
  of inversions by an even amount.  Since the sum of two odd numbers
  is even, any row or column rotation changes the number of inversions
  by an even amount.

  Here is how to obtain a rotation from two swaps.  Suppose that the
  digit sequence $xyz$ appears in some row or column.  Swapping $x$
  with $y$ and then swapping $x$ with $z$ creates the sequence $yzx$,
  which corresponds to a leftward or upward rotation.  Swapping $z$
  with $y$ and then $z$ with $x$ creates the sequence $zxy$.  This
  corresponds to a rightward or downward rotation.
\end{proof}

\begin{theorem}
  Your 6.042 TAs can not obtain the configuration 123 456 789.
\end{theorem}

\begin{proof}
  Let $P$ be a predicate on the states of $M$, denoting whether the
  number of inversions in the digit sequence of the puzzle relative to
  the 123 456 789 sequence is odd.  Moreover, let $P'(n)$, for $n \geq
  0$, be the predicate that asserts $P$ for all states that can be
  reached by $n$-step executions of $M$.  We show that $P$ is an
  invariant property of $M$, by showing that $P'(n)$ holds for all
  $n\geq0$.  The proof is by induction on the length $n$ of the
  execution of the state machine $M$.

  For the base case, we need to show that the property holds in the
  start state, \ie an execution of length $n = 0$.  This is true
  because in the initial configuration, the number of inversions is
  odd, in particular equal to 17.  For the inductive step, we must
  show that if $P$ holds for any configuration reachable after $n$
  steps of $M$, the $P$ holds for any configuration reachable after
  $n+1$ steps of $M$.  Fix $n \geq 0$ and let $q_0, q_1,\ldots, q_n,
  q_{n+1}$ denote any $n+1$-step execution of $M$.  $q_n$ is thus the
  final state of an $n$-step execution of $M$.  Thus, by our inductive
  hypothesis, in the state $q_n$, the puzzle has an odd number of
  inversions.  Now, consider the final step $(q_n,q_{n+1})$ of the
  $n+1$-step execution of $M$.  By Lemma~\ref{lem:rotate}, this step
  changes the number of rotations by an even amount.  It follows that
  the number of rotations of the state $q_{n+1}$ is odd.  Thus, by
  induction, we have shown that $P$ is an invariant property of $M$.

  Finally, since the number of inversions relative to 123 456 789 is
  always odd, the desired configuration with 0 inversions can not be
  obtained.
\end{proof}

In the above proof, we have proven that the the property that the
puzzle has an odd number of inversions is an invariant property of the
state machine $M$.
}

\end{problemparts}
\end{problem}
                                 