\documentstyle[12pt,twoside]{article}

\newcommand{\problem}{%
  \paragraph{Problem}}
\newcommand(\solution}{%
  \paragraph{Solution}}

\begin{document}

\begin{problems}

%BEGIN Kavita's problems
% Fall 1998


%**************
%   PSET 4    *
%**************


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\problem{\bf (15 points)}
Suppose that the following procedure is used to multiply two
non-negative integers $a$ and $b$.

\centerline{
\begin{minipage}{0 in}
\medskip
\begin{tabbing}
xxx \= xxx \= xxx \= xxx \= xxx \= xxx \= \kill
Let $x = a$, $y = b$, $p = 0$. \\
Repeat the following steps. \\
\> If $x = 0$, then output $p$ and terminate. \\
\> Otherwise, if $x$ is even, then let $x = x/2$ and $y = 2y$. \\
\> Otherwise, if $x$ is odd, then let $x = x - 1$ and $p = p + y$.
\end{tabbing}
\medskip
\end{minipage}}

\begin{problemparts}

\problempart Model the procedure with a state machine.

\solution{The set of states $Q$ consists of quintuples $(a, b, x, y,
p)$ where all variables are non-negative integers.  The set of start
states $Q_0$ consists of the single state $(a, b, a, b, 0)$.  The set
of transitions $\delta$ consists of transitions of the form $(a, b, x,
y, p) \rightarrow (a, b, x', y', p')$ where one of the following two
sets of conditions holds:

\begin{enumerate}
\item $x$ is even and positive, $x' = x/2$, $y' = 2y$, and $p' = p$.
\item $x$ is odd, $x' = x - 1$, $y' = y$, and $p' = p + y$.
\end{enumerate}
}

\problempart Formulate an invariant relating $a$, $b$, $x$, $y$, and
$p$ that holds at the top of the loop.  Your invariant should imply
that when $x = 0$, $p = ab$.

\solution{
\[
xy + p = ab
\]
}

\problempart Prove that the invariant holds.

\solution{ The invariant holds initially, because $x = a$, $y = b$,
and $p = 0$.  Suppose that the invariant holds in state $(a, b, x, y,
p)$.  The invariant holds under a transition of the first type because:

\begin{eqnarray*}
x' y' + p'	& = &	(x / 2) \cdot 2y + p \\
		& = &	x y + p \\
		& = &	a b
\end{eqnarray*}

The first equation follows from the definition of the first type of
transition.  The second line is obtained by simplification, and the
third line uses the hypothesis that the invariant holds prior to the
transition.  By similar reasoning, the invariant holds under a
transition of the second type:

\begin{eqnarray*}
x' y' + p'	& = &	(x - 1) \cdot y + (p + y)\\
		& = &	x y + p \\
		& = &	a b
\end{eqnarray*}
}

\problempart Prove that the procedure terminates.

\solution{The variable $x$ is a non-negative integer that decreases
under every transition.  Therefore, the procedure must terminate after
at most $x$ transitions.}

\end{problemparts}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\problem {\bf (10 points)} Brad Banks, the one 6.042 TA that Theory
Pig trusts as his true friend, has promised our mascot a delicious
treat.  He places Theory Pig on one end of a 1 meter long rubber mat
and places the treat at the other end of the mat.  Theory Pig then
begins to run excitedly toward his treat at the rate of 1 centimeter
per second.  (Theory Pig is four inches tall and a bit pudgy.)

However, after exactly one second has elapsed, Brad stretches the
rubber mat out by 1 meter, so that its total length is now 2 meters.
The mat stretches uniformly and instantly, so there are now 2
centimeters of mat behind Theory Pig and 198 centimeters between him
and his treat.  Theory Pig continues running toward his prize, but
whenever another second elapses, Brad stretches the mat out by
another meter.

Either prove that Theory Pig never reaches his treat or else compute
approximately the number of seconds that he requires.

\solution{ Running at a rate of 1 centimeter per second, Theory Pig
crosses $1/100$ of the mat in the first second, $1/200$ of the mat in
the second second, $1/300$ of the mat in the third second, and so
forth.  He reaches his treat within $n$ seconds provided that the sum
of the first $n$ of these fractions is greater than or equal to 1.
Note that the sum of the first $n$ of these fractions is just $H_n /
100$.  This expression is at least 1 when $H_n$ is at least 100.
Since $H_n$ is about $\ln n$, around $e^{100} \approx 10^{43}$ seconds
are required for Theory Pig to reach his tasty treat.}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\problem {\bf (15 points)} The 6.042 staff recently received the
following mystifying, but disturbing email.

\begin{verbatim}
From: grzzwk@xoros19.gammaquad.plnt
To: 6042-staff@theory.lcs.mit.edu
Subject: Pset 2 complaint

We found your depiction of our society in problem set 2 simplistic,
inaccurate, and insulting.  We have launched a Fritolator device from
our homeworld at galactic coordinates (0, 0, 0).  During each hour,
the Fritolator can move in any one of the following ways.

  1.  first coordinate +4, second +1, third -1
  2.  first coordinate +1, second -1, third +3
  3.  first coordinate -2, second +3, third +4

Expect Earth, located at galactic coordinates (7, 8, 5), to be
Fritolated promptly.

/Grzzwk
\end{verbatim}

We are unsure what Fritolation entails, but surmise that it is not
good.

\begin{problemparts}

\problempart Model the movement of the Fritolator as a state machine.

\solution{
\begin{itemize}
\item The set of states $Q$ consists of all triples of integers $(x, y
, z)$.
\item The set of initial states $Q_0$ consists of the single
state $(0, 0, 0)$.
\item For all integers $x$, $y$, and $z$, the set of transitions
$\delta$ contains the following three transitions:

\begin{eqnarray*}
(x, y, z) & \rightarrow & (x + 4, y + 1, z - 1) \\
(x, y, z) & \rightarrow & (x + 1, y - 1, z + 3) \\
(x, y, z) & \rightarrow & (x - 2, y + 3, z + 4)
\end{eqnarray*}
\end{itemize}
}

\problempart Either list a sequence of Fritolator moves leading to the
destruction of Earth, or use the Invariant Theorem to prove that Earth
is safe.

\solution{
Earth is safe.

\bigskip

\begin{proof}
The proof uses the Invariant Theorem.  We prove that the following
invariant holds: in state $(x, y, z)$, $2x + 2y + z \equiv 0
\pmod{3}$.

The invariant holds in the only start state, $(0, 0, 0)$, because $2
\cdot 0 + 2 \cdot 0 + 0 \equiv 0 \pmod{3}$.  Next, we prove that the invariant
is maintained under each transition in $\delta$.  There are three
cases to consider corresponding to the three possible Fritolator
moves.

\begin{itemize}

\item If the Fritolator moves from $(x, y, z)$ to $(x + 4, y + 1, z -
1)$, then the invariant is maintained because:

\begin{eqnarray*}
2 (x + 4) + 2(y + 1) + (z - 1)
	& \equiv & (2 x + 2 y + z) + 9 \pmod{3} \\
	& \equiv & 2 x + 2 y + z \pmod{3} \\
	& \equiv & 0 \pmod{3} \\
\end{eqnarray*}

Terms are just rearranged in the first step.  The second step uses the
fact that 6 is a multiple of 3, and the third step uses the assumption
that the invariant holds in state $(x, y, z)$.

\item Similarly, if the Fritolator moves to position $(x + 1, y - 1, z
+ 3)$, then the invariant is maintained because $2 (x + 1) + 2 (y - 1)
+ (z + 3) \equiv (2x + 2y + z) + 3 \equiv 0 \pmod{3}$.

\item If the Fritolator moves to position $(x - 2, y + 3, z + 4)$,
then the invariant is maintained because $2 (x - 2) + 2 (y + 3) + (z +
4) \equiv (2x + 2y + z) + 6 \equiv 0 \pmod{3}$.
\end{itemize}

Earth is safe at coordinates $(7, 8, 5)$, because $2 \cdot 7 + 2 \cdot
8 + 5 \equiv 2 \pmod{3}$.
\end{proof}
}

\end{problemparts}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


%END   Kavita's problems

%BEGIN Joe's problems


\problem %source: spring00 ps4, adapted from fall97 ps4

The following algorithm, called the \emph{Russian peasants algorithm},
can be used to multiply any two natural numbers $x$ and $y$ using only
left bit-shift (i.e., multiply by 2) and right bit-shift (i.e., divide
by 2 and drop the remainder, if any) operations.  The answer is
accumulated in variable $a$; variables $r$ and $s$ are for temporary
storage.

\begin{tabbing}
XXX\=XXX\=XXX\=XXX\kill
$r:=x$; \\
$s:=y$; \\
$a:=0$;\\
do until $s=0$:\\
   \>if s is even then \\
   \>\>   $r := 2r$; \\
   \>\>   $s := s/2$;\\
   \>else \\
   \>\>   $a := a + r$; \\
   \>\>   $r := 2r$; \\
   \>\>   $s := (s-1)/2$;\\
\end{tabbing}
The answer $xy$ is the value left in the accumulator $a$ when the 
procedure terminates. 

\problempart Model the algorithm as a state machine.  
That is, define the states $Q$, the start states $Q_0$, and the steps
$\delta$.
\omitsolution{
\begin{solution}
$Q=\{(r,s,a,x,y)|r,s,a,x,y\in \mathbb{N}\}$\\
$Q_0=\{(x,y,0,x,y)\}$\\
$\delta: (r,s,a,x,y)\rightarrow (r',s',a',x',y')$, where\\
$x'=x$, $y'=y$, $r'=2r$\\
Even $s$: $s'=s/2$, and $a'=a$\\
Odd $s$: $s'=(s-1)/2$, and $a'=a+r$\\
\end{solution}
}

\problempart List the sequence of states that appears in an execution of the
algorithm for inputs $x=5$ and $y=9$.

\omitsolution{
\begin{solution}
$(5,9,0,5,9)\rightarrow (10,4,5,5,9) \rightarrow (20,2,5,5,9) \rightarrow (40,1,5,5,9) \rightarrow (80,0,45,5,9)$
\end{solution}
}

\problempart Prove that the algorithm gives the correct answer if it
terminates, that is, that $s = 0$ implies $a = xy$.
(Hint:  Use induction on the number of steps in the execution.  You
will have to strengthen the inductive hypothesis.)

\omitsolution{
\begin{solution}
We prove the following invariant.

$P(r,s,a,x,y) = ``xy = rs+a$''.

{\bf Base case: }
For any initial state we have $P(x,y,0,x,y)$ which is true.

{\bf Inductive step:} Consider a transition from $(r,s,a,x,y)$ to
$(r',s',a',x',y')$.  We need to prove that $P(r,s,a,x,y) \rightarrow
P(r',s',a',x',y')$.

There are two cases based on the type of action, {\it even} or {\it odd}.

$\ms{even}$: \\
Doubling $r$ while halving $s$ doesn't change the product $rs$,
and $a$ doesn't change.  So $r's'+a' = rs+a = xy$.

$\ms{odd}$:\\ 
$r' = 2r$, $s' = {s - 1 \over 2}$, and $a' = a + r$.
So $r's' + a' = 2r{ s - 1 \over 2 } + a + r$.
Reorganizing terms yields $r's'+a' = rs+a = xy$.

The invariant is proved.  Now when $s=0$ this implies $a=xy$ and we have
our result.
\end{solution}
}

\problempart Prove that the algorithm terminates. 

\omitsolution{
\begin{solution}
We first notice the invariant that $s\geq 0$ for any reachable
execution state.  We could prove that this is an invariant by showing
it is true for the base case, $y\geq 0$, and furthermore, no
transition exists from a state with $s\geq 0$ to $s<0$ when $s$ is odd
or even.  A more advanced argument is to say that this is enforced by
the ``type'' of $s$, which is that $s\in \mathbb{N}$.

Now consider the value of $s$ during any valid execution.  Since
$s\geq 0$, as shown above, no transition increases $s$.  Furthermore,
for $s>0$, all transitions decrease $s$ by at least 1.  Thus for any
values of $x,y\in \mathbb{N}$, $s$ decreases to 0 in a finite number
of steps, and thus the program terminates in a finite number of steps.
\end{solution}
}

\problem %source: spring00 ps4-5
\label{puzzleProblem}
%[[[Pset 4.5]]]

This problem is repeated from last Friday's tutorial, slightly
rewritten.

Math Moose has been given a new 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, Math Moose has 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, Math Moose has failed miserably.
He is beginning to suspect 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.

\omitsolution{%
\begin{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 relation $\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}
  \end{solution}%
  }

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

\omitsolution{%
\begin{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 & 65 & 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}

Now define $P(q)$ to be the predicate saying that, in state $q$ of $M$,
the number of inversions in the digit sequence relative to the 123 456
789 sequence is odd. 
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$.  

\begin{theorem}
$P'(n)$ is true for all $n \geq 0$.
\end{theorem}

\begin{proof}
By induction on $n$, the length of the execution. 

  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$, then $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$.
\end{proof}


\begin{corollary}
Math Moose cannot obtain the configuration 123 456 789.
\end{corollary}

\begin{proof}
This has an even number (0) of inversions.
\end{proof}

\end{solution}%
}

\end{problemparts}

\problem

\problem %source: spring00 ps4-5
%[[[Shishir:  This is derived from problem set 4, Handout 21, Spring
%98.  Please fill in the solution.]]]
A robot wanders on a 2-dimensional grid, starting at the origin,
$(0,0)$.
In one step, he is able to move unit distance along any diagonal line,
that is, at an angle of $\pm 45$ degrees or $\pm 135$ degrees.
\begin{problemparts}
\problempart
Describe how to model the robot's behavior as a state machine.

\omitsolution{
\begin{solution}

The possible states are:
$Q = \{(x, y)\} \subset (\reals \times \reals) $

The initial state is: $Q_0 = (0, 0)$

The transitions are:
$\delta \subseteq Q \times Q = $ $\{(q1, q2)$ such that $q2$ is $\pm 45$ 
degrees or 
$\pm 135$ degrees from $q1\} $

\end{solution}
}

\problempart
Give an execution of the state machine that reaches the point
$(\frac{5 \sqrt{2}}{2}, \frac{-3 \sqrt{2}}{2})$.

\omitsolution{
\begin{solution}

Starting at $Q_0$ make the following transitions: 
\begin{enumerate}
\item $-45$ degrees: New state is $(\frac{\sqrt{2}}{2}, \frac{- \sqrt{2}}{2} )$
\item $-45$ degrees: New state is $(\frac{2 \sqrt{2}}{2}, \frac{- 2 \sqrt{2}}{2} )$
\item $-45$ degrees: New state is $(\frac{3 \sqrt{2}}{2}, \frac{- 3 \sqrt{2}}{2} )$
\item $45$ degrees: New state is $(\frac{4 \sqrt{2}}{2}, \frac{- 2 \sqrt{2}}{2} )$
\item $-45$ degrees: New state is $(\frac{5 \sqrt{2}}{2}, \frac{- 3 \sqrt{2}}{2} )$
\end{enumerate}
\end{solution}
}

\problempart
Prove (using induction on the length of the execution) that the robot
cannot reach the point $(5,5)$. 

\omitsolution{
\begin{solution}

We will prove a stronger theorem first and then apply it to our special
case.

\begin{theorem*} 
After any n step execution (starting at $Q_0$), the $x$ and $y$ coordinates of
the final state are both multiples of $\frac{\sqrt{2}}{2}$.
\end{theorem*}

\begin{proof} Let $P(n)$ be the predicate that after $n$ steps, the  $x$ and
the $y$ coordinates of the current state are both multiples of 
$\frac{\sqrt{2}}{2}$.

\begin{description}\itemsep 0ex
\item[Base Case:~~] $P(0)$ is true since 
$Q_0 = (0,0)$ and $0$ is a multiple of $\frac{\sqrt{2}}{2}$.
\item[Inductive Step:~~] We must show that for any positive integer $n$,
$P(n) \implies P(n+1)$. We can do this by picking an arbitrary $n$ step
execution and enumerating all the possibilities for the $(n+1)$th step. 
By the inductive hypothesis, after our $n$ step execution, the current $x$ and
$y$ coordinates are both multiples of 
$\frac{\sqrt{2}}{2}$.
Therefore, we can pick integers $k$ and $j$ and call our current state:
$(\frac{k \sqrt{2}}{2} , \frac{j \sqrt{2}}{2} )$

Now there
are 4 possible transitions to the new state, $Q_{n+1}$:
\[
\begin{array}{rccccccccc}
45~degrees: & Q_{n+1} & = & (
\frac{k \sqrt{2}}{2} + \frac{\sqrt{2}}{2},
\frac{j \sqrt{2}}{2} + \frac{\sqrt{2}}{2}) 
& = & (
\frac{(k+1)\sqrt{2}}{2}, 
\frac{(j+1)\sqrt{2}}{2}
) \\
%
-45~degrees: & Q_{n+1} & = & ( 
\frac{k \sqrt{2}}{2} + \frac{\sqrt{2}}{2},
\frac{j \sqrt{2}}{2} - \frac{\sqrt{2}}{2}) 
& = & (
\frac{(k+1)\sqrt{2}}{2}, 
\frac{(j-1)\sqrt{2}}{2}
) \\
%
135~degrees: & Q_{n+1} & = & ( 
\frac{k \sqrt{2}}{2} - \frac{\sqrt{2}}{2},
\frac{j \sqrt{2}}{2} + \frac{\sqrt{2}}{2}) 
& = & (
\frac{(k-1)\sqrt{2}}{2}, 
\frac{(j+1)\sqrt{2}}{2}
) \\
%
-135~degrees: & Q_{n+1} & = & ( 
\frac{k \sqrt{2}}{2} - \frac{\sqrt{2}}{2},
\frac{j \sqrt{2}}{2} - \frac{\sqrt{2}}{2}) 
& = & (
\frac{(k-1)\sqrt{2}}{2}, 
\frac{(j-1)\sqrt{2}}{2}
) \\
\end{array}
\]
In all four situations, our resulting state still satisfies the
predicate. Therefore, we have $P(n) \implies P(n+1)$.

\end{description}

Finally, since the $x$ and $y$ coordinates of any reachable state are always
multiples of
$\frac{\sqrt{2}}{2}$, $(5,5)$ is not reachable.
      
\end{proof}

\end{solution}
}
\end{problemparts}

\problem %source: spring00 ps4-5
%[[[New problem]]]
The nondeterministic algorithm $NSort$ starts with a sequence $S$ of $n$
distinct integers, initially in any order.
$NSort$ describes how to sort the sequence, in place, into increasing order.
What it does is to choose, arbitrarily, any pair of adjacent numbers
that appear in the wrong order, that is, that form an ``inversion'',
as in Problem \ref{puzzleProblem}.
It corrects this inversion by interchanging these two numbers, leaving
the rest of the sequence $S$ unchanged.
$NSort$ repeats this step until no further steps can be applied.

\begin{problemparts}
\problempart
Model this as a state machine.

\omitsolution{
\begin{solution}

The state is represented by a string:
\begin{center}
$Q = \{ x_1 x_2 x_3 \cdots x_n $ such that $x_i \in \integers$ and the 
$x_i$ are all 
distinct $\}$
\end{center}

The possible start states are any random string so:
\[ Q_0 = Q \]
In other words, any state can be a starting state.

The set of transitions 
$\delta \subseteq Q \times Q$ is:
\begin{center}
$\{(q_1, q_2)\}$ such that $q_2$ is exactly the
same as $q_1$ except two adjacent positions are swapped. 
In $q_1$ these positions were
out of order (the greater one had lower index) but in $q_2$ the order is
correct.
\end{center}
\end{solution}
}

\problempart
Prove that $NSort$ eventually terminates with $S$ completely sorted.

\omitsolution{
\begin{solution}
Let us define three quantities:
\begin{description}
\item[~$N_{total}$:] Total number of out of order pairs in the string 
\item[~~~$N_{adj}$:] Number of out of order {\em adjacent} pairs in the string 
\item[$N_{nonadj}$:] Number of out of order {\em non-adjacent} pairs in the string
\end{description}
Notice that since adjacent or non-adjacent is an exhaustive set of
possibilities for a pair, for any state:
\[N_{total} = N_{adj} + N_{nonadj}\] 
Also, notice that all three quantities are by definition in $\naturals$.
The following lemma is very helpful: 

\begin{lemma}
$N_{total} = 0 \Longleftrightarrow N_{adj} = 0$
\end{lemma}

\begin{proof}

$\Longrightarrow$. For contradiction suppose $N_{adj} \neq 0$ but $N_{total}
= 0$. Then $N_{nonadj} = - N_{adj}$. Since both $N_{adj}$ and $N_{nonadj}$
are nonnegative, they must both be 0. Contradiction.

$\Longleftarrow$. For contradiction, suppose $N_{adj} = 0$ but $N_{total}
\neq 0$. Then there exists $i, j \leq n$ such that $i < j$ and $x_i >
x_j$. Let us pick $i$ and $j$ to minimize their difference. In other words,
out of the pairs that are inverted, let's pick the pair that is closest.
Since $N_{adj} =
0$, these two entries cannot be adjacent so $j > i + 1$. 
So there is some entry, $x_{i+1}$ adjacent to $x_i$. Since
no adjacent pairs are out of order,  $x_i < x_{i+1}$. Also, since $x_i$ and
$x_j$ were the closest inverted pair, $x_{i+1}$ and $x_j$ cannot be
inverted. Therefore, $x_{i+1} < x_j$. This means that $x_i < x_{i+1} < x_j$
which is a contradiction.
\end{proof}


First, we can use this lemma to prove {\bf correctness}. That is, we need to
show that when the algorithm terminates, the string is completely sorted. We
know that our algorithm terminates when there are no adjacent inverted
pairs. Applying our lemma, this means that there are no inverted pairs at
all. A string with no inverted pairs is a sorted string. QED.

Second, we can use this lemma to prove {\bf termination}. Consider the
following facts:
\begin{enumerate}
\item

$N_{total}$ decrease with every transition. {\em (Note that $N_{adj}$ does NOT
decrease with every transition.)}
We can show this by examining our transition. 
The exchange itself decreases the number of inversions by one. However,
it may produce ``new'' adjacent inversions. But the key fact is that it can form
no {\em new} inversions. The only thing that can happen is that a previously
non-adjacent inversion can become adjacent. This is because the only items
that move are the ones being exchanged, and they are being ordered
correctly. As far as all the other items in the string are concerned, the
two items are in the same place. Thus, the total number of inversions
decreases by 1 at every transition.

\item

$N_{total}$ will eventually reach 0 in any live execution. This is because
$N_{total}$ is a nonnegative integer by definition. By the well ordering
principle, and the fact that it is decreasing at every transition, it will
eventually reach 0. 

\item

When $N_{total}$ reaches 0, the algorithm will stop. We show this by
applying our lemma. If $N_{total} = 0$ then $N_{adj} = 0$ so the algorithm
terminates by definition.
\end{enumerate}

Thus the algorithm will terminate. Also, at termination, 
$N_{total} = N_{adj} = 0$ so the string is sorted.
\end{solution}
}

\problempart
Give a good upper bound on the number of steps that $NSort$ can take
until it terminates. 

\omitsolution{
\begin{solution}

Two possibilities are:
\begin{description}
\item[Loose upper bound: ]

Every item can be exchanged with every other item at most once. So for all
$n$ items, there are $n-1$ other items that they could be exchanged with. So
$n(n-1) = O(n^2)$ is an upper bound.

\item[Tight upper bound: ]

$N_{total}$ is definitely an upper bound since it decreases by 1 at every
step until it reaches 0. Also, $N_{total}$ is upper bounded by the total
number of combinations of elements of the string. This is $\left(
\begin{array}{c} n \\ 2 \end{array} \right)$ or $\frac{n(n-1)}{2}$. Notice
that this is the same as the loose bound except it recognizes that every
pair in the loose bound is actually being counted twice.

\end{description}

\end{solution}
}

\problempart
For the special case where n = 4, give an example execution that takes
the maximum number of steps to terminate. 

\omitsolution{
\begin{solution}
The following execution takes $\frac{n(n-1)}{2} = \frac{4*3}{2} = 6$ steps:
\[
\begin{array}{rccccccc}
Start  \longrightarrow & 4 & 3 & 2 & 1 \\
Step~1 \longrightarrow & 3 & 4 & 2 & 1 \\
Step~2 \longrightarrow & 3 & 2 & 4 & 1 \\
Step~3 \longrightarrow & 3 & 2 & 1 & 4 \\
Step~4 \longrightarrow & 2 & 3 & 1 & 4 \\
Step~5 \longrightarrow & 2 & 1 & 3 & 4 \\
Step~6 \longrightarrow & 1 & 2 & 3 & 4 
\end{array}
\]
\end{solution}
}

\end{problemparts}

\problem %source: spring00 pset4-5
%[[[Based on spring97, handout 28, pset 9 solutions]]]
The algorithm $Mark$ starts with a connected, undirected graph $G =
(V,E)$, with all edges unmarked.
Then it proceeds to mark some of the edges, by repeatedly performing
the following steps: 
\begin{enumerate}
\item {\bf Choose} any edge $e \in E$ such that there is currently no path of
marked edges between the endpoints of $e$ \\
\item {\bf Mark} edge $e$\\
\end{enumerate}
Prove that when the algorithm finishes, the set of marked edges forms
a spanning tree of the input graph $G$.

(A {\em spanning tree} of $G$ is a tree whose edges are a subset of
the set $E$ of edges of $G$, and that contains an edge incident on every
vertex of $G$.)

\omitsolution{
\begin{solution}

We will need to show that the marked edges are acyclic, touch every vertex
of G, and that the algorithm does indeed finish. 

\begin{description}

\item[Marked edges are acyclic:]

Use the Invariant Theorem:

{\bf Invariant:} The marked edges form an acyclic graph. 
\begin{description}
\item[Start condition:] Initial state.  
Initially all edges are unmarked, so there are no cycles consisting of
marked edges. 

\item[Step condition:]
Consider a step $(q,q')$, where we assume that there are no cycles
consisting of marked edges in state $q$.
We show that the same condition holds in state $q'$.

In this step, the algorithm marks an edge $e$ for which there was
previously no marked path between its endpoints.
This means that, after the step, there is exactly one marked path
between the endpoints of $e$.
Thus, the new edge is not part of a cycle, in the new state $q'$.
This means that there are still no cycles in state $q'$.
\end{description}

\item[Algorithm terminates:] 
This is shown because once an edge is marked, it can never be
unmarked. Since we have a finite set of edges, and every transition
necessarily marks one edge, we will eventually run out of candidate edges
and the algorithm will terminate.

\item[Marked edges touch every vertex of G:] We can show this by
noticing that if $(v, w)$ is an edge in G then there is a path of marked
edges from $v$ to $w$. If there wasn't, then $(v, w)$ would become a
candidate edge because its endpoints are not connected by marked edges. Then
$(v,w)$ would itself be marked and thus $v$ and $w$ are indeed connected by
marked edges. 

Now we need to show that every vertex is touched by a marked edge. For
contradiction, suppose there is some $v \in G$ that is not touched by any
marked edges.  However, G is connected, so there must be at least one
$(v,w)$ edge in G. Since this edge exists, $v$ and $w$ must be connected by
marked edges, so $v$ must indeed be touched by a marked edge. Contradiction.



%[[[We must also show that when no rule can be applied, it must be the
%case that the marked edges form a spanning tree of $G$.
%Shishir?  Prove this?  The following lines appeared in the previous
%solution, but they don't look like a convincing proof to me.
%
%``Since the for-loop loops over all the edges then all the vertices of
%$G$ (that have edges) will be contained in the forest.''
%
%Basically, we have to argue that, if we reach a point where no further
%steps are enabled (a ``final state''), then any two nodes are
%connected by some path of marked edges.
%I think that this probably will use a lemma saying, in a final state,
%if $(v,w)$ is an edge of $G$ then there is a path of marked edges from
%v to w.
%Then apply this lemma in an inductive proof to show that any two nodes
%of $G$ (which are assumed to be connected in $G$ by SOME path), are
%connected in the final state by a path of marked edges.
%Probably could avoid the induction by using some kind of transitive
%closure result.
%]]]
%
\end{description}

\end{solution}
}

\problem %source: spring00 pset4-5
Cache management protocol $HybridCache$ is a hybrid of the two caching
protocols presented in Installment 2 of the notes on computational
processes.
$HybridCache$ maintains a memory and two caches, as before.
Only now, an update to memory causes the value to be cleaned out of
cache1 but not out of cache2.
The intent is that cache2 is allowed to be out-of-date, but cache1 is
not.

\begin{problemparts}

\problempart
Model $HybridCache$ carefully as a state machine.

\omitsolution{
\begin{solution}

\begin{description}
\item[$Q$:] $\{ (memory, cache1, cache2) \mbox{ of the types described in Lecture 8 handouts}\}$. \\
\item[$Q_0$:] memory is arbitrary, caches map everything to $\ms{null}$. \\
\item[$\delta$:] 
$(\ms{memory}, \ms{cache1}, \ms{cache2}) \rightarrow 
 (\ms{memory}', \ms{cache1}', \ms{cache2}')$ where all steps are the same as in Lecture 8 except
the memory update step:
\begin{description}
\item[1. ] 
$\ms{memory}(a) :=$ arbitrary $\ms{value}$ (not null). \\
$\ms{cache1}(a) := \ms{null}$ 
\end{description}
\end{description}

\end{solution}
}

\problempart
State carefully an invariant saying that cache1 is always up-to-date. 

\omitsolution{
\begin{solution}

Can show, in all reachable states either
$\ms{cache1}(a) = \ms{memory}(a)$ or 
$\ms{cache1}(a) = \ms{null}$ \\
\\
In other words: 
If $\ms{cache1}(a) \neq \ms{null}$ then $\ms{cache1}(a) =
\ms{memory}(a)$. \\

Note: No such guarantees are provided for cache2.
\end{solution}
}

\problempart
Prove your invariant carefully using the Invariant Theorem.

\omitsolution{
\begin{solution}
\begin{description}
\item[Start condition:] 
Everything in cache1 is null so the invariant is trivially true.

\item[Transition condition:] 
We show all possible transitions:
\begin{description}
\item[1. Memory Update: ] 
After this step, 
the only changed value is in cache1 and is changed to null. In this case, the Invariant holds 
trivially (they only need to match if cache1 holds a value other than null).
\item[2. Cache1 Update: ] 
The only changed value is in cache1 and is changed to match the one in memory. Invariant holds.
\item[3. Cache2 Update: ] 
Only cache2 changes. Since the Invariant makes no claims about cache2, the Invariant still holds.
\item[4. Cache1 Drop Value: ] 
The only changed value is in cache1 and is changed to null. In this case, the Invariant holds 
trivially.
\item[5. Cache2 Drop Value: ]
Same as 3.
\end{description}
\end{description}

\end{solution}
}

\problempart
Now modify $HybridCache$ to a new $WrongHybridCache$ algorithm,
which is just like $HybridCache$ but includes one additional type of
step,
which allows anything to be copied from
cache2 to (the same address in) cache 1.
Model this new algorithm as a state machine.

\omitsolution{
\begin{solution}

Same as in a. except for one additional transition:
\begin{description}
\item[6. ] 
$\ms{cache1}(a) := \ms{cache2}(a)$ 
\end{description}
\end{solution}
}

\problempart
Give an execution of $WrongHybridCache$ that demonstrates that the
invariant is violated. 

\omitsolution{
\begin{solution}
\begin{description}
\item[memory\_write(1)] 
$~$\\
$\ms{memory}(a) := 1$ \\
$\ms{cache1}(a) := null$ 

\item[cache1\_update()]
$~$\\
$\ms{cache1}(a) := 1$ 

\item[cache2\_update()]
$~$\\
$\ms{cache2}(a) := 1$ 

\item[memory\_write(2)]
$~$\\
$\ms{memory}(a) := 2$ \\
$\ms{cache1}(a) := null$ 

\item[cache2\_to\_cache1()]
$~$\\
$\ms{cache1}(a) := 1$ 

\end{description}

Now cache1 holds a different value than memory in entry a. 
\end{solution}
}

\problempart
Identify precisely where your proof of the invariant for $HybridCache$
would break down if you applied it to $WrongHybridCache$.

\omitsolution{
\begin{solution}

It would break down in trying to prove the transition holds through transition 6. 
Here it is not the case that the value in cache1 is always changed to either match memory
or be null. Cache1 can take on any value from cache2, and we have no guarantees that the value in
cache2 is up to date.

\end{solution}
}

\end{problemparts}

\problem %source: spring00 ps4-5
%[[[New problem.  Comes from lecture notes from fall98---I believe
%Eric Lehmann wrote up a supplementary handout on this.  But
%beware---the old statement of this that I used in fall98 had the boys
%and girls reversed.]]]
It turns out that the stable marriage algorithm described in lecture
(Installment 2 of notes) is very unfair, in the sense that, in any
(live) execution of the algorithm:
\begin{itemize}
\item The boys end up paired up with the most preferred girl that they
possibly could get.
\item The girls end up paired up with the least preferred boy that they
possibly could get.
\end{itemize}
(So, being aggressive pays.)

More precisely, define $\ms{PP}$ (``possible pairs'') to be the set of
all (boy,girl) pairs that occur in any stable pairings.
Then, in the final state of the algorithm:
\begin{itemize}
\item If a boy $b$ likes a girl $g$ more than the partner he has received, then
$(b,g) \notin \ms{PP}$, that is, $g$ isn't even possible for him.
\item If a girl $g$ likes a boy $b$ less than the partner she has
received, then $(b,g) \notin \ms{PP}$. 
\end{itemize}

Prove these results.

\omitsolution{
\begin{solution}

\begin{description}
\item[(a) ]

You can prove as an invariant, the claim that:
``If $b$ has crossed $g$ off his list, then $(b,g) \notin \ms{PP}$.''
This statement immediately implies the claim in (a).

%[[[Shishir: 
The key step is where g rejects b, and he crosses her off
his list. 
She rejects him in favor of some other boy b'.

Now, suppose for the sake of contradiction that P is a stable pairing
containing $(b,g)$.
We can show that $(b',g)$ form an unstable pair in P:
We know that $g$ prefers $b'$ to $b$, because in this step of the
algorithm, she rejects $b$ in favor of $b'$.
We have to argue that, also, $b'$ prefers $g$ to whomever he is matched up
with in P---call her $g'$.

This is a tricky argument.
Can argue it by contradiction, using the fact that the invariant is
true before the step.
Suppose for the sake of contradiction that $b'$ prefers $g'$ to $g$.
In the pre-state, $b'$ is pursing $g$, so he must have crossed off
his higher preference $g'$.
But by the invariant in the pre-state, this means that $(b',g') \notin
\ms{PP}$, that is, $(b',g')$ do not form a possible pair.
That's a contradiction, because we've assumed that they are paired in
the stable pairing $\ms{PP}$.
%]]]

\item[(b) ]

You can prove the invariant:

``If $g$ likes $b$ less than her most-preferred boy that is currently
pursuing her, then $(b,g) \notin \ms{PP}$.''
This statement implies the claim in (b).

This can be proved without using an inductive argument (or the
Invariant Theorem), but simply by contradiction using the invariant
used for part (a). 

%[[[Shishir:  It's not so simple to keep straight.

Suppose for the sake of contradiction, that there is some reachable
state in which
$g$ likes $b$ less than her most-preferred boy that is currently
pursuing her, call him $b'$, 
but $(b,g) \in \ms{PP}$.
Fix P, some stable pairing having $(b,g) \in P$.
We can show that $(b',g)$ form an unstable pair in P:
We know that $g$ prefers $b'$ to $b$, by the assumption above.
We have to argue that also $b'$ prefers $g$ to whomever he is matched
with in $P$, call her $g'$.

Suppose he doesn't (this is going to be a contradiction within a
contradiction!), that is $b'$ prefers $g'$ to $g$.
That is, $b'$ prefers $g'$ to the girl he is currently pursuing.
This means that $b'$ has crossed $g'$ off his list in the current state.
By the previous invariant, proved for part (a), it follows that
$(b',g') \notin \ms{PP}$.  
So surely we can't have $(b',g') \in P$.
This is a contradiction, which means that $b'$ does prefer $g$ to
$g'$.
That's what we needed to show above.

So, this all says that $(b',g)$ form an unstable pair in P.
That's a contradiction to the assumption that P is a stable matching.


%Shishir:
%You might find it helpful to write this in a structured way.  This is
%exactly the sort of proof where the logic gets confusing.
%Shishir: I have a handwritten structured version at home, but it has
%the boys and girls interchanged.  I think Eric probably type-set this
%and put it into the supplementary lecture notes for fall98.]]]
\end{description}

\end{solution}
}

\problem %source: spring00 pset5

$ req \in \set{\mquote{add\mdash term}, \mquote{find\mdash coeff}, null}
        \union \set{\mquote{OK}} \union \ints $

$ power \in \nats \union \set{null}  $

$ mult \in \ints \union \set{null}  $

\item $Q_0$: \\
A set with only one element:

$\;\; \set{(0, null, null, null)} $

or, equivalently,

$\;\; p = 0$, $req = null$, $power = null$, $mult = null$

\item $L$:
    \begin{itemize}
    \item[] Input labels:
        \begin{itemize}
        \item[] $req\mdash add\mdash term(c,e)$, \ \ $c \in \ints, e \in \nats$
        \item[] $req\mdash coeff(e)$, \ \ $e \in \nats$
        \end{itemize}
    \item[] Internal labels:
        \begin{itemize}
        \item[] $comp\mdash sum(c,e)$, \ \ $c \in \ints, e \in \nats$
        \item[] $comp\mdash coeff(e)$, \ \ $e \in \nats$
        \end{itemize}
    \item[] Output labels:
        \begin{itemize}
        \item[] $return(\mquote{OK})$
        \item[] $return(c)$, \ \ $c \in \ints$
        \end{itemize}
    \end{itemize}

\item $\delta$: \\
        Each is associated with (generates) the label of its namesake.
    \begin{enumerate}
    \item $req\mdash add\mdash term(c,e)$:  \\
        Can occur anytime. \\
        if $req = null$ then \\
        $~\;\;\;\; req := \mquote{add}$ \\
        $~\;\;\;\; power := e$ \\
        $~\;\;\;\; mult := c$
    \item $req\mdash coeff(e)$:  \\
        Can occur anytime. \\
        if $req = null$ then \\
        $~\;\;\;\; req := \mquote{find\mdash coeff}$ \\
        $~\;\;\;\; power := e$ \\
        $~\;\;\;\; mult := null$
    \item $comp\mdash sum(c,e)$:  \\
        Can occur if $req = \mquote{add\mdash term}$, $mult = c$, and $power = e$. \\
        $~\;\;\;\; p := p + c \cdot x^e$ \\
        $~\;\;\;\; req := \mquote{OK}$
    \item $comp\mdash coeff(e)$:  \\
        Can occur if $req = \mquote{find\mdash coeff}$ and $power = e$. \\
        $~\;\;\;\; req := \textrm{coefficient of $x^e$ in $p$}$
    \item $return(\mquote{OK})$:  \\
        Can occur if $req = \mquote{OK}$. \\
        $~\;\;\;\; req, power, mult := null$
    \item $return(c)$:  \\
        Can occur if $req = c$. \\
        $~\;\;\;\; req, power, mult := null$
    \end{enumerate}

\end{itemize}



}

  \problempart List some (4--5) traces that are exhibited by your state
  machine $\ms{ADP}$.  Include at least one that involves a request arriving
  when it is not supposed to.

\omitsolution{

  
  \medskip
  \textbf{Solution:} 

Start with $(0, null, null, null)$:

\[
\begin{array}{ll}
%perhaps put explanations in on right?
req\mdash add\mdash term(1,1) & \\
return(\mquote{OK})  & \\
req\mdash add\mdash term(2,2) & \\
return(\mquote{OK})  & \\
req\mdash coeff(2)      & \\
return(2)  & \\
req\mdash add\mdash term(2,1) & \\
return(\mquote{OK})  & \\
req\mdash coeff(1)      & \\ 
return(3)  & \\
\end{array}
\]

Start with $(0, null, null, null)$:

\[
\begin{array}{ll}
req\mdash add\mdash term(1,1)  & \\
return(\mquote{OK})  & \\
req\mdash add\mdash term(2,2) & \\
req\mdash coeff(2)  & \\
return(\mquote{OK})  & \\
req\mdash coeff(2)  & \\
req\mdash add\mdash term(3,2)  & \\
return(2)  & \\
req\mdash coeff(2)  & \\
return(2)  & \\
\end{array}
\]

Start with $(0, null, null, null)$:

\[
\begin{array}{ll}
req\mdash add\mdash term(4,2) & \\
req\mdash add\mdash term(7,1)  & \\
return(\mquote{OK})  & \\
req\mdash coeff(3)  & \\
req\mdash coeff(2)  & \\
return(0)  & \\
req\mdash coeff(1)  & \\
return(0)  & \\
req\mdash coeff(2)  & \\
return(4)  & \\
\end{array}
\]

Of course, there are many more traces. The important thing about this
system is that requests will be dropped if there is still a pending
request that has not generated a $return$ -- the value of $req$ will
not be $null$ when they come in.


}

  \problempart Describe in words an implementation of your state
  machine $\ms{ADP}$.  The state of this implementation should involve
  lower-level mathematical objects like numbers, matrices, sequences,
  etc.

\omitsolution{


% I do not really know what is adequate here!

  \medskip
  \textbf{Solution:} 

\begin{description}
\item[Using Arrays: ] Keep an array $poly$ such that the $i$th entry holds the
coefficient of $x^i$ in $p$. The array size will have to grow as necessary,
or there will be a limit on the terms of the polynomial. 
$comp\mdash add\mdash term(c,e)$ will simply be $poly[e] := poly[e] + c$.
$comp\mdash coeff(e)$ will be $req := poly[e]$.

\item[Using Ordered Pairs: ] Keep a set $terms$ of ordered pairs $(i, c)$ 
mapping the $i$th entry to the coefficient of $x^i$ in $p$.
$comp\mdash add\mdash term(c,e)$ will be more complex, unless we just add
the pair and sum all pairs with like first components on lookup. We will 
have to search through for an existing pair with a matching first component.
This will require more internal state. $comp\mdash coeff(e)$ will be a
similar search for the right pair, returning $0$ if none is found.

\end{description}


}

  \problempart Formalize your implementation as a labeled state
  machine $\ms{Imp}$.  It should have the same external labels as your
  labeled state machine $\ms{ADP}$.

\omitsolution{

  
  \medskip
  \textbf{Solution:} 

\begin{description}
\item[Using Arrays: ] Assume that we ignore the bounds of the array.

We need the following modifications to the abstract machine:
\begin{itemize}
\item $Q$: \\
For all (many) $i \in \nats$,  \\
$~\;\;\; poly[i] \in \ints $

$ req \in \set{\mquote{add\mdash term}, \mquote{find\mdash coeff}, null}
        \union \set{\mquote{OK}} \union \ints $

$ power \in \nats \union \set{null}  $

$ mult \in \ints \union \set{null}  $

\item $Q_0$: \\
A set with only one element:

$poly[i] = 0 \textrm{for all $i$}$, $req = null$, $power = null$, $mult = null$

\item $L$: Same as before.

\item $\delta$: Same as before for input and output. 
    \begin{itemize}
    \item $comp\mdash sum(c,e)$:  \\
        Can occur if $req = \mquote{add\mdash term}$, $mult = c$, and $power = e$. \\
        $~\;\;\;\; poly[e] := poly[e] + c$ \\
        $~\;\;\;\; req := \mquote{OK}$
    \item $comp\mdash coeff(e)$:  \\
        Can occur if $req = \mquote{find\mdash coeff}$ and $power = e$. \\
        $~\;\;\;\; req := poly[e]$
    \end{itemize}
\end{itemize}


\item[Using Unique Ordered Pairs: ]

We need the following modifications to the abstract machine:
\begin{itemize}
\item $Q$: \\
A linked list $terms$ of the form $(i, m, next)$
with $i \in \nats$, $m \in \ints$, $next \in terms \union \set{null}$.

$firstterm \in terms$

$curterm \in terms \union \set{null}$

$ req \in \set{\mquote{add\mdash term}, \mquote{find\mdash coeff}, null}
        \union \set{\mquote{OK}} \union \ints $

$ power \in \nats \union \set{null}  $

$ mult \in \ints \union \set{null}  $

\item $Q_0$: \\
A set with only one element:

$firstterm = (0, 0, null)$, $curterm = firstterm$,  $terms = \set{firstterm}$,
$req = null$, $power = null$, $mult = null$

\item $L$: Same as before for input and output labels.
    \begin{itemize}
    \item[] Internal labels:
        \begin{itemize}
        \item[] $comp\mdash sum(c,e)$, \ \ $c \in \ints, e \in \nats$
        \item[] $comp\mdash sum\mdash next(c,e)$, \ \ $c \in \ints, e \in \nats$
        \item[] $comp\mdash sum \mdash default(c,e)$, \ \ $c \in \ints, e \in \nats$
        \item[] $comp\mdash coeff(e)$, \ \ $e \in \nats$
        \item[] $comp\mdash coeff \mdash next(e)$, \ \ $e \in \nats$
        \item[] $comp\mdash coeff \mdash default(e)$, \ \ $e \in \nats$
        \end{itemize}
    \end{itemize}

\item $\delta$:  Input, output transitions same as before. 
    \begin{itemize}
    \item $comp\mdash sum(c,e)$:  \\
        Can occur if $req = \mquote{add\mdash term}$, $mult = c$, $power = e$,
        $curterm \neq null$, $curterm.i = e$ \\         
        $~\;\;\;\; curterm.m := curterm.m + c$ \\
        $~\;\;\;\; req := \mquote{OK}$ \\
        $~\;\;\;\; curterm := firstterm$
    \item $comp\mdash sum \mdash next(c,e)$:  \\
        Can occur if $req = \mquote{add\mdash term}$, $mult = c$, $power = e$,
        $curterm \neq null$, $curterm.i \neq e$ \\      
        $~\;\;\;\; curterm := curterm.next $ 
    \item $comp\mdash sum \mdash default(c,e)$:  \\
        Can occur if $req = \mquote{add\mdash term}$, $mult = c$, $power = e$,
        $curterm = null$ \\
        $~\;\;\;\; firstterm := (e, c, firstterm) $ \\
        $~\;\;\;\; req := \mquote{OK} $ \\
        $~\;\;\;\; curterm := firstterm$

    \item $comp\mdash coeff(e)$:  \\
        Can occur if $req = \mquote{find\mdash coeff}$, $power = e$,
        $curterm \neq null$, $curterm.i = e$ \\
        $~\;\;\;\; req := curterm.m$ \\
        $~\;\;\;\; curterm := firstterm$
    \item $comp\mdash coeff \mdash next(e)$:  \\
        Can occur if $req = \mquote{find\mdash coeff}$, $power = e$,
        $curterm \neq null$, $curterm.i \neq e$ \\      
        $~\;\;\;\; curterm := curterm.next $ 
    \item $comp\mdash coeff \mdash default(e)$:  \\
        Can occur if $req = \mquote{find\mdash coeff}$, $power = e$,
        $curterm = null$ \\     
        $~\;\;\;\; req := 0$ \\
        $~\;\;\;\; curterm := firstterm$

%    \item $return(\mquote{OK})$:  \\
%       Can occur if $req = \mquote{OK}$. \\
%        $~\;\;\;\; req, power, mult := null$ 
%    \item $return(c)$:  \\
%       Can occur if $req = c$. \\
%        $~\;\;\;\; req, power, mult := null$
    \end{itemize}
\end{itemize}

Note that we implicitly added a new term to $terms$ every time we
expanded the linked list.

\item[Using Multiple Ordered Pairs: ]

We need the following modifications to the abstract machine:
\begin{itemize}
\item $Q$: \\
A linked list $terms$ of the form $(i, m, next)$
with $i \in \nats$, $m \in \ints$, $next \in terms \union \set{null}$.

$firstterm \in terms$

$curterm \in terms \union \set{null}$

$total \in \ints$

$ req \in \set{\mquote{add\mdash term}, \mquote{find\mdash coeff}, null}
        \union \set{\mquote{OK}} \union \ints $

$ power \in \nats \union \set{null}  $

$ mult \in \ints \union \set{null}  $

\item $Q_0$: \\
A set with only one element:

$firstterm = (0, 0, null)$, $curterm = firstterm$,  $terms = \set{firstterm}$,
$total = 0$,
$req = null$, $power = null$, $mult = null$

\item $L$: Same as before for input and output labels.
    \begin{itemize}
    \item[] Internal labels:
        \begin{itemize}
        \item[] $comp\mdash sum(c,e)$, \ \ $c \in \ints, e \in \nats$
        \item[] $comp\mdash coeff(e)$, \ \ $e \in \nats$
        \item[] $comp\mdash coeff \mdash next(e)$, \ \ $e \in \nats$
        \item[] $comp\mdash coeff \mdash end(e)$, \ \ $e \in \nats$
        \end{itemize}
    \end{itemize}

\item $\delta$:  Input, output transitions same as before. 
    \begin{itemize}
    \item $comp\mdash sum(c,e)$:  \\
        Can occur if $req = \mquote{add\mdash term}$, $mult = c$, and $power = e$ \\
        $~\;\;\;\; firstterm := (e, c, curterm)$ \\
        $~\;\;\;\; req := \mquote{OK}$ 
    \item $comp\mdash coeff(e)$:  \\
        Can occur if $req = \mquote{find\mdash coeff}$, $power = e$,
        $curterm \neq null$, and $curterm.i = e$ \\
        $~\;\;\;\; total := total + curterm.m$ \\
        $~\;\;\;\; curterm := curterm.next $
    \item $comp\mdash coeff \mdash next(e)$:  \\
        Can occur if $req = \mquote{find\mdash coeff}$, $power = e$,
        $curterm \neq null$, and $curterm.i \neq e$ \\
        $~\;\;\;\; curterm := curterm.next $
    \item $comp\mdash coeff \mdash end(e)$:  \\
        Can occur if $req = \mquote{find\mdash coeff}$, $power = e$,
        and $curterm = null$ \\
        $~\;\;\;\; req := total$ \\
        $~\;\;\;\; curterm := firstterm$ \\
        $~\;\;\;\; total := 0$
%    \item $return(\mquote{OK})$:  \\
%       Can occur if $req = \mquote{OK}$. \\
%        $~\;\;\;\; req, power, mult := null$
%    \item $return(c)$:  \\
%       Can occur if $req = c$. \\
%        $~\;\;\;\; req, power, mult := null$
    \end{itemize}
\end{itemize}

\end{description}


}

  \problempart Argue that your implementation $\ms{Imp}$ is correct,
  in the sense that every trace of $\ms{Imp}$ is also a trace of
  $\ms{ADP}$.

\omitsolution{


  \medskip
  \textbf{Solution:} 

\begin{description}
\item[Using Arrays: ] This is the easiest.

        The abstraction function is obvious: All corresponding elements
have the same values and for every term $cx^i$ in $p$, $poly[i] = c$.
Only the to differing transitions are nontrivial to examine.
(Otherwise, the executions are identical and the abstraction function
is clearly preserved). However, even $comp\mdash sum$ and 
$comp\mdash coeff$ are easily accounted for: if an execution of
$Imp$ is extended by either, extend an execution of $ADP$ with the
same trace using the same transition. $comp\mdash sum$ preserves the
abstraction function by performing matching arithmetic.
$comp\mdash coeff$ preserves the abstraction function because $p$
and $poly$ are in correspondence and will set $req$ to the same value.

\item[Using Unique Pairs: ] Somewhat tricky to do formally.

        The abstraction function is: elements of the same name have the 
same values; every non-zero term in $p$ has exactly one corresponding
triplet in $terms$, and every zero-coefficient term in $p$ either has
no corresponding triplet or has a triplet with a second component of
$0$.

We need other elements of an invariant:
In $Imp$, $firstterm$ begins a linked list that reaches all terms in $terms$;
there are no terms with $i = mult$ `between' $firstterm$ and
$curterm$; no two terms have the same $i$ component; if $req$ is not
\mquote{find\mdash coeff} or \mquote{add\mdash term} 
then $curterm = firstterm$.

Input and output transitions have a simple identity correspondence.
Roughly, if the last transition of the partial execution of $Imp$ is:
\begin{itemize}
        \item[] $\mathbf{comp\mdash sum(c,e)}$ \\
                perform a $comp\mdash sum(c,e)$ transition. Both set $req$ to
                \mquote{OK}; the assignments keep the polynomial structures 
                aligned. (We use the fact that the IH tells us that no other 
                element of $terms$ represents the same exponent here). Although
                $req$ is changed, $curterm$ is set to $firstterm$. Nothing
                else is changed.
        \item[] $\mathbf{comp\mdash sum\mdash next(c,e)}$ \\
                do nothing. No data is changed, and the invariant holds over
                the change in $curterm$ because $i \neq mult$ for the old
                $curterm$.
        \item[] $\mathbf{comp\mdash sum \mdash default(c,e)}$ \\
                perform a $comp\mdash sum(c,e)$ transition. If there are no
                terms after $curterm$, and no terms with $i = mult$ between
                $firstterm$ and $curterm$, then there must be no terms at all
                with $i = mult$. So adding in the new term did not violate
                uniqueness. The new $firstterm$ is connected to all of the
                elements of $terms$ because the old $firstterm$ was.
        \item[] $\mathbf{comp\mdash coeff(e)}$ \\
                perform a $comp\mdash coeff(e)$ transition. Must be the correct
                coefficient because $p$ and $terms$ are in correspondence and
                no two terms have the same $i$ component.
        \item[] $\mathbf{comp\mdash coeff \mdash next(e)}$ \\
                do nothing.  No data is changed, and the invariant holds over
                the change in $curterm$ because $i \neq mult$ for the old
                $curterm$.
        \item[] $\mathbf{comp\mdash coeff \mdash default(e)}$ \\
                perform a $comp\mdash coeff(e)$ transition. If there are no
                terms after $curterm$, and no terms with $i = mult$ between
                $firstterm$ and $curterm$, then there must be no terms at all
                with $i = mult$. By the correspondence between $p$ and $terms$,
                the coefficient must be $0$ in both $ADP$ and $Imp$.
\end{itemize}

Although the steps are not filled in, the above is a basic reasoning
that traces of $Imp$ can be matched by traces of $ADP$.

\item[Using Multiple Pairs: ] Slightly trickier to do formally.

        The abstraction function is: elements of the same name have the 
same values; every term in $p$ has a coefficient equal to the sum of
$m$ in all triplets $(i, m, next)$ in $terms$ with $i$ equal to that
coefficient.

We need other elements of an invariant:
In $Imp$, $firstterm$ begins a linked list that reaches all terms in $terms$;
$total$ is the sum of $m$ in all triplets $(i, m, next)$ between 
$firstterm$ and $curterm$; if $req$ is not
\mquote{find\mdash coeff} then $curterm = firstterm$.

Input and output transitions have a simple identity correspondence.
Roughly, if the last transition of the partial execution of $Imp$ is:
\begin{itemize}
        \item[] $\mathbf{comp\mdash sum(c,e)}$ \\
                perform a $comp\mdash sum(c,e)$ transition. Both set $req$ to
                \mquote{OK}. The assignments keep the polynomial structures 
                aligned by adding in the new coefficient.
                The new $firstterm$ is connected to all of the
                elements of $terms$ because the old $firstterm$ was.
                Nothing else is changed.
        \item[] $\mathbf{comp\mdash coeff(e)}$ \\
                do nothing. $total$ is appropriately increased, since $curterm$
                is advanced beyond the term that is contributing.
        \item[] $\mathbf{comp\mdash coeff \mdash next(e)}$ \\
                do nothing.  No data is changed, and the invariant holds over
                the change in $curterm$ because $i \neq mult$ for the old
                $curterm$.
        \item[] $\mathbf{comp\mdash coeff \mdash end(e)}$ \\
                perform a $comp\mdash coeff(e)$ transition. If there are no
                terms after $curterm$, then all terms with $i = mult$ are between
                $firstterm$ and $curterm$. Thus, $total$ must be the proper
                coefficient of term $e$. Since $p$ and $terms$ are in correspondence,
                $Imp$ and $ADP$ will update $req$ to the same value.
\end{itemize}

\end{description}
        

}

\end{problemparts}



%END   Joe's problems

%BEGIN Ray's problems


%%%%%%%%%%%%%%%%%  S99 ps4



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\problem {\bf (15 points)} Suppose that the following procedure is used to
raise a real number $x$ to the non-negative integral power $y$.  
\begin{itemize}
\item Do the assignments $a := x, b := y, p := 1$.
\item Repeat the following steps:
  \begin{itemize}
  \item If $b$ is 0, output $p$ and terminate.
  \item If $b$ is even, do the assignment $a := a^2$ (that is, set the next
        value of $a$ to be the square of the current value), and also do
        $b := b/2$.
  \item If $b$ is odd, do $p := p \cdot a$ and $b := b - 1$.
  \end{itemize}
\end{itemize}

\begin{problemparts}
\problempart Model the procedure with a state machine.

\solution{
The state can be represented with a triple of numbers $a,b,p$:
\[Q = \{a, b, p\} \subset
(\reals \times \naturals \times \reals)
\]
The initial state is
\[
q_0 = (x,y,1)
\]
There are two transitions:
\begin{eqnarray*}
(a, b, p) &\rightarrow& (a^2, b/2, p) \,\,\mbox{ if $b$ is even and $b > 0$}
\\
(a, b, p) &\rightarrow& (a, b-1, ap) \,\,\mbox{ if $b$ is odd}
\end{eqnarray*}
The terminating condition is $b=0$, and then the state machine outputs~$p$.
}


\problempart Formulate an invariant relating $a, b, x, y$, and $p$ that
holds at the top of the loop.  Your invariant should imply that if
$b = 0$, then $p = x^y$.

\solution{
The invariant is expressed by the following predicate $P(\cdot)$ which
takes a state of the machine as an argument:
\[
P(a,b,p)=\mbox{``\,\,$a^bp=x^y$\,\,''}
\]
Note that if $b=0$ and $P(a,b,p)$ then $a^bp=p=x^y$.
}

\problempart Prove that the invariant holds.

\solution{
Clearly, $P(q_0)$ holds:
\[
P(q_0)=\mbox{``\,\,$(x^y)*1=x^y$\,\,''}
\]
Now, we show that if $P(q)$ and $(q,q')$ is a valid transition then
$P(q')$: 

Take some $q=(a,b,p)$ and assume $P(q)$, i.e. that $a^bp=x^y$.  $q'=(a',b',p')$
could be a state following $q$ if one of the two cases holds:
\begin{itemize}
\item 
If $b>0$ and $b$ even then $(a',b',p')=(a^2,b/2,p)$, and then
\[
(a')^{b'}p'=(a^2)^{(b/2)}p=a^bp=x^y
\]
where the last equation follows from $P(q)$.  Hence, in this case
$P(q')$ is true.
\item
If $b$ odd then $(a',b',p')=(a,b-1,ap)$, and then
\[
(a')^{b'}p'=a^{b-1}ap=a^bp=x^y
\]
where again, the last equation follows from $P(q)$.  Hence, in this case
$P(q')$ is true as well.
\end{itemize}
}


\problempart Prove that the procedure terminates.

\solution{
We need to show that $b$ always reaches $0$, because that's the
termination condition.  Let's argue the following facts:
\begin{enumerate}
\item 

It is an invariant of this state machine that $b$ is an integer.  It
starts as an integer $y$, and the two transitions preserve that: If
$b\in\integers$ and $b$ is even then $b/2\in\integers$.  Similarly,
if $b\in\integers$ then $(b-1)\in\integers$.

\item

$b$ cannot be a negative number.  We can show that by a contradiction:
If $b$ ever reached a negative number, since $b$ starts from a
nonnegative integer $y$, there must be a transition where $b$ went
below $0$, i.e. a transition from $b\geq{0}$ to $b'<0$.  But that's impossible
with our transitions:  
\begin{itemize}
\item
If $b\geq{0}$ then $b/2\not<{0}$
\item
If $b\geq{0}$ and $b\neq{0}$ then $b-1\not<0$.
\end{itemize}

\item

$b$ decreases in every transition (obviously, if $b>0$ than $b/2<b$
and $b-1<b$).
\end{enumerate}

Facts (1), (2) and (3) imply that $b$ must attain the value $b=0$ and
trigger the state machine to terminate.

Formally, it the the well-ordering principle that we use here: From
facts (1) and (2) it follows that for any execution of this state
machine, the set of values of variable $b$ is a subset of $\naturals$.
Therefore, from the well-ordering principle, it must have the smallest
element $b_0$.  Now from fact (3) we see that $b_0=0$ (or otherwise
$b_0$ could not be the smallest value attained by $b$, since if
$b\neq{0}$ then the next $b$ would be smaller).  Hence $b_0=0$ and so
the procedure must terminate.
}

\end{problemparts}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\problem {\bf (20 points)} A hungry ant is placed on an unbounded grid.
Each square of the grid either contains a crumb or is empty.  The squares
containing crumbs form a path in which, except at the ends, every crumb is
adjacent to exactly two other crumbs.  The ant is placed at one end of the
path and on a square containing a crumb.  For example, the figure below
shows a situation in which the ant faces North, and there is a trail
of food leading approximately Southeast.  The ant has already eaten
the crumb upon which it was initially placed.

\bigskip
\centerline{\resizebox{!}{2.0in}{\includegraphics{figs/ant.eps}}}
\bigskip

The ant can only smell food directly in front of it.  The ant can only
remember a small number of things, and what it remembers after any move
only depends on what it remembered and smelled immediately before the
move.  Based on smell and memory, the ant may choose to move forward one
square, or it may turn right or left.  It eats a crumb when it lands on
it.

%The ant sends a signal whenever it cannot smell food on all four adjacent squares.

The above scenario can be nicely modelled as a state machine in which each
state is a pair consisting of the ``ant's memory'' and ``everything
else,'' e.g., information about where things are on the grid.  Work out
the details of such a model state machine; design the ant-memory part of
the state machine so the ant will eat all the crumbs on \emph{any} finite
path at which it starts and then signal when it is done.  Be sure to
clearly describe the possible states, transitions, and inputs and outputs
(if any) in your model.  Briefly explain why your ant will eat all the
crumbs.

\solution{
If all the crumbs are placed as if ``on a string'', then the ant can
pick them all up very easily: If the ant smells no crumb in front of
it, it should turn in some fixed direction (say left), and if it does
smell a crumb, it should go forward and eat it.  Hence the ant can eat
all the crumbs of bread even if it is completely memory-less.
However, we requested that the ant-machine stops and signals {\em
done} when all the bread crumbs are eaten.  If the ant had no memory
than after eating the last crumb it would rotate indefinitely.
Therefore we should embed it with a memory of how many times it
rotated in the same spot in the search of an adjacent bread crumb.  If
the number of turns reaches four, all the bread crumbs are eated and
the ant can signal {\em done}.  Here is the state machine:
\begin{eqnarray*}
AntMemory &=& \{0,1,2,3,4\}
\\
BoardLocation &=& \naturals \times \naturals
\\
AntDirection &=& \set{N,E,W,S}
\\
Crumbs &\subseteq& BoardLocation
\\
AntLocation &=& BoardLocation
\\
Q &=& AntMemory \times (AntLocation \times AntDirection \times Crumbs)
\end{eqnarray*}

The transitions correspond to the three actions \{``go straight'',
``turn left'', ``done''\}.  We will use variables $q=(m,l,d,C)$ to
represent a state $q\in{Q}$ ($m\in{AntMemory}, l\in{AntLocation},
d\in{AntDirection}, C\in{Crumbs}$).  Let ${\sf Loc}(l,d)$ be a
function taking a location $l\in{AntLocation}$ and
$d\in{AntDirection}$ and returning $l'\in{AntLocation}$ s.t. $l'$ is a
location adjacent to $l$ in direction $d$.  In particular, if the ant
is in location $l$ and goes in direction $d$, it will come to location
$l'={\sf Loc}(l,d)$.  Let ${\sf Next}(d)$ be a function which picks
next direction of an ant which turns left, i.e. ${\sf Next}$ maps N to
W, W to S, S to E, and E to N.

\begin{itemize}
\item
{\sf go straight:}
$(m,l,d,C)\rightarrow(0,{\sf Loc}(l,d),d,C\setminus\{{\sf Loc}(l,d)\})$ if
${\sf Loc}(l,d)\in{C}$.
\item
{\sf turn left:} $(m,l,d,C)\rightarrow(m+1,l,{\sf Next}(d),C)$ if
${\sf Loc}(l,d)\not\in{C}$ and $m\neq{4}$.
\item
{\sf done:} If $m=4$, ant signals ``done''.
\end{itemize}
}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\problem {\bf (20 points)} A popular hand-held electronic game by Tiger 
Electronics called ``Lights Out'' is a $5\times5$ grid of buttons, each one
of which is either lighted or not.  The puzzle is to make all the
lights go out by pushing a sequence of buttons.  Pushing a button
toggles the state of the button pushed (lighted $\iff$ not lighted) and
all of its adjacent neighbors (not the diagonal neighbors).

The $5\times5$ game is a very large state machine involving millions
of states.  Thus let us consider instead the 3x3 game as shown:

\bigskip
\centerline{\resizebox{!}{2.0in}{\includegraphics{figs/lightsout.eps}}}
\bigskip

To win this game, we only need to press one button.  Pressing the top center
button will result in itself and the three neighbors turning off.

\begin{problemparts}
\problempart Describe this game as a state machine.  Don't draw every state;
             just describe the states and how you can move from one to another.

\solution{
The state of this game could be represented as a nine bit string
$s=s_1...s_9$, with one bit $b_i$ per each button, saying whether that
button is lit ($b_i=1$) or not lit ($b_i=0$).  There can be many
conventions, but here we will assume that $s_1s_2s_3$ are the top row
buttons, $s_4s_5s_6$ the middle row, and $s_7s_8s_9$ the bottom row,
all left to right.  From every state $s$ there are nine transitions,
one per each button that can be pressed.  Note that if there is a
transition from $s$ to $s'$ then there is a transition involving the
same button from $s'$ to $s$.  The transitions from
$s=s_1s_2s_3s_4s_5s_6s_7s_8s_9$ lead to:
\begin{eqnarray*}
\overline{s_1}\overline{s_2}s_3\overline{s_4}s_5s_6s_7s_8s_9
&& \mbox{if button 1 is pressed}\\
\overline{s_1}\overline{s_2}\overline{s_3}s_4\overline{s_5}s_6s_7s_8s_9
&& \mbox{if button 2 is pressed}\\
{s_1}\overline{s_2}\overline{s_3}s_4{s_5}\overline{s_6}s_7s_8s_9
&& \mbox{if button 3 is pressed}\\
\overline{s_1}{s_2}{s_3}\overline{s_4}\overline{s_5}s_6\overline{s_7}s_8s_9
&& \mbox{if button 4 is pressed}\\
\mbox{etc...}
\end{eqnarray*}
where $\overline{0}=1$ and $\overline{1}=0$.
}

\problempart How many states are there?

\solution{
Since each 9-bit string represents a state, there are $2^9=512$ possible states.
}

\problempart Suppose all nine buttons are lighted.  What is the fewest number
             of buttons we must push to make all nine go out?  Which buttons
             must we push?

\solution{
You can lit all buttons in 5 moves: pressing all corner
buttons (buttons 1,3,7 and 9) and the middle button (button 5).
}

\problempart Is every pattern of lights reachable?  Prove your answer. 

\solution{
Yes, because you can toggle each button individually:
\begin{itemize}
\item
The middle button can be toggled with all the other buttons remaining
in the same state by pressing the four buttons in the four edge
centers (2,4,6,8) and the middle button (5).
\item
Each corner button can be toggled without changing any other buttons
by pressing that corner button, the two adjacent corner buttons, and
the two buttons in the centers of the two edges not adjacent to the
given corner.  For example, to change button 1 individually, we press
buttons (1,3,7,6,8).
\item
Each edge button can be toggled individually by pressing the middle
button and all the three buttons on the opposite edge.  For example,
to change button 2, we press (5,7,8,9).
\end{itemize}
}

\end{problemparts}


%END   Ray's problems

%BEGIN Ivan's problems (spring '98)

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%pset4 problem1 spring98
\problem{\bf [10 points]} 

Consider a robot which wanders on a plane.  Our robot can move unit
distance along any diagonal line (that is at an angle of $\pm 45$ degrees or
$\pm 135$ degrees).  If our robot starts at point $(0,0)$, can it ever reach
the point $(1,1)$?  Prove your answer.

\solution{
It cannot reach $(1,1)$.  Let's model the robot's movements as a state
machine and find an invariant which is preserved by every move of the
robot.  The states are pairs of coordinates $(x,y)$, the initial state
is $(0,0)$ and there are four possible movements:
%
$$ (x,y) \,\,\leftarrow\,\,
(x\pm\frac{\sqrt{2}}{2},y\pm\frac{\sqrt{2}}{2}) $$
%
An invariant of every reachable state $(x,y)$ is that both $x$ and $y$
are integer multiples of ${\sqrt{2}}/{2}$.  It holds for the initial
state, and it is preserved by every move of our robot.  Therefore, the
machine can never reach a state $(1,1)$, as this state does not
satisfy the invariant.  If it did, i.e., if there was a natural number
$m$ s.t. $1=m\sqrt{2}/{2}$ then we would have that $\sqrt{2}={2}/{m}$,
and $\sqrt{2}$ would be a rational number.  Contradiction.
}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%pset4 problem2 spring98: part a is from ps4 in spring'97
\problem{\bf [20 points]} 

We are given two buckets, $A$ and $B$, a water hose, a receptacle, and a
drain.  The buckets and receptacle are initially empty.  The buckets are
labeled with their respectively capacities, positive integers $a$ and $b$.
The receptacle can be used to store an unlimited amount of water, but has
no measurement markings.  Excess water can be dumped into the drain.
Among the possible moves are:
\begin{enumerate}
\item\label{hose-bucket} fill a bucket from the hose,
\item pour from the receptacle to a bucket until the bucket is full
or the receptacle is empty, whichever happens first,
\item empty a bucket to the drain,
\item\label{bucket-receptacle} empty a bucket to the receptacle,
\item pour from $A$ to $B$ until either $A$ is empty or $B$ is full,
whichever happens first,
\item pour from $B$ to $A$ until either $B$ is empty or $A$ is full,
whichever happens first.
\end{enumerate}

\bparts 
\ppart{\bf [4 points]} 

Model this scenario with a state machine.  (What are the states?  How does
a state change in response to a move?)

\solution{
The states are triples $(x,y,z)$ which give the current amount of
water in the bucket $A$, bucket $B$, and the receptacle, respectively.
The initial state is $(0,0,0)$.

The moves make the following transitions:
\begin{enumerate}
\item fill a bucket from the hose
$$ (x,y,z) \rightarrow (a,y,z) \mbox{ or } (x,b,z)$$

\item pour from the receptacle to a bucket until the bucket is full
or the receptacle is empty, whichever happens first
$$ 
(x,y,z) \rightarrow \left \{ \begin{array}{l} 
(a,y,z-(a-x)) \mbox{ if pouring to A and } z \geq (a-x) \\
(x+z,y,0) \mbox{ if pouring to A and } z < (a-x) \\
(x,b,z-(b-y)) \mbox{ if pouring to B and } z \geq (b-y) \\
(x,y+z,0) \mbox{ if pouring to B and } z < (b-y) 
\end{array} \right.
$$

\item empty a bucket to the drain

$$ (x,y,z) \rightarrow (0,y,z) \mbox{ or } (x,0,z) $$

\item empty a bucket to the receptacle

$$ (x,y,z) \rightarrow (0,y,z+x) \mbox{ or } (x,0,z+y) $$

\item pour from $A$ to $B$ until either $A$ is empty or $B$ is full,
whichever happens first

$$ 
(x,y,z) \rightarrow \left \{ \begin{array}{l} 
(0,y+x,z) \mbox{ if } x < (b-y) \\
(x-(b-y),b,z) \mbox{ if } x \geq (b-y)
\end{array} \right.
$$

\item pour from $B$ to $A$ until either $B$ is empty or $A$ is full,
whichever happens first


$$ 
(x,y,z) \rightarrow \left \{ \begin{array}{l} 
(0,y+x,z) \mbox{ if } x < (b-y) \\
(x-(b-y),b,z) \mbox{ if } x \geq (b-y)
\end{array} \right.
$$
\end{enumerate}
}

\ppart{\bf [8 points]}\label{gcd-iff}

Prove that we can put $k\in\naturals$ gallons of water into the
receptacle using the above operations iff
$\mbox{gcd}(a,b) \mid k $.
\hint Use the fact that if $a,b$ are positive integers then there
exist integers $s,t$ such that $\mbox{gcd}(a,b)=sa+tb$.

\solution{
We need to prove two facts (the ``iff'' statement has two directions):
\begin{enumerate}
\item
If $\mbox{gcd}(a,b) \mid k $ then we can put $k$ gallons of water into
the receptacle.

\begin{proof}

Since there exist integers $s,t$ s.t.  $\mbox{gcd}(a,b)=sa+tb$, then
if $\mbox{gcd}(a,b) \mid k $ then there exists an integer $n$ s.t. $n
* \mbox{gcd}(a,b) = k$, and hence $n(sa+tb)=k$.  Assume without loss
of generality that $sa\geq{tb}$ (otherwise exchange the buckets in the
following argument).  Then we can fill the receptacle with $k$ gallons
if we first repeat $ns$ times moves $1$ and $4$, filling the $A$
bucket and pouring its content into the receptacle (note that if
$sa\geq{tb}$ then $s\geq{0}$).  With this series of moves we will get
from state $(0,0,0)$ to $(0,0,nsa)$.  Then, if $t=0$, we are already
done since $k=nsa$.  If $t>0$, we repeat $nt$ times moves $1$ and $4$
but now using the bucket $B$.  This gets us from $(0,0,nsa)$ to
$(0,0,nsa+ntb)=(0,0,k)$.  If $t<0$ we repeat $n*(-t)$ times moves $2$
and $3$ using the bucket $B$.  At the end of this series we will be in
state $(0,0,nsa-n*(-t)b)=(0,0,nsa+ntb)=(0,0,k)$
\end{proof}

\item
If we can put $k$ gallons of water into the receptacle then
$\mbox{gcd}(a,b) \mid k $.

\begin{proof}

We show that it is an invariant of our state machine that
$\mbox{gcd}(a,b)$ divides $x$, $y$ and $z$.  It will prove in
particular, that $z$ is always a multiple of $\mbox{gcd}(a,b)$

Let's denote $\mbox{gcd}(a,b)$ by $c$.  The invariant is preserved by
the initial state $(0,0,0)$.\footnote{Remember that $(x\mid
y)\iff(\exists_{b\in\integers}\,\,\,y=xb)$}.  Each move preserves this
invariant, because in each move the new values of $x,y$ or $z$ are
always integer linear combinations of the previous values $x,y,z$ or
$a,b$, i.e., they are expressed by a formula
$n_1x+n_2y+n_3z+n_4a+n_5b$ for some
$(n_1,n_2,n_3,n_4,n_5)\in\integers^5$.  For example in move 2, case 1,
the new value of $z$ is expressed by the above formula with
$(n_1,n_2,n_3,n_4,n_5)=(1,0,1,-1,0)$.  Since $c$ divides $a$ and $b$,
if $c$ divides $x,y,z$ before the move, it divides every such linear
formula, and hence it divides the values of $x,y$ and $z$ after each
move.
\end{proof}
\end{enumerate}
}

\ppart{\bf [8 points]} 

Let's restrict the valid moves to numbers~\ref{hose-bucket}
and~\ref{bucket-receptacle} only.  Prove that there exists a number $n$,
such that for all integer $k\geq n$, we can fill the receptacle with $k$
gallons of water iff $\mbox{gcd}(a,b) \mid k$.

\solution{
Again, pick $s,t$ s.t. $c=\mbox{gcd}(a,b)=sa+bt$.  If both
$s,t\geq{0}$ then $(s,t)=(0,1)$ or $(1,0)$, i.e., $a=b$ (check that in
all other cases $c$ would be greater than either $a$ or $b$, which is
impossible).  If $a=b$ then $c=a=b$, and for each $k\geq{c}$, $c\mid
k$, we can fill the receptacle by repeating moves $1$ and $4$
${k}/{c}\in\naturals$ times (with any bucket, since $a=b$).

Clearly it cannot be that both $s,t\leq0$ (or $c$ would be a
non-positive integer).  So we are left with two cases: $t<0<s$ or
$s<0<t$.  Assume without loss of generality that $t<0<s$.

We show that if $k\geq{n}$ for $n=-t{b^2}/{c}$, and $k$ is a
multiple of $c$, then we can fill the receptacle with $k$ gallons.
Let's denote $k$ as a multiple of $b$ plus a ``remainder'' in the
following way:
%
$$ k=k_1b+k_2c\mbox{, where
}k_1,k_2\in\naturals\,\,\wedge\,\,0\leq{k_2}<\frac{b}{c} $$
%
We can represent $k$ in this way since it is divisible by $c$.  Notice
also, that since $k\geq{-t{b^2}/{c}}$, then
$k_1\geq{-t{b}/{c}}$.  Since $c=sa+bt$, we can rewrite $k$ as
follows:
\begin{eqnarray*}
k&=&k_1b+k_2c
\\
&=&k_1b+k_2(sa+bt)
\\
&=&(k_2s)a+(k_1+k_2t)b
\end{eqnarray*}
Hence, as long as $k_1\geq{-t{b}/{c}}$, both $(k_2s)$ and $(k_1+k_2t)$
are non-negative integers.  And hence, we can fill the receptacle by
$(k_2s)$ times pouring bucket $A$ into it, and then $(k_1+k_2t)$ times
bucket $B$, both just with moves $1$ and $4$.
}

\eparts

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%pset4 problem3 spring98
\problem{\bf [25 points]} 

Consider the following game for two players.  The players alternate moves.
A move consists of a pair $(x,y)$ of natural numbers, subject to the
constraint that no move may be $\geq$ to any previous move in both
coordinates.  The player who makes the $(0,0)$ move is the loser.

At any point in the game, a valid move $(a,b)$ is said to be
\emph{bounded} iff both $a$ is bounded above by the $x$-coordinate of
some previous move and $b$ is bounded above by the $y$-coordinate of
some previous move.  For example, if the previous moves have been
$(1,3),(3,1), (2,2)$, then there are ten possible bounded moves:
$\{(1,2),(2,1),(1,1),(0,3),(0,2),(0,1),(0,0),(1,0),\\(2,0),(3,0)\}$.
There is also an infinite number of possible unbounded moves at this
point, namely, any move with one coordinate equal to $0$ and the other
larger than $3$.

For any state $S$ of the game after the first move, let $X(S)$ be the
minimum of the $x$-coordinates of the previous moves, $Y(S)$ be the
minimum of the $y$-coordinates, and $B(S)$ be the number of possible
bounded moves.  Define the \emph{measure}, $M(S)$, of the state to be the
triple $(X(S), Y(S), B(S))$.

Define the following ordering on triples of natural numbers:
\[(x,y,k) < (x',y',k') \iff [(x< x') \vee (x= x' \wedge
y < y') \vee (x=x' \wedge y = y' \wedge k < k')\]

\bparts

\ppart{\bf [10 points]} Prove that any nonempty subset of
$\naturals^3$ has a least element under the above ordering.

\solution{
Let $S$ be some nonempty subset of $\naturals^3$.  Let
$S_x=\{x\mid\exists_{y,z}\,\,(x,y,z)\in{S}\}$.  Then
$S_x\subset\naturals$, and so by the well-ordering principle, there is
a smallest element $x_{min}$ in $S_x$.  Now take a set
$S_{y}=\{y\mid\exists_{z}\,\,(x_{min},y,z)\in{S}\}$.  Since
$S_{y}\subseteq\naturals$, and it is not empty, it has a smallest
element $y_{min}$.  Similarly, the set
$S_{z}=\{z\mid(x_{min},y_{min},z)\in{S}\}$ has a smallest element
$z_{min}$.

Clearly, $(x_{min},y_{min},z_{min})$ is the smallest element in $S$.
If there was some smaller element $(x',y',z')$ in $S$, then:
\begin{itemize}
\item
If $x'<x_{min}$ then $x'\neq{x_{min}}$ would be the smallest element
in $S_x$.  Impossible.
\item
If $x'=x_{min}$ and $y'<y_{min}$ then $y'\neq{y_{min}}$ would be the
smallest element in $S_{y}$.  Impossible.
\item
If $x'=x_{min}$, $y'=y_{min}$ and $z'<z_{min}$ then $z'\neq{z_{min}}$
would be the smallest element in $S_z$.  Impossible.
\end{itemize}
}

\ppart{\bf [10 points]} Conclude that the game always terminates,
regardless of the players' strategy.

\solution{
We will show below that the measure $M(S)=(X(S),Y(S),B(S))$ is always
decreasing according to the ordering in $\naturals^3$ defined above.
On the other hand $M(S)$ cannot pass below $(0,0,0)$ because the
minimum x coordinate, the minimum y coordinate and the number of
bounded points cannot be negative.  Therefore the game has to
terminate.

Let's prove that measure $M(S)$ decreases with every move.  Assume by
contradiction that for some move leading from state $S=(x,y)$ to state
$S'=(x',y')$, we have that $M(S')\geq{M(S)}$.  There are three cases
in which ${M(S)}\leq{M(S')}$ could be true:
\begin{enumerate}
\item
$X(S)<X(S')$, which would mean that the minimum of the x-coordinates
has increased, which is impossible (the minimum of a set to which we
are adding some new element cannot increase).
\item
$X(S)=X(S')\,\wedge\,Y(S)<Y(S')$, which would mean that the minimum of
the y-coordinates has increased, which is impossible for the same
reason as above.
\item
$X(S)=X(S')\,\wedge\,Y(S)=Y(S')\,\wedge\,B(S)\leq{B(S')}$.  Let
$\{(x_1,y_1),\ldots,(x_n,y_n)\}$ be the points that were picked up to
move $S\,\rightarrow\,S'$ (i.e., the points that constitute state $S$),
and let $(x',y')$ be the new point.  If $X(S)=X(S')$ and $Y(S)=Y(S')$,
then $x'\geq\min_i\{x_i\}\,\wedge\,y'\geq\min_i\{y_i\}$.

We first show that $(x',y')$ must be a bounded point in state $S$.
Assume otherwise.  That would mean that either $x'$ or $y'$ were not
bounded in state $S$.  Without loss of generality, assume $x'$ was not
bounded, i.e., that $x'>{x_i}$ for all $i$.  On the other hand, we
know that $y'\geq{}y_j=\min_i\{y_i\}$.  But then $y_j\leq(y')$ and
$x_j<x'$ which would make $(x',y')$ an illegal move.  Hence $(x',y')$
must be a bounded point of state $S$.

Now we show that since $(x',y')$ is bounded in $S$, state
$S'=S\cup\{(x',y')\}$ must have fewer bounded points than $S$, i.e.,
that $B(S')<B(S)$.  This will finish the proof that
$X(S)=X(S')\,\wedge\,Y(S)=Y(S')\,\wedge\,B(S)\leq{B(S')}$ cannot be
true.  

Notice that a point $(x,y)$ is bounded in state $S=\{x_i,y_i\}$ iff it
is a valid move and $x\leq\max_S\{x_i\}$ and $y\leq\max_S\{y_i\}$.
Since, if $(x',y')$ is bounded in $S$ then the maximal x and y
coordinates do not change from $S$ to $S'$.  Consequently, if
$x\leq\max_{S'}\{x_i\}\,\wedge\,y\leq\max_{S'}\{y_i\}$ then
$x\leq\max_S\{x_i\}\,\wedge\,y\leq\max_S\{y_i\}$.  Also, if a point
$(x,y)$ is valid in $S'$, it is also valid in $S$ (it clearly follows
from the fact that $S\subset{S'}$).  From these two facts it follows
that if a point is bounded in $S'$, it is also bounded in $S$.  In
other words, the set ${\cal B}'$ of bounded points of $S'$ is a subset
of ${\cal B}$, the set of bounded points of $S$.  Since the latter is
a finite set\footnote{
%
After the first move, the set of bounded points is always finite,
because for whatever values $x_{max},y_{max}$, there are finite number
of pairs $(x,y)\in\naturals^2$ s.t. $x\leq{x_{max}}$ and
$y\leq{y_{max}}$.
%
} and ${\cal B}'\subset\{{\cal B}\setminus(x',y')\}$, it follows that
$B(S')=|{\cal B}'|<|{\cal B}|=B(S)$.
\end{enumerate}
This proves that measure $M(S)$ always decreases and hence finishes
the proof that the game always terminates.
}

\ppart{\bf [5 points]} Does any player have a winning strategy?
Prove your answer.

\solution{
The first player has two winning strategies:

\noindent
{\bf Strategy 1:} If the first player starts with $(1,1)$ then
whatever the second player picks, either $(0,n)$ or $(0,n)$ for some
$n$, the first player will respond with, respectively, $(n,0)$ or
$(0,n)$.  By symmetry, the first player will always have a move
whenever the second player had a move, except when the second player
picks $(0,0)$ and loses.

\noindent
{\bf Strategy 2:} The second winning strategy is slightly more tricky:
The first player starts by picking $(0,2)$,\footnote{Of course,
picking $(2,0)$ would be equivalent, and the following argument will
hold for it as well, with x and y coordinates replaced} and then:
\begin{itemize}
\item
If the 2nd player picks $(0,n)$ for any $n\geq{1}$, 1st player responds with
$(1,n-1)$.
\item
If the 2nd player picks $(1,n)$ for any $n\geq{0}$, 1st player
responds with $(0,n+1)$.
\end{itemize}
And the above procedure should be repeated for all consecutive moves.
Notice that if player 2 had a valid move, so does player 1, unless
player 2 picked $(0,0)$ and lost.

Furthermore, there are no other winning strategies for player 1,
because if she starts with any other legal move, player 2 will be able
to adopt either of the two winning strategies and win for sure:
\begin{itemize}
\item
If player 1 picks some $(m,n)$ where $m,n\geq{1}$ and
$(m,n)\neq(1,1)$, then player 2 can pick $(1,1)$ next, and then use
the first strategy to win against player 1.
\item
If player 1 picks some $(0,n)$ or $(n,0)$ where $n\geq{3}$, then
player 2 can respectively pick $(0,2)$ or $(2,0)$ next, and then use
the second strategy to win against player 1.
\item
If player 1 picks $(1,0)$ or $(0,1)$ then player 2 picks the other one
and wins.
\end{itemize}
}

\eparts

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%pset4 problem4 spring98
\problem{\bf [45 points]} 

The Stable Marriage Problem was described in lecture.  In this problem we
generalize slightly to handle ``bachelors.''  The setup is that there is a
finite number, not necessarily equal, of men and women; each man has a
strict (no ties) ranking of \emph{some} of the women according to his
preference.  The women on a man's list are said to be \emph{acceptable} to
him.  Likewise each woman has a ranking of the men who are acceptable to
her.

A \emph{marriage set} is a bijection (matching) between a subset of the men
and a subset of the women such that each man is matched to a woman he
finds acceptable, and each woman is matched to a man she finds acceptable.
In other words, a marriage set matches up men and women as ``husband'' and
``wife'' so that each man has exactly one wife, and each woman exactly one
husband.  Moreover, each wife is on her husband's list of ranked women,
and each husband is on his wife's list of ranked men.  Men and women not
in the marriage set are called \emph{bachelors}.

A husband in a marriage set is said to be \emph{tempted} by a woman if (1) he
prefers the woman to his wife, and (2) either the woman prefers him to her own
husband, or the woman is a bachelor who finds him acceptable.  Similarly,
a wife may be tempted by a man.  A marriage set is \emph{stable} iff no
husband is tempted by any woman and no wife is tempted by any man.

\bparts

\ppart{\bf [5 points]}
For all $n>1$, describe a set of $n$ men and $n$ women for whom there is
exactly one stable marriage set in which they are all married.

\solution{
One solution is to arrange preferences so that each woman is the
first-choice of exactly one man, and that man is also her first
choice.  It's easy to see that when a man and a woman have each other
as first choice, they will be a rogue couple unless they are married.

Another solution is to have all the men rank the women in the same
order, and all the woman rank the men in the same order.  In other
words, all the lists held by the women are the same, and so are the
lists held by the men.  It is as if there was an ``objective''
ordering of both men that all women share and vice versa.  Then the
first-choice man must marry the first-choice woman, after which the
second best man must marry the second woman, and so on.  If they do
not marry in this order then we can find the rogue couple as follows:
Let's $x_1,\ldots,x_n$ be the above ordering of men and
$y_1,\ldots,y_n$ be the ordering of women.  Take the first man $x_i$
who marries out of order ($i=\min\{k\mid x_k\mbox{ not married to
}y_k\}$).  Then $x_i$ must have married ``below his rank'', i.e., he is
married to $y_j$ where $j>i$ (because each woman $y_k$ for $k<i$ must
be married to man $x_k$, or man $x_i$ would not be the first who
married out of order).  The woman $y_i$ that was ``rightly his'', must
have married some man $x_m$ who is also ``below her status''
(otherwise, $x_m$ would be a man of a higher rank than $x_i$, who also
married out of order).  Notice that $x_i$ and $y_i$ form a rogue
couple.
}

\eparts

We can approach the Stable Marriage Problem with Bachelors using
essentially the same protocol as in lecture (the only difference is
the italicized phrase ``\emph{from a man she finds acceptable}''
below):

\subsubsection*{The Mating Algorithm}

The mating ritual takes place over several days.  The following events
happen each day:

{\bf Morning}: Each man who has not yet crossed all the women off his
rank list, ``proposes'' to the woman he most prefers among those remaining
on his list.

{\bf Afternoon}: Each woman who receives at least one proposal \emph{from
a man she finds acceptable}, says to her favorite suitor, ``Maybe\fourdots\
Come back tomorrow.''  To the other suitors, she says, ``Cross me off your
list.''  We say that on this afternoon, the woman is \emph{engaged} to the
man to whom she said ``Maybe\dots''  (Some women may not be engaged to
anybody on a given afternoon.)

{\bf Evening}: Each man who hears a ``Cross me off\dots'' message, crosses
the woman who gave him the message off his list.

{\bf Termination condition}: The algorithm terminates on the first
afternoon when every man who proposed to a woman that morning ends up
engaged to her in the afternoon.  Then all the engaged couples get
married.

\bparts

\ppart{\bf [5 points]}
Model the problem as a state machine.  State clearly what the states and
state transitions are.  What is the start state? 

\solution{
Just like in the original mating problem from the lecture, our state
machine is ${\cal M} = (Q, q_0, \delta)$.  States $Q$ are all possible
ways of crossing off girls' names on the boys' lists.  The starting
state $q_0$ is the state with no names crossed off on any list.  The
transitions $\delta$ lead from a state with a given set of boys' lists
to a set in which some boys (possible none or all) have the same
lists, and some have lists with the first girl crossed off.  

In fact the boys whose lists remain the same are of three kinds:
\begin{itemize}
\item
Those whose current list of girls is empty.
\item
Those whose current first girl does not appear as currently first on
any other boy's list.
\item
Those whose current first girl appears on other boys lists as first,
but these other boys are either unacceptable to this girl (not on her
list of boys at all), or they have lower ranks on her list.
\end{itemize}
\noindent
While the boys whose new lists have the first girl crossed off are of
two kinds:
\begin{itemize}
\item
Those who are not ranked on the list of boys of their current first
girl (they are unacceptable to their current first girls).
\item
Those whose current first girl appears on other boys lists as first,
and one of those other boys ranks higher on this girl's list.
\end{itemize}
}

\ppart{\bf [8 points]}
Use derived variables to prove termination.
How long does the protocol take to terminate?

\solution{
The same argument as in the original mating algorithm works here:

Let $f(q)$ be the number of uncrossed girl's names in state $q$.
Initially, every boy's list has at most $m$ uncrossed girl's names and
so $f(q_0) \leq mn$.  To prove that $f(q)$ is a decreasing derived
variable, we must show that for every execution $q_0, q_1, \ldots$, we
have $f(q_0) > f(q_1) > \ldots$.  For this purpose, it is sufficient
to show that $f(q) > f(q')$ for every transition $(q, q') \in \delta$.

In every transition $(q, q')$, since $q$ does not satisfy the
termination condition, we know that there is a man who proposes to
some girl on that morning and does not end up engaged to her in the
afternoon.  This could only happen if she told him ``Cross me
off\dots'' on that afternoon, and hence he will cross her off in the
evening.  But this means that $f(q)$ decreases by at least 1.

Notice also, that $f(q)\geq{0}$ for each $q$.  Therefore, since there
exists a decreasing derived variable $f(q)$ which take values in
natural numbers, starts from $f(q_0)\leq {mn}$, and is bounded from
below by $0$, the algorithm terminates within $nm$ steps.
}

\ppart{\bf [7 points]}
Prove that the marriage set at the end of the protocol is stable. 

\solution{
Again, the argument is the same as in the original mating algorithm:
We use the same derived variables:

\begin{itemize}

\item Let $f_i(q)$ be the original rank that boy $i$ assigned to the
girl he is proposing to in state $q$.  If the boy is not proposing to
anyone, the value of the variable is $m+1$.

\item Let $g_i(q)$ be the original rank that girl $i$ assigned to the
boy to whom she says ``Maybe\dots'' in state $q$.  If nobody is
proposing to her in state $q$, then the value of the variable is
$n+1$.

\end{itemize}

To prove the stability of the marriage set, we will need the following
facts about the derived variables $f_i(q)$ and $g_i(q)$:

{\bf Facts}
{\em
\begin{enumerate}

\item 
$f_i$ is a non-decreasing derived variable.  As a boy crosses off
names, the rank of the girl he proposes to increases; that is, he is
forced to pursue girls that he ranks lower.

\item 
$f_i$ is non-skipping.  Each boy crosses off at most one name each
day.

\item 
$f_i(q_0) = 1$.  Initially, each boy proposes to his favorite gal.

\item 
The preceding two facts together with the Non-Skipping Theorem imply
that if boy $i$ marries eventually, then he must have at some point
proposed to each girl that he ranked higher than his mate.

\item 
Similarly, if boy $i$ never marries, he must have at some point
proposed to each girl on his list.

\item $g_i$ is a non-increasing derived variable.  Each girl keeps
stringing along her top choice by saying ``Maybe'' (holding $g_i$
constant) until someone better comes along (decreasing $g_i$) or until
the algorithm terminates.

\end{enumerate}
}

We now show that the algorithm produces a stable marriage set.  Assume
for the purpose of contradiction that there is a rogue couple $B - G$.
Let $G'$ be the girl that married $B$, and let $B'$ be the boy who
married $G$.

Since $B - G$ is a rogue couple, $B$ must like $G$ better than $G'$.
Fact 4 implies that $B$ proposed to $G$ first.  However, she must have
said ``Cross me off\dots'' to him.  This, together with Fact 6,
implies that $G$ found someone she likes even better than $B$.  In
particular, this implies that $G$ likes $B'$ better than $B$.  But
this contradicts the assumption that $B - G$ is a rogue couple.
}

\ppart{\bf [5 points]} Suppose that no person is unacceptable to more than
one person of the opposite sex.  Show that there can be a situation in
which every stable marriage set leaves two bachelors of each sex.
\hint Find a situation involving exactly two men and two women.

\solution{
For example, take two men $M1,M2$ and two women $W1,W2$, and
sadistically set their preferences as follows:
\begin{itemize}
\item M1 accepts only W1
\item M2 accepts only W2
\item W1 accepts only M2
\item W2 accepts only M1
\end{itemize}
No mutually acceptable marriage is possible, hence the only stable
marriage set is an empty set.  Since it leaves two men and two women
unmarried, it is true that every stable marriage leaves two bachelors
of each sex.

Note that even though in every scenario an empty set is a stable
marriage set which also leaves {\em all} men and women unmarried, it
is not true for every scenario that {\em every} stable marriage set
has this property.
}

\ppart{\bf [8 points]}
Suppose that the number of women and men is the same, and that no
person is unacceptable to more than one person of the opposite sex.
Show that the protocol leads to a stable marriage set where at most
two men are bachelors.

\solution{
We first prove a helpful fact:\\
%
{\it If a man finds a woman acceptable and vice versa, then it cannot
be that both end up as bachelors.}

\begin{proof}
Suppose for contradiction that M and W are bachelors.  If M finds W
acceptable, he is either married to her or proposed to her at some
point (facts 4 and 5 in part 4d).  Since he is a bachelor now, he must
have proposed to her at some point, and she must have rejected him.
But since M is acceptable to her, she could have rejected him only
because there was some man she was engaged to at that time.  But once
a woman is engaged to somebody, she has to marry (not necessarily the
same person, but someone).  Hence we have a contradiction.
\end{proof}

Now assume that there are at least 3 bachelors of one sex, say men.
\begin{itemize}
\item
Since the number of men is equal to the number of women, if there are
3 male bachelors, there are 3 female bachelors.
\item
Pick a bachelor woman W1 (call the other two W2 and W3).  She must be
unacceptable to at most one of the bachelors.  Call the other two
bachelors, those that find W acceptable, M2 and M3.
\item
If W1 found either M2 or M3 acceptable, then she would not not end up
a bachelor (from the fact argued above, and because both M1 and M2 are
bachelors).  So she finds them unacceptable.
\item
Since no man can be unacceptable to more than one woman, woman W2
(same holds for W3) must find both M2 and M3 acceptable.
\item
Since no woman can be unacceptable to more than one man, W2 must be
acceptable to either M2 or M3 (same for W3).  Without loss of
generality say that M2 finds W2 acceptable.
\item
By the fact argued above, it cannot be that both M2 and W2 end up as
bachelors.
\end{itemize}
}

\ppart{\bf [7 points]}

Let's modify the mating algorithm above by introducing the following
change to the procedure for the Afternoon events.  On each afternoon, all
the women say ``Maybe\dots'' as before, but only one woman says ``Cross me
off your list'' and she says it to only one (but any one) among the
suitors she would have said it to in the protocol above.

In particular, on each afternoon at most one ``Cross me off your list'' is
spoken.  Notice that now the state of the men is no longer uniquely
determined by which afternoon it is.  Briefly indicate whether this
refined protocol always yields a stable final marriage set.  When there is
a final marriage set, is it necessarily the same as the one from the
original protocol?

\solution{
{\bf Q:} Does the new protocol always yield stable final marriage set?
\\ 
{\bf A:} Yes.  The same argument as in part 4c applies here to show
that the new one-at-a-time protocol terminates (it runs slower, but it
terminates eventually).  And also the same argument as in part 4d
applies here to show the one-at-a-time protocol leads to a stable
marriage set.  Notice that all the facts 1-6 from part 4d are still
true in the new protocol.

{\bf Q:} Is the final marriage set of the new protocol the same as the
one from the original protocol?
\\ 
{\bf A:} Yes.  The two protocols produce exactly the same marriage
sets, because both of them lead to a marriage set which is
man-optimal.  You can show that the morning-afternoon-evening protocol
is man-optimal in the same way as it is shown in the lecture notes
(theorem 2.9) for the original mating problem from the lecture.
Moreover, the same argument applies to the one-at-at-time protocol
presented here.  Since there is exactly one man-optimal matching
(every man marries the first woman on his list), the two protocols
find the same matchings.

\ignore{
Another way to argue that the one-at-a-time matching is the same as
that produced by the morning-afternoon-evening protocol, is to show
that it does not matter in what order the simultaneously possible
crossings-out are performed.  This argument would be more complicated,
and it would involve arguing the following fact:

If at some point, woman W1 can tell man M1 to cross her off his list,
and at the same time woman W2 can tell man M2 to cross her off, then
if either of these cross-out occurs, it will still be possible to do
the other one next.

% PROF. MEYER:
%I doubt that anyone will come up with this argument, so I won't finish
%spelling it out, but if you see anyone with reasoning along the line of
%this lemma, don't assume they're off the track.
}

}

\eparts

%END   Ivan's problems

%BEGIN George's problems
%%%%%%%%%%%%%%  Fall 2000  Problem Set 5   %%%%%%%%%%%%%%   %%%%%%%%%%%%%%%
\problem
% 1
% Puzzle state machine, modular arithmetic
In ancient times, the downtown section of Verona was laid out in a 1000
by 1000 meter square.  Romeo lived at grid point $(0,0)$ of the square, 
and Juliet lived at grid point $(0,1000)$.  Of course, Romeo and Juliet 
wanted to meet, at {\em exactly\/} the same point in the square.
However, both were restricted by their rather strange families to move
according to very particular rules:
Romeo could only move $3$ units, parallel to either the $x$ axis or $y$
axis or at a $45$ degree angle to both axes.
Juliet could only move $3$ units, and only parallel to either
the $x$ axis or $y$ axis.

\ppart
Model Romeo and Juliet and their possible moves as a (single) state
machine.  That is, define the states $Q$, the start state $Q_0$, and the
transitions $\delta$.

\solution{
\medskip
\textbf{Solution:}
\begin{description}
\item $Q = \{ (R_x, R_y, J_x, J_y) | R_x, R_y, J_x, J_y \in \{ 0,
\ldots, 1000 \} \}$, where $(R_x, R_y)$ and $(J_x, J_y)$ are the
positions of Romeo and Juliet, respectively.
\item $Q_0 = \{ (0, 0, 0, 1000) \}$
\item $\delta: (R_x, R_y, J_x, J_y)\rightarrow (R_x + 3a, R_y + 3b, J_x + 3c,
J_y + 3d))$, where \\
$(a, b, c, d) \in \{
(1,0,0,0),(-1,0,0,0),(0,1,0,0),(0,-1,0,0),(1,1,0,0),(1,-1,0,0),$\\
$(-1,1,0,0),(-1,-1,0,0),(0,0,1,0),(0,0,-1,0),(0,0,0,1),(0,0,0,-1) \}$
\end{description}
}

\ppart 
Can Romeo and Juliet meet by some sequence of moves?  If yes, then give
such a sequence of moves.  If no, then prove formally (using an
invariant) that no sequence of moves can yield a meeting.

\solution{
\medskip
\textbf{Solution:}
We show that for all reachable states $q = (R_x, R_y, J_x, J_y)$, 
$$R_x + R_y - J_x - J_y \equiv 2 \pmod{3}.$$
For notational convenience, let $r(q) = R_x + R_y - J_x - J_y$.  For the
only possible initial state $q_0$, $r(q_0) = -1000$, so $r(q_0) \equiv 2
\pmod{3}$.  For any transition from state $q$ to state $q'$, we note that
$r(q')-r(q)$ is always a multiple of 3. Hence $r(q') \equiv 2 \pmod{3}$
implies $r(q) \equiv 2 \pmod{3}$.  

Suppose, for a contradiction, that Romeo and Juliet 
can meet in some state $q$. That would imply that $r(q) = 0$.
However, we just showed that $r(q)$ can never be $0$, which yields a
contradiction.
}
          
%%%%%%%%%%%%%%  Fall 2000  Problem Set 5    %%%%%%%%%%%%%%   %%%%%%%%%%%%%%%

\problem
% 2
% Sequential algorithm
In the late 1960s, the military junta that ousted the government of the
small republic of Miranda outlawed multiplication and division by any
number other than $3$.  When democracy was reinstated 30 years later,
people were interested in rediscovering the lost art of multiplication.
A young inventor came up with the following algorithm to multiply any
two natural numbers $x$ and $y$ using only multiplication and division by
3:

\begin{tabbing}
XXX\=XXX\=XXX\=XXX\kill
{\bf procedure} {\it multiply}$(x, y$: natural numbers$)$ \\
$r:=x$; \\
$s:=y$; \\
$a:=0$;\\
{\bf do until} $s = 0$ \\
   \>{\bf if} $s \equiv 0 \pmod 3$ {\bf then} \\
   \>\>   $r := 3r$; \\
   \>\>   $s := s / 3$;\\
   \>{\bf else if} $s \equiv 1 \pmod 3$ {\bf then} \\
   \>\>   $a := a + r$; \\
   \>\>   $r := 3r$; \\
   \>\>   $s := (s - 1) / 3$; \\
   \>{\bf else} \\
   \>\>   $a := a + 2r$; \\
   \>\>   $r := 3r$; \\
   \>\>   $s := (s - 2) / 3$; \\
{\bf return} $a$; \\
\end{tabbing}

\ppart
Model the algorithm as a state machine $(Q, Q_0, \delta)$.

\solution{
\medskip
\textbf{Solution:}
\begin{description}
\item $Q=\{(r,s,a,x,y) | r,s,a,x,y\in \mathbb{N}\}$
\item $Q_0=\{(x,y,0,x,y)\}$
\item $\delta: (r,s,a,x,y)\rightarrow (3r,s',a',x,y)$, where \\
If $s \equiv 0 \pmod{3}$: $s'=s/3$, and $a'=a$ \\
If $s \equiv 1 \pmod{3}$: $s'=(s-1)/3$, and $a'=a+r$\\
If $s \equiv 2 \pmod{3}$: $s'=(s-2)/3$, and $a'=a+2r$
\end{description}
}

\ppart
List the sequence of steps that appears in the execution of the
algorithm for inputs $x = 5$ and $y = 10$.

\solution{
\medskip
\textbf{Solution:}
$(5, 10, 0, 5, 10) \rightarrow
(15, 3, 5, 5, 10) \rightarrow
(45 ,1, 5, 5, 10) \rightarrow
(135, 0, 50, 5, 10)$
}

\ppart
Prove that the algorithm gives the correct answer if it terminates, 
that is, that $s = 0$ implies $a = xy$. ({\em Hint}:  Use induction on 
the number of steps in the execution.  You will have to strengthen the 
inductive hypothesis.)

\solution{
\medskip
\textbf{Solution:}
We prove the following invariant.

$P(r,s,a,x,y) = ``xy = rs+a$''.

{\bf Base case: }
For any initial state we have $P(x,y,0,x,y)$ which is true.

{\bf Inductive step:} Consider a transition from $(r,s,a,x,y)$ to
$(r',s',a',x',y')$.  We need to prove that $P(r,s,a,x,y) \rightarrow
P(r',s',a',x',y')$.  We consider three cases:

If $s \equiv 0 \pmod{3}$, then 
$r's' + a' = (3r)\frac{s}{3} + a = rs + a = xy = x'y'.$

If $s \equiv 1 \pmod{3}$, then 
$r's' + a' = (3r)\frac{s-1}{3} + (a+r) = rs + a = xy = x'y'.$

If $s \equiv 2 \pmod{3}$, then 
$r's' + a' = (3r)\frac{s-2}{3} + (a+2r) = rs + a = xy = x'y'.$

In all three cases, the last equality was derived by applying the
inductive hypothesis, and in all cases $P(r',s',a',x',y')$ holds.
When $s=0$, the we get that $a=xy.$  We also know that the algorithm terminates
when $s=0$.  It follows, therefore, that if the algorithm terminates,
then the correct answer is produced.
}

\ppart
Prove that the algorithm terminates.

\solution{
\medskip
\textbf{Solution:}

We first notice that $s\geq 0$ for any reachable
execution state.  We prove that this is an invariant by showing
it is true for the base case, $y\geq 0$, and furthermore, no
transition exists from a state with $s\geq 0$ to $s<0$ in all
cases.

Now consider the value of $s$ during any valid execution.  Since
$s\geq 0$, as shown above, no transition increases $s$.  Furthermore,
for $s>0$, all transitions decrease $s$ by at least 1.  Thus for any
values of $x,y\in \mathbb{N}$, $s$ decreases to 0 in a finite number
of steps, and thus the program terminates in a finite number of steps.
}
           
%%%%%%%%%%%%%%  Fall 2000  Problem Set 5    %%%%%%%%%%%%%%   %%%%%%%%%%%%%%%
\problem
% 3
% State machine, tricky representation, tricky invariants
Shah Shahryar's wife betrays him with a slave and he vows revenge on all
women.  Each night, he will marry a new bride and the next morning have
her beheaded.  One night comes beautiful Sheherezade and presents the
Shah with a game:  

You have three numbers: 1, 1 and 2.  At each time, you are allowed to
replace any two numbers $x$, $y$ with $\frac{x+y}{\sqrt{2}}$,
$\frac{x-y}{\sqrt{2}}$, but you must not change your third number.  You
will win only if, using this rule, you can obtain the numbers $a$, $b$
and $c$.

\ppart Model Sheherezade's game as a state machine. ({\em Note}: The
representation is a little tricky because the numbers are not ordered.)

\solution{
\medskip
\textbf{Solution:}
\begin{description}
\item $Q = \mathbb{R}^3$
\item $Q_0 = \{ (1,1,2) \}$
\item $\delta:$
$(x,y,z) \rightarrow (\frac{x+y}{\sqrt{2}},\frac{x-y}{\sqrt{2}},z)$ or
$(x,y,z) \rightarrow (x',y',z')$, where $(x', y', z')$ is a permutation
of $(x,y,z)$.
\end{description}
}

For each of the following choices of $a$, $b$ and $c$, say whether or
not the Shah can win the game.  If yes, show a sequence of winning
steps.  If no, provide a proof using an invariant.

\ppart 
$(a,b,c) = (\frac{3 \sqrt{2}}{2}, \frac{\sqrt{2} + 1}{2},
\frac{\sqrt{2} - 1}{2})$ 

\solution{
\medskip
\textbf{Solution:}
Yes. 
$(1,1,2) \rightarrow (2,1,1) \rightarrow $
$(\frac{3 \sqrt{2}}{2}, \frac{\sqrt{2}}{2},1) \rightarrow $  
$(\frac{3 \sqrt{2}}{2}, \frac{\sqrt{2} + 1}{2}, \frac{\sqrt{2} - 1}{2})$.
}

\ppart 
$(a, b, c) = (\frac{\sqrt{3} - 1}{2}, \frac{\sqrt{3} + 1}{2}, 7)$

\solution{
\medskip
\textbf{Solution:}
No.  The predicate

$$P(x,y,z) : x, y, z \in \{ p + q\sqrt{2} | p, q \in \mathbb{Q} \}$$

is an invariant for the state machine.  For the base case and the
permutation transitions, the claim is evident. For the transitions of
type $(x,y,z) \rightarrow (x',y',z')$ where 
$(x',y',z') = (\frac{x+y}{\sqrt{2}},\frac{x-y}{\sqrt{2}},z)$, let
$x=p+q\sqrt{2}, y=r+s\sqrt{2}, z=u+v\sqrt{2}$.  Then 
$x' = 2(q+s) + (p+r)\sqrt{2}, y' = 2(q-s) + (p-r)\sqrt{2}, z' = z$, so 
$P(x,y,z) \rightarrow P(x',y',z')$.
Since $P(\frac{\sqrt{3} - 1}{2}, \frac{\sqrt{3} + 1}{2}, 7)$ is false,
this state is not reachable.
}

\ppart 
$(a, b, c) = (1, 2, 2)$


\solution{
\medskip
\textbf{Solution:}
No.  The predicate

$$P(x,y,z) : x^2 + y^2 + z^2 = 6$$

is an invariant for the state machine.  For the base case and the
permutation transitions, the claim is evident again.  For the
transitions of type 
$(x,y,z) \rightarrow (\frac{x+y}{\sqrt{2}},\frac{x-y}{\sqrt{2}},z)$,
we have $x^2 + y^2 + z^2 = (\frac{x+y}{\sqrt{2}})^2 +$ 
$(\frac{x-y}{\sqrt{2}})^2 + z^2$.  Since $P(1,2,2)$ does not hold, the
state $(1,2,2)$ is not reachable.
}
                      
%%%%%%%%%%%%%%  Fall 2000   Problem Set 5   %%%%%%%%%%%%%%   %%%%%%%%%%%%%%%
\problem
% 4
% Matching, intuition
Consider the matching problem from lecture.

\ppart
For a particular value of $n$, give an example of a stable match between $n$
boys and $n$ girls where no person gets their first choice.

\solution{
\medskip
\textbf{Solution:}

Let $n=3$.  Call the boys $1, 2, 3$ and the girls $a, b, c$.  Consider
the following preference list:

\begin{center}
\begin{tabular}{llll||llll} \hline
choice& 1st& 2nd& 3rd& choice& 1st& 2nd& 3rd \\ \hline
1& a& b& c& a& 2& 3& 1 \\
2& b& c& a& b& 3& 1& 2 \\
3& c& a& b& c& 1& 2& 3 \\ \hline
\end{tabular}
\end{center}
   
The matching $(1, b), (2, c), (3, a)$ is stable even though no person
gets their first choice.
}


\ppart
Can a stable match where no person gets their first choice be produced
by the matching algorithm described in class?  If yes, state an example
and show why the example works.  If not, prove using an invariant.

\solution{
\medskip
\textbf{Solution:}

Yes. For $n=4$, for boys $1, 2, 3, 4$ and the girls $a, b, c, d$, the
following preference list yields such a match (x choices don't matter):

\begin{center}
\begin{tabular}{lllll||lllll} \hline
choice& 1st& 2nd& 3rd& 4th& choice& 1st& 2nd& 3rd& 4th \\ \hline
1& a& c& x& x& a& 3& 2& 1& 4 \\
2& b& a& x& x& b& 1& 4& 3& 2 \\
3& b& d& x& x& c& x& 1& x& x \\
4& a& b& x& x& d& x& 3& x& x \\ \hline
\end{tabular}
\end{center}

The matching algorithm executes as follows:

\begin{description}
\item[Round 1] $a$ picks $1$. $b$ picks $3$. $2, 4$ are dropped.
\item[Round 2] $a$ picks $2$. $b$ picks $4$. $1, 3$ are dropped.
\item[Round 3] $c$ picks $1$. $d$ picks $3$.
\end{description}
}
                 
%%%%%%%%%%%%%%  Fall 2000  Problem Set 5    %%%%%%%%%%%%%%   %%%%%%%%%%%%%%%
\problem
% 5
% Matching, invariant
Consider an instance of the matching problem with $n$ boys and $n$
girls.  Call a person {\em unlucky} if he or she is matched up with
one of his or her $\floor{\frac{n}{2}}$ last choices.  In this
problem, we will prove the following: 
 
{\bf Theorem}  The matching algorithm from class never produces a
matching in which every person is unlucky.

Fix an execution of the matching algorithm.  Define the variables 
$B_i, G_i, i \in \{ 1, 2, \ldots, n \}$ as follows:
\begin{description}
\item $B_i = j$ if the $i$-th boy is currently courting the $j$-th girl
on his list
\item $G_i$ is the number of boys that the $i$-th girl has rejected.
\end{description}

\ppart
Show that $\sum_{i=1} ^n B_i - \sum_{i=1} ^n G_i$ is preserved at each
step of the matching algorithm.

\solution{
\medskip
\textbf{Solution:}
Let $S = \sum_{i=1} ^n B_i - \sum_{i=1} ^n G_i$.  Suppose that at step
$t$, boy $b_i$ proposes to girl $g_j$.  There are three possible outcomes:

If $g_j$ has not had any previous proposals, she must accept.  In this
case, none of the $B_i$s and none of the $G_j$s change, so $S$ is preserved.

If $g_j$ rejects, then $G_j$ increases by 1, $B_i$ increases by 1, and
the other $B$s and $G$s remain the same.  $S$ is preserved again.

If $g_j$ accepts $b_i$ because she likes him better than her current
mate $b_{i'}$, then $G_j$ increases by 1, $B_{i'}$ increases by 1, and
the other $B$s and $G$s remain the same.  $S$ is preserved in this case
as well.
}

\ppart
Formulate an invariant that you can use to prove the theorem, and 
show that your invariant is correct.

\solution{
\medskip
\textbf{Solution:}
Let $P : S = n$.  In the initial state, this is true because everyone is
courting the first girl on their list.  From part (a) it follows that
all transitions preserve the truth value of $P$.  Therefore $P$ is an
invariant.
}

\ppart
Use your invariant to prove the theorem.

\solution{
\medskip
\textbf{Solution:}
We prove the statement by contradiction.  Consider a match M in which
every person is unlucky.  Then:
\begin{description}
\item For every $i \in \{ 1, \ldots, n \}$, 
$B_i \geq \ceil{\frac{n}{2}} + 1$, and
\item For every $i \in \{ 1, \ldots, n \}$,
$G_i \leq \floor{\frac{n}{2}} - 1$.
\end{description}

It follows that $\sum_{i=1} ^n B_i - \sum_{i=1} ^n G_i \geq 2n$.  This
violates the invariant $P$.
}  
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%END   George's problems

%BEGIN Josh's problems
%END   Josh's problems

%BEGIN Tina's problems
% fall 99
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%pset 6, #2
\problem \textbf{Terminating games}
% taken from spring 98

Consider the following game for two players.  The players alternate
moves.  A move consists of a pair $(x,y)$ of natural numbers, subject
to the constraint that no move may be $\geq$ to any previous move in
both coordinates.  The player who makes the $(0,0)$ move is the loser.

\bparts 

\ppart Identify a winning strategy for the first player, and argue its
correctness.

\solution{
The first player has two winning strategies:

\noindent
{\bf Strategy 1:} If the first player starts with $(1,1)$ then
whatever the second player picks, either $(0,n)$ or $(0,n)$ for some
$n$, the first player will respond with, respectively, $(n,0)$ or
$(0,n)$.  By symmetry, the first player will always have a move
whenever the second player had a move, except when the second player
picks $(0,0)$ and loses.

\noindent
{\bf Strategy 2:} The second winning strategy is slightly more tricky:
The first player starts by picking $(0,2)$,\footnote{Of course,
picking $(2,0)$ would be equivalent, and the following argument will
hold for it as well, with x and y coordinates replaced} and then:
\begin{itemize}
\item
If the 2nd player picks $(0,n)$ for any $n\geq{1}$, 1st player responds with
$(1,n-1)$.
\item
If the 2nd player picks $(1,n)$ for any $n\geq{0}$, 1st player
responds with $(0,n+1)$.
\end{itemize}
And the above procedure should be repeated for all consecutive moves.
Notice that if player 2 had a valid move, so does player 1, unless
player 2 picked $(0,0)$ and lost.

Furthermore, there are no other winning strategies for player 1,
because if she starts with any other legal move, player 2 will be able
to adopt either of the two winning strategies and win for sure:
\begin{itemize}
\item
If player 1 picks some $(m,n)$ where $m,n\geq{1}$ and
$(m,n)\neq(1,1)$, then player 2 can pick $(1,1)$ next, and then use
the first strategy to win against player 1.
\item
If player 1 picks some $(0,n)$ or $(n,0)$ where $n\geq{3}$, then
player 2 can respectively pick $(0,2)$ or $(2,0)$ next, and then use
the second strategy to win against player 1.
\item
If player 1 picks $(1,0)$ or $(0,1)$ then player 2 picks the other one
and wins.
\end{itemize}
}

\eparts

At any point in the game, a valid move $(a,b)$ is said to be
\emph{bounded} iff both $a$ is bounded above by the $x$-coordinate of
some previous move and $b$ is bounded above by the $y$-coordinate of
some previous move.  For example, if the previous moves have been
$(1,3),(3,1), (2,2)$, then there are ten possible bounded moves:
$\{(1,2),(2,1),(1,1),(0,3),(0,2),(0,1),(0,0),(1,0),\\(2,0),(3,0)\}$.
There is also an infinite number of possible unbounded moves at this
point, namely, any move with one coordinate equal to $0$ and the other
larger than $3$.

For any state $S$ of the game after the first move, let $X(S)$ be the
minimum of the $x$-coordinates of the previous moves, $Y(S)$ be the
minimum of the $y$-coordinates, and $B(S)$ be the number of possible
bounded moves.  Define the \emph{measure}, $M(S)$, of the state to be the
triple $(X(S), Y(S), B(S))$.

Define the following ordering on triples of natural numbers:
\[(x,y,k) < (x',y',k') \iff [(x< x') \vee (x= x' \wedge
y < y') \vee (x=x' \wedge y = y' \wedge k < k')\]

\bparts

\ppart Prove that any nonempty subset of
$\naturals^3$ has a least element under the above ordering.

\solution{
Let $S$ be some nonempty subset of $\naturals^3$.  Let
$S_x=\{x\mid\exists_{y,z}\,\,(x,y,z)\in{S}\}$.  Then
$S_x\subset\naturals$, and so by the well-ordering principle, there is
a smallest element $x_{min}$ in $S_x$.  Now take a set
$S_{y}=\{y\mid\exists_{z}\,\,(x_{min},y,z)\in{S}\}$.  Since
$S_{y}\subseteq\naturals$, and it is not empty, it has a smallest
element $y_{min}$.  Similarly, the set
$S_{z}=\{z\mid(x_{min},y_{min},z)\in{S}\}$ has a smallest element
$z_{min}$.

Clearly, $(x_{min},y_{min},z_{min})$ is the smallest element in $S$.
If there was some smaller element $(x',y',z')$ in $S$, then:
\begin{itemize}
\item
If $x'<x_{min}$ then $x'\neq{x_{min}}$ would be the smallest element
in $S_x$.  Impossible.
\item
If $x'=x_{min}$ and $y'<y_{min}$ then $y'\neq{y_{min}}$ would be the
smallest element in $S_{y}$.  Impossible.
\item
If $x'=x_{min}$, $y'=y_{min}$ and $z'<z_{min}$ then $z'\neq{z_{min}}$
would be the smallest element in $S_z$.  Impossible.
\end{itemize}
}

\ppart Conclude that the game always terminates,
regardless of the players' strategy.

\solution{
We will show below that the measure $M(S)=(X(S),Y(S),B(S))$ 
decreases with every move
according to the ordering in $\naturals^3$ defined above.
%On the other hand $M(S)$ cannot pass below $(0,0,0)$ because the
%minimum x coordinate, the minimum y coordinate and the number of
%bounded points cannot be negative.  
%Therefore the game has to
%terminate.

Assume by
contradiction that for some move leading from state $S=(x,y)$ to state
$S'=(x',y')$, we have that $M(S')\geq{M(S)}$.  There are three cases
in which ${M(S)}\leq{M(S')}$ could be true:
\begin{enumerate}
\item
$X(S)<X(S')$, which would mean that the minimum of the x-coordinates
has increased, which is impossible (the minimum of a set to which we
are adding some new element cannot increase).
\item
$X(S)=X(S')\,\wedge\,Y(S)<Y(S')$, which would mean that the minimum of
the y-coordinates has increased, which is impossible for the same
reason as above.
\item
$X(S)=X(S')\,\wedge\,Y(S)=Y(S')\,\wedge\,B(S)\leq{B(S')}$.  Let
$\{(x_1,y_1),\ldots,(x_n,y_n)\}$ be the points that were picked up to
move $S\,\rightarrow\,S'$ (i.e., the points that constitute state $S$),
and let $(x',y')$ be the new point.  If $X(S)=X(S')$ and $Y(S)=Y(S')$,
then $x'\geq\min_i\{x_i\}\,\wedge\,y'\geq\min_i\{y_i\}$.

We first show that $(x',y')$ must be a bounded point in state $S$.
Assume otherwise.  That would mean that either $x'$ or $y'$ were not
bounded in state $S$.  Without loss of generality, assume $x'$ was not
bounded, i.e., that $x'>{x_i}$ for all $i$.  On the other hand, we
know that $y'\geq{}y_j=\min_i\{y_i\}$.  But then $y_j\leq(y')$ and
$x_j<x'$ which would make $(x',y')$ an illegal move.  Hence $(x',y')$
must be a bounded point of state $S$.

Now we show that since $(x',y')$ is bounded in $S$, state
$S'=S\cup\{(x',y')\}$ must have fewer bounded points than $S$, i.e.,
that $B(S')<B(S)$.  This will finish the proof that
$X(S)=X(S')\,\wedge\,Y(S)=Y(S')\,\wedge\,B(S)\leq{B(S')}$ cannot be
true.  

Notice that a point $(x,y)$ is bounded in state $S=\{x_i,y_i\}$ iff it
is a valid move and $x\leq\max_S\{x_i\}$ and $y\leq\max_S\{y_i\}$.
Since, if $(x',y')$ is bounded in $S$ then the maximal x and y
coordinates do not change from $S$ to $S'$.  Consequently, if
$x\leq\max_{S'}\{x_i\}\,\wedge\,y\leq\max_{S'}\{y_i\}$ then
$x\leq\max_S\{x_i\}\,\wedge\,y\leq\max_S\{y_i\}$.  Also, if a point
$(x,y)$ is valid in $S'$, it is also valid in $S$ (it clearly follows
from the fact that $S\subset{S'}$).  From these two facts it follows
that if a point is bounded in $S'$, it is also bounded in $S$.  In
other words, the set ${\cal B}'$ of bounded points of $S'$ is a subset
of ${\cal B}$, the set of bounded points of $S$.  Since the latter is
a finite set\footnote{
%
After the first move, the set of bounded points is always finite,
because for whatever values $x_{max},y_{max}$, there are finite number
of pairs $(x,y)\in\naturals^2$ s.t. $x\leq{x_{max}}$ and
$y\leq{y_{max}}$.
%
} and ${\cal B}'\subset\{{\cal B}\setminus(x',y')\}$, it follows that
$B(S')=|{\cal B}'|<|{\cal B}|=B(S)$.
\end{enumerate}
This proves that measure $M(S)$ always decreases and hence finishes
the proof that the game always terminates.
}
\eparts
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% pset 6, #4
\problem {\bf Linked lists}

You are given a one-way linked list with starting link $l_0$.  For any
link, $l$, we let $S(l)$ denote the next link in the list after $l$. If
$S(l) = \texttt{NULL}$, then link $l$ is the last link on the list.  But
the list may link back to itself (that is, it may be that $S(l_1)=S(l_2)$
for some links $l_1 \neq l_2$), in which case there is no last link
because the list ends in a cycle.  To determine whether or not there is a
cycle, you could follow the links down the list recording the links
encountered while checking to see if a link is ever revisited, but this
could take a lot of memory and time.  So you use the following procedure
to detect cycles:

\begin{verbatim}
a := l_0;
b := l_0;
while ((S(a) != NULL) and (S(b) != NULL) and (S(S(b)) != NULL))
{
    a := S(a);
    b := S(S(b));
    if a = b
        return "CYCLE"
};
return "NO CYCLE"
\end{verbatim}

\noindent
Prove that this procedure terminates and produces the correct answer.

\solution{ If the list has no cycles, then within $n/2$ steps, where $n$
is the length of the list, either \texttt{S(b)} or \texttt{S(S(b))} will
be \texttt{NULL}, so the process will break from the while loop and return
\texttt{NO CYCLE}.

\hspac
\noindent
If the list does contain a cycle, then eventually both markers \texttt{a}
and \texttt{b} will be stuck in the cycle.  Let $d_j$ denote the distance
measured clockwise from \texttt{b} to \texttt{a} at the $j^{th}$ execution
of the while loop.  (Assume the markers are moving around the cycle in the
clockwise direction.) If $d_j$ = 0, then \texttt{a} = \texttt{b}, so the
process terminates and outputs \texttt{CYCLE}.  Otherwise, note that at
each execution of the while loop, this distance decreases by exactly one,
so after $d_j$ steps, the process outputs \texttt{CYCLE} and terminates.
}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% pset 6 #5

\problem{\bf Mystery Problem}

Given a list of numbers $A[1], \dots,A[n]$, sorted in increasing order,
and a number $a$, consider the following procedure which takes as
arguments natural numbers $i,j \in \set{1,\dots,n}$ such that $i \leq j$:

\begin{verbatim}
Proc(i, j):
    start  := i;
    end    := j;
    middle := start + quotient((end - start)/2);
    if A[middle] = a
        return middle;
    if (start = middle)
        return "NOT FOUND";
    if A[middle] > a
        Proc(start, middle)
    else
        Proc(middle+1, end)
\end{verbatim}

\noindent
What does $\mbox{\texttt{Proc}}(i, j)$ do?  Prove your answer.
Note that {\tt start}, {\tt middle}, and {\tt end} are always integers.

\solution{

If $a$ is in the list, say $a= A[k]$, then $\mbox{\texttt{Proc}}(1,n)$
returns $k$.  If $a$ is not in the list, then $\mbox{\texttt{Proc}}(1,n)$
returns \texttt{NOT FOUND}.

To prove this, we prove more generally that for any $1 \leq i \leq j \leq
n$, if $a$ is in the list $A[i],\dots,A[j]$---say $a= A[k]$---then
$\mbox{\texttt{Proc}}(i,j)$ returns $k$.  And if $a$ is not in the list
$A[i],\dots,A[j]$, then $\mbox{\texttt{Proc}}(i,j)$ returns \texttt{NOT
FOUND}.  The proof is by induction on the value of $j-i$.

If $j-i = 0$, that is $j = i$, then in the call
$\mbox{\texttt{Proc}}(i,j)$, the initial value of \texttt{middle} will be
$i$, and the call will return $i$ or \texttt{NOT FOUND} according to
whether $a = A[i]$, that is, whether $a$ is in the list $A[i]$.  So in the
base case, the call behaves according to thte hypothesis.

Now suppose $j-i > 0$.  In the call $\mbox{\texttt{Proc}}(i,j)$, let $k$
be the initial value of \texttt{middle}.  From the assignment which
defines the initial value of \texttt{middle}, we conclude that $i\leq k <
j$.  If $a = A[k]$, then the call will return $k$; but in this case, $a$
is indeed in the list $A[i],\dots,A[j]$, so this is the return behavior
specified by the induction hypothesis for $j-i$.  Next, if $A[k]>a$, then
the call of $\mbox{\texttt{Proc}}(i,j)$ will return the same result as the
call $\mbox{\texttt{Proc}}(i,k)$.  But now $k-i < j - i$ so by induction,
this call returns the index of $a$ if $a$ is in the list $A[i], \dots,
A[k]$, and returns \texttt{NOT FOUND} otherwise.  But since $A[k]>a$, it
follows that $a$ is in the list $A[i], \dots, A[j]$ iff it is in the list
$A[i], \dots, A[k]$, so the answer returned by the call
$\mbox{\texttt{Proc}}(i,k)$ is the one required by the induction
hypothesis for $j-i$.  A similar argument verifies the induction
hypothesis for $j-i$ in the case that $A[k]<a$.

}
%%%%%%%%%%%%%%%%%%%%%%%
%pset 5, #1  state machine
\begin{problems}
\problem \textbf{Integer Multiplication}
Consider the following procedure to compute the product
of positive integers $x$ and $y$.
\begin{itemize}
\item Do the assignment $a := x$.
\item Do the assignment $b := y$.
\item Repeat the following steps:
\begin{itemize}
\item If $b = 1$ \textbf{return} $a$ and halt.
\item Do the assignment $a := a + x$
\item Do the assignment $b := b - 1$
\end{itemize}
\end{itemize}
\renewcommand{\theenumi}{(\roman{enumi})}
\begin{enumerate}
\item Model the procedure with a state machine. 
\item Formulate an invariant relating $x$, $y$, $a$, and $b$,  which
holds at the top of the loop. Your invariant should imply that upon
termination, $a = xy$.
\item Prove that the invariant holds. 
\item Argue that the process terminates. 
\end{enumerate}
\renewcommand{\theenumi}{(\arabic{enumi})}

\solution{
(i). The states Q can be represented as tuples $(x, y) \subset (\mathbb{N} \times \mathbb{N}$). \\
The initial state $q_0$ is $(x, y)$. 
There is only one transition: $(a,b) \rightarrow (a+x, b-1)$. 
The terminating condition is $b = 1$, and the machine outputs $a$. \\
(ii). The invariant is expressed by the predicate $P(\cdot)$, which takes
a state of the machine as its argument: \\
$P(a,b)$ = ``$a + x(b-1) = xy$'' \\
Note that if $b = 1$ and $P(a,b)$, then $a + x(1-1) = xy \Rightarrow a = xy$. \\
(iii). $P(q_0)$ holds, since $x + x(y-1) = x + xy - x = xy$. 
If $(q, q')$ is a valid transition, we will show that $P(q) \Rightarrow P(q')$. 
For any state $q = (a, b)$, $q'$ will be a state following $q$ iff $q' = (a+x, b-1)$.
If we assume that $P(q)$ holds, then $a + x(b-1) = xy \Rightarrow a + xb - x = xy
\Rightarrow a+(x-x)+xb-x=xy \Rightarrow (a+x)+x(b-2)=xy$, which is $P(q')$. \\
(iv). The process terminates when $b = 1$. Since $b$ begins as a positive integer and 
decreases by one with each transition, it must reach 1.
}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% pset 5, #2 State Machine
\problem \textbf{Modular Exponentiation} \\
Consider the following procedure to compute $a^b \bmod n$.
\begin{itemize}
\item Let $\langle b_k, b_{k-1}, \ldots, b_0\rangle$ be the binary representation of $b$.
\item Do the assignment $c := 1$.
\item Do the assignment $d := a \bmod n$.
\item Do the assignment $i := k$.
\item Repeat the following steps:
\begin{itemize}
\item if $i = 0$ \textbf{return} $d$ and halt.
\item Do the assignment $i := i-1$.
\item Do the assignment $c := 2c$.
\item Do the assignment $d := (d \cdot d) \bmod n$.
\item if $b_i = 1$
\begin{itemize}
\item Do the assignment $c := c+1$.
\item Do the assignment $d := (d \cdot a) \bmod n$.
\end{itemize}
\end{itemize}
\end{itemize}

\renewcommand{\theenumi}{(\roman{enumi})}
\begin{enumerate}
\item Model the procedure with a state machine. 
\item Notice that at the begining of every iteration 
the binary representation of $c$ 
is $\langle b_k, b_{k-1}, \ldots, b_i \rangle$.
Formulate an invariant relating $a$, $b$, $c$, $d$, $i$, and $n$,  which
holds at the top of the loop. Your invariant should imply that upon
termination, $d = a^b \bmod n$.
\item Prove that the invariant holds. 
\end{enumerate}
\renewcommand{\theenumi}{(\arabic{enumi})}
\solution{
(i). The states $Q$ can be represented as triples $(c, d, i) \subset
(\mathbb{N} \times \mathbb{N}\times \mathbb{N}$). The initial state
$q_0$ is $(1,a\bmod n,k)$.  
There are two possible transitions: if $b_{i-1} = 0$,
then $(c,d,i) \rightarrow (2c, d^2 \bmod n, i-1)$, else $(c,d,i)
\rightarrow (2c+1, d^2a \bmod n, i-1)$.  The terminating condition is
$i = 0$, and the machine outputs $d$. \\
(ii). The invariant is expressed by the predicate $P(\cdot)$, which
takes a state of the machine as its argument: \\ $P(c,d,i)$ = ``$d =
a^c \bmod n \wedge c = \langle b_k, b_{k-1}, \ldots, b_i \rangle$'' \\
Note that if $i = 0$ and $P(c,d,i)$, then $c = b$, and therefore $d =
a^b \bmod n$. \\
(iii). $P(q_0)$ holds, since $d = a \bmod n = a^1 \bmod n = a^c \bmod n$, 
and $c = 1 = b_k$
($b_k$ must be 1, as it is the most significant bit).  If $(q, q')$ is
a valid transition, we will show that $P(q) \Rightarrow P(q')$.  For
any state $q = (c,d,i)$, $q'$ will be a state following $q$ iff either
$b_i-1 = 0$ and $q' = (2c, d^2 \bmod n, i-1)$ or $b_i-1 = 1$ and $q'=(2c+1,
d^2a \bmod n, i-1)$.  If we assume that $P(q)$ holds, \emph{i.e.} $d_0
= a^{c_0} \bmod n$ and $c_0 = \langle b_k, b_{k-1}, \ldots,
b_{i_0}\rangle$ then there are two cases to consider. In the case
$b_{i_0-1} = 0$, we have $d = d_0 \cdot d_0 \equiv a^{c_0} \cdot
a^{c_0} \equiv a^{2c_0} \equiv a^c \pmod n$ and $c = 2c_0 = \langle
b_k, \ldots, b_{i_0}, 0 \rangle$, which is $P(q')$. In the case that
$b_{i_0-1} = 1$, we have $d = d_0 \cdot d_0 \cdot a \equiv a^{c_0}
\cdot a^{c_0} \cdot a \equiv a^{2c_0+1} \equiv a^c \pmod n$ and $c =
2c_0+1 = \langle b_k, \ldots, b_{i_0}, 1 \rangle$, which is $P(q')$. 
}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%5
%END   Tina's problems


%BEGIN Kavita's problems
% Fall 1998


%**************
%   PSET 3    *
%**************

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\problem {\bf (10 points)} 
John Dunagan, one of the 6.042 TAs, gave our friend Theory Pig a new
toy for his birthday.  The toy consists of a $3 \times 3$ grid of
squares, where each square contains one of the letters in THEORY PIG.
Each row can be rotated right or left and each column can be rotated
up or down.  The effects of such rotations are explained in the figure
below.

\[
\begin{array}{|c|c|c|}
\hline
H & E & Y \\ \hline
P & I & G \\ \hline
R & O & T \\ \hline
\end{array}
\rightarrow
\begin{array}{|c|c|c|}
\hline
R & E & Y \\ \hline
H & I & G \\ \hline
P & O & T \\ \hline
\end{array}
\rightarrow
\begin{array}{|c|c|c|}
\hline
R & E & Y \\ \hline
I & G & H \\ \hline
P & O & T \\ \hline
\end{array}
\]

The first picture shows Theory Pig's new toy configured as he first
received it.  The leftmost column is then rotated downward to give the
middle picture.  The $H$ and $P$ move down, and the $R$ rotates back
up to the top.  Then the middle row is rotated leftward to produce the
final picture.  The $I$ and $G$ move left, and the $H$ rotates back
around to the right.

Naturally, Theory Pig wants to arrange the letters so as to spell his
name.

\[
\begin{array}{|c|c|c|}
\hline
T & H & E \\ \hline
O & R & Y \\ \hline
P & I & G \\ \hline
\end{array}
\]

Based on prior experience, Theory Pig is afraid that the toy might be
specially designed to make this delightful combination utterly
impossible, no matter what sequence of row and column rotations he
attempts.

\begin{problemparts}

\problempart Model Theory Pig's toy as a state machine.

\solution{
\begin{itemize}

\item The set of states $Q$ consists of all arrangements of the letters in
THEORY PIG on a $3 \times 3$ grid.

\item The set of start states $Q_0$ consists of the single arrangement HEY PIG,
ROT!

\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 toy indicated above,
prove that Theory Pig can never spell his name.

\solution{
The idea is to keep track of the number of letter pairs that are out
of order relative to $THEORYPIG$.  For example, in the initial
configuration, $H$ appears before $T$; this pair of letters is out of
order, because $T$ appears before $H$ in $THEORYPIG$.  We will refer
to an out-of-order letter pair as an {\em inversion}.  In the initial
configuration, there are 17 inversions:

\[
\begin{array}{ccccc}
HT & ET & YT & YO & YT \\
PR & PO & PT & IR & IO \\
IT & GR & GO & GT & RO \\
RT & OT
\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 letters out of order, and Theory Pig can never
spell out his name.

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 letters changes the number of inversions
by an odd amount.
\end{lemma}

\begin{proof}
If the letters were initially in the same order as in $THEORYPIG$,
then the number of inversions is increased by 1, an odd number.
Otherwise, the letters 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 letters changes the number of inversions by an
odd amount.
\end{lemma}

\begin{proof}
We will show how to swap of any pair of letters using an odd number of
swaps of adjacent letters.  The preceding lemma says that swapping
adjacent letters changes the number of inversions by an odd amount.
Therefore, swapping any pair of letters 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 letters using an
odd number of swaps of adjacent letters.  Suppose that we are swapping
letters $x$ and $y$, where $x$ is on the left, $y$ is on the right,
and there are $k$ stray letters 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 letters 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 letters back to
their original position.  The total number of swaps of adjacent
letters is $k + 1 + k = 2k + 1$, which is odd for all $k \geq 0$.
\end{proof}

\begin{lemma}
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
letter 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}
Theory Pig can never spell his name.
\end{theorem}

\begin{proof}
The proof uses the Invariant Theorem.  We prove the following
invariant: the number of inversions in the letter sequence relative to
$THEORYPIG$ is always odd.

The invariant holds in the single start state, because the number of
inversions is initially 17, which is odd.  Furthermore, the invariant
is maintained under every transition.  The preceding lemma states that
every row or column rotation changes the number of inversions by an
odd amount.  Therefore, if the number of inversions was odd before a
transition, then the number of inversions must be odd after a
transition.  Thus the invariant is established by the Invariant
Theorem.

Since the number of inversions relative to $THEORYPIG$ is always odd,
the string can never be formed.
\end{proof}
}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%END   Kavita's problems


\end{problems}

\end(document}
