\documentclass[11pt,twoside]{article}
\usepackage{amsmath}
\usepackage{psfig}

\input{/pub/www/classes/6.042/fall99/inputs/macros-course}

%\newcommand{\solution}[1]{\smallskip \textbf{Solution:} #1 \textbf{endsoln}}
\newcommand{\solution}[1]{}

\begin{document}

\tutprobn{10}{10/15/99}{October 16, 1999}

\begin{problems}

\problem \textbf{The 15 puzzle.}  This puzzle consists of sliding square
tiles numbered $1,\dots,15$ held in a $4\times4$ frame with one blank
square.  Any tile adjacent to the blank square can slide into it.

The state machine model of the puzzle has states consisting of a 4 by 4
matrix with 16 entries consisting of the integers $1,\dots,15$ and a
blank.  For example, 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}\]

The state transitions correspond to exchanging the blank square and an
adjacent numbered tile.  For example, a blank 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
blank square, and

\item the coordinates of the blank 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 earlier in the list, and is larger, than the second element
of the pair. For example, the list 12453 has two out-of-order
pairs: 43 and 53.  The increasing list $12\dots n$ has no out-of-order
pairs.

\bparts

\ppart  Explain why there are exactly $n(n-1)/2$ out-of-order pairs in the
list $n\, n-1\, n-2\, \dots 1$.

\solution{

\emph{All} pairs in the sequence are out of order, so we just need to
count all the pairs in the sequence.  One way to count the pairs in the
sequence is to notice that for all $i \neq j$ between 1 and $n$, exactly
one of the ordered pairs $(i,j)$ and $(j,i)$ appears in the sequence,
namely the one in which the larger number appears first.  So the number of
out-of-order pairs is exactly half the number of ordered pairs.  By the
Product Rule, there are $n(n-1)$ such ordered pairs, so there are
$n(n-1)/2$ out-of-order pairs in the sequence.

Another way to derive the answer is to notice that there are $n-1$
out-of-order pairs starting with $n$, and $n-2$ out-of-order pairs
starting with $n-1$, \dots, 1 out-of-order pairs starting with 2.  So the
total number is $(n-1) + (n-2) + \cdots + 1$; this sum was proved by
induction in Rosen to equal $n(n-1)/2$.  (Next week we'll learn some
methods to find such ``closed form'' formulas for sums.)

}

\eparts

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 blank square.

\bparts

\ppart 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 $((16 \cdot 15/ 2) + 4) \bmod 2 = 1$.}

\ppart  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, 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$.  This reverses the order of three
pairs in $L$, changing the number of inversions by 3 or 1, but always by
an odd amount.  So the sum of $i$ and the number of out-of-order pairs
changes by an even amount, 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.

}

\eparts


\problem The weighted graph in Figure~\ref{fig:flowprob} represents a
system of pipes.  The weight on an edge indicates the \emph{capacity} of
the corresponding pipe, that is, the maximum rate at which water can pass
through the pipe in gallons per second.  Suppose that water enters the
system at vertex $S$ and leaves the system at vertex $T$.  The goal of
this problem is to determine the \emph{capacity} of the system, that is,
the maximum rate at which water can pass through the entire system in
gallons per second.

\begin{figure}[htbp]
\centerline{\psfig{figure=figures/flowprob.eps,height=2in}}
\caption{\em Connections and capacities of some pipes.}
\label{fig:flowprob}
\end{figure}

A \emph{flow} is modeled by assigning to each edge a direction and a
nonnegative number, called the \emph{flow rate through the edge}.  The
\emph{flow rate out of a vertex} is the sum of the flow rates of edges
with flows directed out of the vertex; the flow rate \emph{into} a vertex
is defined similarly.  The \emph{net flow} out of a vertex is the
difference of the flow out of and the flow into the vertex.  The flow rate
of an edge must not exceed the capacity of the edge.  Also, except for the
vertices $S$ and $T$, the net flow out of each vertex must be zero.

\bparts

\ppart Prove that the net flow out of vertex $S$ equals the net flow into
$T$.  This number is called the \emph{overall rate} of the flow.

\solution{

The sum of the net flow rates out of all the vertices counts the flow on
every edge once in each direction and therefore sums to zero.  Also, the
net flow out of each vertex other than $S$ and $T$ is zero, so the net
flow out of $S$ plus the net flow out of $T$ must also be zero.}

\ppart The least upper bound of all possible overall flow rates is called
\emph{the capacity of the system}.

Define a flow for the system in Figure~\ref{fig:flowprob} with as large an
overall flow rate as you can.  So the capacity of the system is at least
as large as this flow rate.

\solution{

With the flow rates and directions shown in Figure~\ref{fig:flowsol}, the
rate of flow through the entire system is 7 gallons per second, so the
capacity of the system is at least this large.

\begin{figure}[htbp]
\centerline{\psfig{figure=figures/flowsol.eps,height=2in}}
\caption{\em The maximum flow through the pipes.}
\label{fig:flowsol}
\end{figure}
}

\ppart Find a set of pipes with minimum total capacity such that removing
those pipes from the system completely cuts off vertex $S$ from vertex
$T$.  Mark these pipes on your diagram.  If you've done it right, this
total will equal the flow rate you found above.

\solution{

The edges marked with X's in Figure~\ref{fig:flowsol} have a total
capacity of 7 gallons per second.  Removing these edges disconnects $S$
from $T$.}

\ppart Explain why the capacity of a system can never exceed the capacity
of such a \emph{cut set} of edges cutting off $S$ from $T$.  (Don't offer
physical arguments about conservation of amount of liquid through pipes.
Such arguments \emph{assume} our model correctly reflects physical
reality, but that's exactly what we're trying to check.)  Conclude that
the capacity of the system is the rate you found in the two previous
parts.

\solution{Let $L,R$ be any partition of the vertices into two sets with $S
\in L$ and $T \in R$, and consider some flow.  Define $O_L$ to be
the sum of the net flows out of all the vertices in $L$.  Since the net
flow out of each vertex in $L$ besides $S$ is zero, $O_L$ is
actually equal to the net flow out of $S$.

On the other hand, notice that in the sum which defines $O_L$, the flow
rate of each edge between vertices in $L$ appears positively and
negatively.  On the other hand, the flow rates on edges going between $L$
and $R$ are counted once---positively if the flow is directed from $L$ to
$R$, negatively otherwise.  These edges are exactly the edges in the cut
set that separates $L$ from $R$.  So $O_L$ is also equal to the sum of the
flows on edges in the cut set, positively if the edge flow is directed out
of $L$, negatively otherwise.  But the flow on each edge in the cut set
must be bounded by the capacity of the edge, so the magnitude of $O_L$ can
at most equal the sum of the capacities of the edges in the cut set.
Since the net flow out of $S$ equals $O_L$, it's magnitude is also bounded
by the capacity of the cut set.

}

\eparts

\end{problems}

\end{document}


