\documentclass[11pt, twoside]{article}
\input{macros-course}
\usepackage{graphicx}
\renewcommand{\implies}{\longrightarrow}
\newcommand{\ignore}[1]{}
\showsolutionstrue
\begin{document}
\handout{practice-ps1-sol}{Practice Problem Set 1 - Solutions}{March 11, 2001}

\medskip
\begin{problems} 

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

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


%BEGIN Ray's problems


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

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

\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{figures/practice1-ant}}}
\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 (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}

%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

%END   Ivan's problems

%BEGIN George's problems
%%%%%%%%%%%%%%  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.
}
                      
%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

%END   Tina's problems

\end{problems}

\end{document}                            
