\documentclass[12pt,twoside]{article}
\setlength{\textheight}{5.25in}
\usepackage{amsmath}
\usepackage{graphics}
\usepackage{psfig}
\input{macros-course}

\begin{document}

\psol{4}{March 6, 1999}

\newcommand{\reserve}[1]{}
\newcommand{\solution}{\bigskip\noindent{\bf Solution:}}
\newcommand{\stas}[1]{{\bf Stas's Comment:}{\it #1}}


\begin{center}
{\bf (Revised on 3/7/99)}
\end{center}

\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 := 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{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{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}


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

\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?

\solution

No.  I cannot meet my TA on this map: There is no even-length path
that connects the two nodes we are placed on.  Note that a solution
exists if and only if there is an even-length path between the nodes
that I and my TA initially occupy (a path could traverse the same
nodes and edges many times).  You can convince yourself that there is
no even-length path in this example by noting that every simple path
connecting the two nodes has odd length, and furthermore, that this
graph has only even-length cycles, and hence no amount of loops attached
to any of the simple paths can create an even-length path.

In part (c) we will argue that there is an even-length path between
every two nodes on the graph if the graph is connected and not
bi-partite.  The graph in this example is connected but it {\em is}
bi-partite, and if we 2-color it (i.e. partition its vertices into
two disjoint sets $V_1$ and $V_2$ s.t. there is no edges within $V_1$
and no edges within $V_2$) then me and my TA both occupy a node of the
same color.

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

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

\solution

Yes.  Now there is an odd-length path between the two nodes.  Note
that this graph is connected but not bipartite.  Note also that, in
contrast to the previous graph, this one has an odd cycle.

\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.

\solution

Such graph must have an even-length path between every two nodes.  A graph
with two or more vertices has this property if and only if it is
connected and not bipartite.  Here is a proof:

\noindent
($\Rightarrow$) Suppose there is an even length path between every two
vertices.  Since there is a path between every two vertices, the graph is
certainly connected.  Now supppose the graph was also bipartite.  On any
path in a bipartite graph, the successive vertices alternate colors. So if
the path has even length, the first and last colors will agree.  Since
every two vertices are connected by an even length path, every pair of
vertices has the same color.  In particular, the endpoints of any edge
must have the same color, a contradiction.  Hence the graph cannot be bipartite.

\noindent
($\Leftarrow$)
Suppose a connected graph has a pair of vertices $v \neq w$ such that
there is no path of even length between $v$ and $w$.  We will show that
the graph is bipartite.

Let $E$ be the set of vertices reachable by an even length path from $v$,
and let $O$ be the vertices reachable by an odd length path from $v$.  We
claim that coloring vertices in $E$ white and coloring vertices in $O$
black is a 2-coloring of the graph.

First of all we must show that this rule really defines a coloring.  Since
every vertex other than $v$ is reachable from $v$ by a path whose length
must be even or odd, every vertex besides $v$ gets assigned a color.  But
$v$ also gets a color: leaving and returning to $v$ using the same path in
both directions is an even length path from $v$ to $v$, so $v$ gets
colored white.

Moreover, every vertex will be assigned a unique color.  To verify this,
we must show that no vertex is in both $E$ and $O$.  But suppose $E$ and
$O$ had a vertex, $x$, in common.  This means there is an odd-length path,
$p_o$, and also an even length path $p_e$, each going from $v$ to $x$.
But because the graph is connected, there is also a path, $q$, from $x$ to
$w$.  Now the paths $p_oq$ and $p_eq$ both go from $v$ to $w$, and one of
them must be of even length, a contradiction.  So $E$ and $O$ are indeed
disjoint.

All that remains is to show is that there is no edge between distinct
vertices in $E$ nor between distinct vertices in $O$.  Suppose there was
an edge with endpoints $y \neq x$ which were both in $E$.  Then the even
length path from $v$ to $y$ followed by the edge $(y,x)$ is an odd length
path from $v$ to $x$, so $x$ is in $O$ as well as $E$, which we know is
impossible.  Similarly, there can't be an edge between two vertices in $O$.

So we have shown that the graph is bipartite. \qed

\iffalse

\bigskip\noindent{\bf Solution 2:}

Another solution to this problem was to argue that a graph has an
even-length path between every two nodes if and only if it is
connected and has an odd cycles.  This statement will follow from the
solution above and from the following theorem:
\begin{quote}
{\bf Theorem:} {\it
A graph is bipartite if and only if it has no odd cycles.}
\end{quote}
Here is the proof:

\noindent
($\Rightarrow$)

To say that a graph is bipartite is the same as to say that it is
2-colorable.  If $G=(V,E)$ is bipartite, then let $R,B$ (for red and
blue) $R\cap B=\emptyset, R\cup B=V$ be the two-coloring of $G$.  Take
any node $v_0$ in $V$, and any path $v_0,v_1,v_2,...,v_n,v_0$ that
goes from $v_0$ to $v_0$ (in other words, take any cycle in $G$).
Assume without loss of generality that $v_0\in{R}$.  Then it must be
that $v_i\in{R}$ if $i$ even and $v_i\in{G}$ if $i$ odd.  Hence $n$
must be odd and the length of the cycle is even.

\noindent
($\Leftarrow$)

We give a proof by induction on $n=|E|$, $n\geq{0}$.  The predicate we
will prove is the following: $P(n)=$``For every graph $G=(V,E)$ for
$|E|=n$, if $G$ has no odd cycles then $G$ is bipartite'':

\medskip
\noindent 
%
{\em Base case:} $P(0)$ is true because a graph with no edges is both
bipartite and has no odd cycles.

\medskip
\noindent 
%
{\em Inductive case:} Take some $n\geq{1}$.  We will show that if
$P(n-1)$ then $P(n)$.  Take some $G=(V,E)$ s.t. $|E|=n$.  Assume $G$
has no odd cycles.  Pick an edge $e=(v,u)\in{E}$ and remove it to
create a graph $G'=(V,E')$ where $E'=E\setminus\{e\}$.  Then $|E'|<n$
and $G'$ has no odd cycles, since $G$ did not have any.  Hence, from
$P(n)$ it follows that $G'$ is bipartite.  Let $R,B$ be a
two-coloring of $G'$.  We have two cases: First, if $u\in{R}$ and
$v\in{B}$ or vice versa, then the same $(R,B)$ is a two-coloring for
both $G'=(V,E')$ and $G=(V,E)$ and hence, in this case, $G$ is
bipartite.  The other case is if $u,v\in{R}$ (or $u,v\in{B}$, but
without loss of generality we can assume the former).  We have two
cases here:
\begin{enumerate}
\item
If $u$ and $v$ are not connected in $G'$ then we can invert the colors
in the connected (in $G'$) component $C\subseteq{V}$ to which $v$
belongs (and keep the colors of the vertices that do not belong to the
connected component $C$).  In result we will get another good
two-coloring of $G'$, but now $u$ and $v$ have a different color.
Hence this case looks like the one we looked at above.
\item
If $u$ and $v$ are connected in $G'$, then since they have the same
color in a two-coloring of $G'$, there is an even-length path between
them in $G'$.  But then adding an edge $(u,v)$ to $G'$ creates an
odd-length cycle, which contradicts the assumption that $G$ has no
odd-length cycles.
\end{enumerate}
\fi


\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).

\solution

We need to show that $\preceq$ is transitive and anti-symmetric:

\begin{itemize}
\item
$\preceq$ is transitive: Suppose a copy of $T_1$ is a subtree of $T_2$;
then there is path, $P$, from the root of the $T_1$-copy to the root of
$T_2$.  Suppose also that a copy of $T_2$ is a subtree of $T_3$; then
there is path, $Q$, from the root of the $T_2$-copy to the root of $T_3$.
Now the $T_2$-copy has a copy of the $T_1$-copy as a subtree; call this
subtree $T'_1$.  So the path $P$ has a copy, $P'$, from the root of $T'_1$
to the root of the $T_2$-copy.  This means that the path $P'$ followed by
the path $Q$ leads from the root of $T'_1$ to the root of $T_3$.  So
indeed, there is a copy of $T_1$, namely $T'_1$, which is a proper subtree
of $T_3$.

\item
We show that $\preceq$ is anti-symmetric: Suppose (a copy of) $T_1$ is a
proper subtree of $T_2$ and also $T_2$ is a proper subtree of $T_1$.  Then
$T_1$ has a copy of itself as a proper subsubtree.  Therefore there is a
path --- which must be of length two or more --- from the root of $T_1$ to
the root of the copy of $T_1$.  This path extends to a path of length four
or more to the root of the copy in the copy, and then extends to the root
of the copy in the copy in the copy\dots.  In this way we can find an
infinite path in $T_1$, contradicting the assumption that $T_1$ is
finite-path.
\end{itemize}

Now we must show that $\preceq$ is well-founded.  Suppose not.  Then, as
shown in Handout 18 on well-founded posets, there must be an infinite
$\preceq$-decreasing sequence of distinct elements.  That is, an infinite
sequence $T_1 \succ T_2 \succ T_3 \succ \dots$ of distinct finite-path
trees.  By definition, $T_n \succ T_{n+1}$ means there is a path from the
root of $T_n$ to a vertex which is the root of an isomorphic copy of
$T_{n+1}$.  It's convenient to assume that $T_{n+1}$ itself --- rather
than an isomorphic copy --- is the subtree of $T_n$.  This assumption
is justified because we could always replace $T_{n+1}$ in the sequence
above with the actual subtree of $T_n$ isomorphic to it.

Now $T_n \succ T_{n+1}$ implies there is a path $P_n$ (necessarily of
length one or more) from the root of $T_n$ to the root of $T_{n+1}$.  But
then $P_1$ followed by $P_2$ followed by $P_3$ \dots is an infinite path
from the root of $T_1$, contradicting the hypothesis that $T_1$ is
finite-path.  Hence there cannot be such an infinite decreasing sequence
of finite-path trees, and this implies that the set of finite-path trees
partially ordered by $\preceq$ is a well-founded poset.  \qed


\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.

\solution

Problem 7(b) of Problem Set 3 established a stronger fact about game
trees: either one player has a winning strategy or both players have
nonlosing strategies.  In the solutions for Problem Set 3, the first
solution of 7(b) used induction on tree depth and so only applied to trees
of finite depth.  However, the second solution given for 7(b) only used
the fact that the ``proper subtree'' relation is a well-founded partial
order, and so it applies \emph{without change} to finite path trees.

\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}
coordinate-wise $\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.

\solution

In Problem 2 of Tutorial 4, we studied a more general version of the
game above, where the first player chose $n$, which sets up a
``dimension of the board they play on''.  The game above, is like the
game from Tutorial 4 where the first player always picks $n=3$, and so
all consequent moves are {\em triples} of natural numbers.  We can use
similar logic as in that problem to argue the following:
\begin{enumerate}
\item
Let's first cast the question of whether moves in this game are valid
or not in terms of some partial ordering in set $\naturals^3$:

A sequence $p_1,p_2,p_3,...,p_n$ (or an infinite sequence
$p_1,p_2,p_3,...$) of points in $\naturals^3$ (i.e. a sequence of
triples of natural numbers) is a {\em valid sequence of moves} in this
game (alternating moves of player A and player B), if and only if
\[
\forall(i,j)\,\, i<j \Rightarrow p_i \not\leq_3 p_j
\]
where relation $\leq_p$ is a partial order in $\naturals^3$ defined
as follows:
\[
(x_1,y_1,z_1) \leq_3 (x_2,y_2,z_2) ~~~\iff~~~
((x_1\leq{x_2})\wedge(y_1\leq{y_2})\wedge(z_1\leq{z_2}))
\]

\item
First note that $(\naturals,\leq)$ is a well-quasi-ordered set. Here is
a definition from Tutorial 4:
\begin{quote}
{\bf Definition 4.1:} {\it
A poset $(P,\preceq)$ is \emph{well-quasi-ordered} iff, for every infinite
sequence $p_1, p_2, \dots p_n \dots$ of elements in $P$, there are positive
integers $i<j$ such that $p_i \preceq p_j$.}
\end{quote}
The well-quasi-ordered property of $(\naturals,\leq)$ is immediate: any
infinite sequence of distinct natural numbers $n_1,n_2,n_3,...$ must
eventually include a number larger than $n_1$, and so must be a sequence
of the required kind.

\item
Now we can use the findings of Problem 2 in Tutorial 4 to argue that
set $(\naturals^3,\leq_3)$ is well-quasi-ordered.  We use Lemma 4.2 of
part (e) of Problem~2:
\begin{quote}
{\bf Lemma 4.2:} {\it
Suppose  $(P, \leq_P)$ and $(Q, \leq_Q)$ are well-quasi-ordered posets.
Then so is $P \times Q$ under the coordinate-wise partial order.}
\end{quote}
This lemma implies that since $(\naturals,\leq)$ is a
well-quasi-ordered poset by point (2) above, then so is $(\naturals^2,
\leq_2)$ where $\leq_2$ is a coordinate-wise partial order in
$\naturals^2$.  And applying the lemma once more, we get that
$(\naturals^3, \leq_3)$ is a well-quasi-ordered poset too.

\item
As in Part (e) of Problem 2, by bringing together point (1) and (3)
above, we realize that since $(\naturals^3,\leq_3)$ is
well-quasi-ordered, then in every infinite sequence of points
$p_1,p_2,p_3,...$ in $\naturals^3$, there must be a pair $(i,j)$,
$i<j$ s.t. $p_i\leq{p_j}$.  By point (1), this means that no infinite
sequence of points in $\naturals^3$ can be a sequence of valid moves
in this game.  Hence, every sequence of valid moves in this game is
finite (In particular, the game can never go on for ever).

\item
The fact that there can be no infinite sequence of valid moves in this
game means this game has a {\em finite-path} game tree.  Therefore,
the result from part (b) of this problem above applies here, i.e. one
of the players has a non-losing strategy.  But since there is no
``draw'' outcome in this game, a non-losing strategy must be a
winning strategy.

\end{enumerate}

\problempart \emph{Extra Credit}: Who has a winning strategy?  What is
the strategy?   \textbf{(We don't known the answer.)}

\iffalse
\stas{See what the students write and tell me if there are some
different strategies.  For $n=2$, there is a winning strategy for
player A: It should pick $(1,1)$ and then respond to every $(x,y)$
with $(y,x)$, unless $(x,y)=(0,0)$ and player B looses.  But I dont
see how to translate it into a 3-D strategy easily...  Please email
everyone if you see a light.}
\fi
\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?

\solution 

You were guaranteed to get a student-optimal stable marriage set if
you ran the stable marriage algorithm given in lecture, where Students
are Men and Companies are Women.  The result is the following assignment:

\begin{center}
\begin{tabular}{c|c|c} 
Student & Companies & Rank in the original list \\ \hline
Albert:  & Bellcore & 2\\
Ben:     & AT\&T & 1\\
Chris:   & Compaq & 1\\
Doug:    & Draper &1
\end{tabular}
\end{center}

\problempart What is a company-optimal stable marriage set for
this problem?

\solution

Similarly, you were guaranteed to get a company-optimal stable
marriage set if you ran the stable marriage algorithm given in
lecture, where Students are Women and Companies are Men.  The result
is the following assignment:

\begin{center}
\begin{tabular}{c|c|c}
Company & Students & Rank in the original list\\ \hline
AT\&T:    & Albert & 2\\
Bellcore: & Ben & 2\\
Compaq:   & Chris & 2\\
Draper:   & Doug & 2
\end{tabular}
\end{center}




\problempart Are there any other stable marriage sets possible?

\solution
We noted in lecture that the Gale-Shapley dating protocol yields a
(necessarily unique) man-optimal stable marriage assignment, and moreover
this assignment is also the unique women-pessimal one.  Therefore, from
parts (a) and (b) we know that in both student-optimal and
student-pessimal stable marriage sets, Chris is married to Compaq, and
Doug to Draper Labs.  So Chris can never do better or worse than Compaq in
any stable marriage set, viz., he is married to Compaq in all stable
marriage sets; likewise for Doug and Draper.  Hence the possibilities for
Albert and Ben are only AT\&T and Bellcore.  Since both these
possibilities are given in the two solutions above, there are no other
stable marriage sets possible.


\end{problemparts}

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

\end{problems} \end{document}
