\documentclass[11pt,twoside]{article}    
\usepackage{latex-macros/course}% !! use the macros 

\begin{document} 
\inclassproblems{4, Wed.}

\begin{problem} 
By now you are very familiar with the
\href{http://theory.lcs.mit.edu/classes/6.042/spring06/}{6.042 icon} that
appears on the course webpage and lecture slides.  This icon is a picture
of a game called the \textbf{Fifteen Puzzle}.  In this problem you will
establish a basic property of the Fifteen Puzzle using the method of
invariants, which may help you appreciate why this icon was chosen as the
course logo.

The 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 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, an 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} 
\]

We will use the invariant method to prove that there is no way to reach
the target state starting from the initial state.

\instatements{\newpage}
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}

\bparts
\ppart Write out the ``list'' representation of the start state and the
``impossible'' state.

\solution{
start: ((1\ 2\ \dots\ 15), (4,4)),

impossible: ((15\ 14\ \dots\ 1), (4,4)), 
}
\eparts

Let $L$ be a list of the numbers $1,\dots,15$ in some order.  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 and \emph{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.

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

\begin{problemparts}

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

\solution{The parity of the start state is
\[
(0+4) \bmod 2 = 0.
\]
The 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, consider how moves may
affect the parity.  There are only 4 moves types of moves: 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.}

\end{problemparts}

By the way, if two states have the same parity, then in fact there
\emph{is} a way to get from one to the other.  If you like puzzles, this
is a good one to think about on your own about after class.

\end{problem}

\instatements{\newpage}
\begin{problem}
The most straightforward way to compute the $b$th power of a number, $a$,
is to multiply $a$ by itself $b$ times.  This of course requires $b-1$
multiplications.  There is another way to do it using considerably fewer
multiplications.  This algorithm is called \emph{Fast Exponentiation}:

Given inputs $a \in \reals, b \in \naturals$,
initialize registers $x,y,z$ to $a,1,b$ respectively,
and repeat the following sequence of steps until termination:
\begin{itemize}
\item if $z=0$ \textbf{return} $y$ and terminate
\item $r := \text{remainder}(z,2)$
\item $z := \text{quotient}(z,2)$
\item if $r = 1$, then $y := xy$
\item $x := x^2$
\end{itemize}
We claim this algorithm always terminates and leaves $y = a^b$.

\bparts

\ppart  Model this algorithm with a state
machine, carefully defining the states and transitions.

\solution{\begin{enumerate}
\item $Q \eqdef\ \ \reals \cross \reals \cross \naturals$,
\item $Q_0 \eqdef\ \ \set{(a,1,b)}$,
\item transitions
\begin{equation*}
(x,y,z) \rightarrow
\begin{cases}
(x^2, y, \text{quotient}(z,2)) & \text{if $z$ is positive and even},\\
(x^2, xy, \text{quotient}(z,2)) & \text{if $z$ is positive and odd}.
\end{cases}
\end{equation*}
\end{enumerate}
}

\ppart Let $d \eqdef a^b$.  Verify that the following predicate, $P$, is
an invariant:
\[
P((x,y,z)) \eqdef\ \ [yx^z = d].
\]

\solution{TBA}

\ppart Prove that the algorithm is partially correct: if it halts, it does
so with $y=d$.

\solution{$P$ holds for the start state $(a,1,b)$ since $1\cdot a^b = a^b =d$
by definition.  So by the Invariant Theorem, $P$ holds for all reachable
states.  But a terminal state must have $z = 0$, so if any terminal state
$(x,y,0)$ is reachable, then $y = yx^0 = d$ as required.}

\ppart Prove that the algorithm terminates.

\solution{Just notice that $z$ is a natural-number-valued variable that
gets smaller at every transition.  So by the Well-Ordering Principle, when
this variable reaches its minimum value, the algorithm terminates.}

\ppart In fact, prove that it requires at most $2 \log_2 b$
multiplications for the Fast Exponentiation algorithm to compute $a^b$ for
$b>1$.

\solution{The value of $z$ is initially $b$ and gets halved at least at
every other step.  So it can't be halved more than $\log_2 b$ times before
hitting zero.}

\eparts
\end{problem}

\insolutions{
TA's: An extra problem for teams that finish early:

\begin{problem}
A robot moves on the two-dimensional integer grid.  It starts out at
$(0,0)$, and is allowed to move in any of these four ways:
\begin{enumerate}
\item (+2,-1)   Right 2, down 1
\item (-2,+1)   Left 2, up 1 
\item (+1,+3) 
\item (-1,-3) 
\end{enumerate}

Prove that this robot can never reach (1,1).
\end{problem}}

\solution{A simple invariant that does the job is defined on states
$(i,j)$ by the predicate: $i + 2j$ is an integer multiple of $7$.}


\end{document}
