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

\input{macros-course}

\begin{document}
\pset{4}{February 23, 1998}{Tuesday, March 2}

\newcommand{\reserve}[1]{}

\newcommand{\solution}[1]{}
% \newcommand{\solution}[1]{\bigskip #1}

{\bf Reading assignment}: Lecture Notes 6 and 7 on State Machines,
Invariance, and Termination.

\iffalse
4:45pm ARM

\textbf{CONSIDER POSSIBLE REVISION FOR ``LIGHTS OUT'' problem: let button
toggle the states of four neighbors but NOT itself, so parity becomes an
invariant.}
\fi


\begin{problems}

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

\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 := 0$.
\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.
\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$.

\problempart Prove that the invariant holds.
\problempart Prove that the procedure terminates.
\end{problemparts}
\solution{will be drafted later}


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

\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.  For example, the figure below shows a situation in which the ant
faces North, and there is a trail of food leading approximately Southeast.

\bigskip
\centerline{\resizebox{!}{2.0in}{\includegraphics{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{States =
(how many turns since smelled food -- $\set{0,1,2,3}$,
 location of ant -- $\naturals \cross \naturals$,
 direction ant is facing -- $\set{N,E,W,S}$,
 locations of crumbs -- sequence of zero or more locations).

The ant needs to know how many times it turned without seeing food.  If
the ant turned all the way around without seeing any food, then the ant
must be at the end of the trail.  The input is whether or not there is
food in front of the ant, and there is a ``done'' output.  There are
transitions corresponding to the four possible ant actions \{``go
straight'', ``turn left'', ``turn right'', ``done''\}.  The ant-memory
machine looks like (will be drawn later)}

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

\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{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.
\problempart How many states are there?
\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?
\problempart Is every pattern of lights reachable?  Prove your answer. 
\end{problemparts}

\solution{to be drafted later}

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

\problem {\bf (15 points)} Unfortunately, I was not able to turn in my
problem set for 6.042 and I need to meet my TA to get it in.  We are
both driving through the city and in order for me to turn in the
problem set we must meet at exactly the same place at the same time.
Given the following map,

\bigskip
\centerline{\resizebox{!}{2.0in}{\includegraphics{map1.eps}}}
\bigskip

\begin{problemparts}
\problempart At each time step, both I and my TA simultaneously move to an
adjacent node in the graph.  We would like to organize our routes such
that we meet at the same node at the same time.  Can we do it?

\problempart How about if we used the following map instead?

\bigskip
\centerline{\resizebox{!}{2.0in}{\includegraphics{map2.eps}}}
\bigskip

\problempart Describe a general criterion for a graph where I would be able
             to meet my TA at some vertex regardless of our initial positions.
\end{problemparts}

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

\problem {\bf (15 points)} A rooted tree is called \emph{finite-path} iff
it has no infinite simple paths starting at the root.

A finite-path tree need not be finite nor even have an upper bound on the
length of its paths.  For example, there is a finite-path tree whose root
has an infinite number of children and each child of the root is at the
top of a finite chain of descendents one longer than the previous child's.
The first seven branches of this tree are shown in
Figure~\ref{fin-path-tree}.

\begin{figure}[htbp]
\centerline{\psfig{figure=fptree.eps,height=3in}}
\caption{\em The first seven branches of a finite-path tree with paths of
every finite length.}
\label{fin-path-tree}
\end{figure}

Let $\preceq$ be the binary relation on rooted trees ``is (isomorphic to)
a proper subtree of.''  That is, $T_1 \preceq T_2$ iff there is a
\emph{non-root} vertex $v$ of $T_2$ such that $T_1$ is isomorphic to the
subtree of $T_2$ rooted at $v$.

\begin{problemparts}

\problempart Prove that $\preceq$ is a well-founded partial order on
finite-path trees.  (Use the definition of a partial order from Tutorial 3
which does not require that a partial order be reflexive).

\problempart In Problem 7 of Problem Set 3, we established that for any
two-person game with a \emph{finite} game tree, at least one player has a
non-losing strategy.  Show that this result in fact holds for all
two-person games with a \emph{finite-path} game tree.

\problempart Here is an example of a game.  Player one chooses a triple of
natural numbers.  Then players alternate choosing triples of natural
numbers.  Any triple may be selected as long as it is \emph{not}
coordinatewise $\geq$ any previously selected triple.  The game ends
when a player picks the triple $(0,0,0)$; this player loses.

For example, player 1 might first choose (7,8,9).  Player 2 could then
choose (0,1,67), and after that Player 1 could choose (83, 0,0).  Player 2
can then choose (1,0,0).  Now player 1 can choose (0,0,1), allowing player
2 to choose (0,1,0).  This finally leaves player 1 with only the losing move
(0,0,0).

\iffalse In other words, if the first $n$ moves in the game are
$(x_1,y_1),(x_2,y_2),...,(x_n,y_n)$ where $(x_i,y_i)$ pairs with odd $i$'s
were picked by player A and those with even $i$'s were picked by player B,
then the next player (A if $n+1$ is odd or B if $n+1$ is even) can pick a
pair of natural numbers $(x_{n+1},y_{n+1})$ only if there is no $k$,
$1\leq{k}\leq{n}$ s.t. $x_{n+1}\geq{}x_k$ {\em and} $y_{n+1}\geq{}y_k$.\fi

Show that one of the players must have a winning strategy.  \hint Use the
results about well-quasi-orders from Tutorial 4.

\problempart \emph{Extra Credit}: Who has a winning strategy?  What is
the strategy?

\end{problemparts}

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

\problem {\bf (15 points)} Four people are interested in participating in
the VI-A program where each person ranks his top choices of companies
and the companies rank the students as well.  The people Albert, Ben,
Chris, and Doug are interested in companies AT\&T, Bellcore, Compaq,
and Draper Labs.  Below are the students' rankings of the companies
and the companies' rankings of the students.

\begin{center}
\begin{tabular}{c|c} 
Student & Companies \\ \hline
Albert:  & Compaq, Bellcore, AT\&T, Draper \\
Ben:     & AT\&T, Bellcore, Draper, Compaq \\
Chris:   & Compaq, Draper, AT\&T, Bellcore \\
Doug:    & Draper, AT\&T, Bellcore, Compaq 
\end{tabular}
\end{center}

\begin{center}
\begin{tabular}{c|c}
Company & Students \\ \hline
AT\&T:    & Doug, Albert, Chris, Ben \\
Bellcore: & Chris, Ben, Albert, Doug \\
Compaq:   & Doug, Chris, Albert, Ben \\
Draper:   & Ben, Doug, Chris, Albert
\end{tabular}
\end{center}

\begin{problemparts}
\problempart What is a student-optimal stable marriage set for
this problem?
\problempart What is a company-optimal stable marriage set for
this problem?
\problempart Are there any other stable marriage sets possible?
\end{problemparts}

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

\end{problems} \end{document}
