\documentstyle[11pt,twoside,amsfonts,amstex,psfig]{article}

\addtolength{\topmargin}{-1in}
\setlength{\textwidth}{6.5in}
\setlength{\textheight}{9in}

\raggedbottom

\input{macros-course}

\newcommand{\recn}[3]
{\setcounter{problemsetnum}{#1}
\handout{tut#1}{Notes for Recitation #1 (#2/98)}{#3}
}


\begin{document}

\recn{4}{10/2}{October 2, 1998}


\section{Greatest Common Divisor}

In class this week, we studied invariants and how to use them.  As
another example of invariants, we will prove that Euclid's famous
algorithm for computing the greatest common divisor of two numbers
never gives the wrong answer.  This is half of a proof that the
algorithm is correct; the other half is to prove that the algorithm
terminates.  We do this by exhibiting a decreasing derived variable; a
theorem presented in lecture then implies termination.

\begin{defin}
The {\em greatest common divisor} ($GCD$) of two natural numbers $x$
and $y$, not both zero, is the largest $n \in {\cal N}$ such that $n |
x$ and $n | y$.
\end{defin}

For example, $GCD(6, 15) = 3$, $GCD(6,7) = 1$, and $GCD(2,0) = 2$.
$GCD(0, 0)$ is undefined.  Computing greatest common divisors is
important in cryptography.

One way to compute the $GCD$ of two numbers is to factor both into
primes and then pull out prime factors shared by both.  For example:

\begin{eqnarray*}
24 & = & 2^3 \cdot 3 \\ 36 & = & 2^2 \cdot 3^2 \\ & \Rightarrow & GCD
= 2^2 \cdot 3 = 12
\end{eqnarray*}

The problem is that factoring is very slow.  Fortunately, the Greek
mathematician Euclid thought of a better algorithm.  (He apparently
never implemented this algorithm; perhaps he was too lazy to learn C.)

The input to procedure {\tt Euclid} is a pair of numbers $(x, y)$.
There are only two steps in the algorithm:

\begin{enumerate}
\item If $y$ = 0, return $x$.
\item Otherwise, return {\tt Euclid}$(y, x \bmod y)$.
\end{enumerate}

(Recall that $x \bmod y$ denotes the remainder when $x$ is divided by
$y$.)

As an example, suppose that the procedure is called with inputs $x =
22$ and $y = 16$.  This would generate a sequence of recursive calls:
{\tt Euclid}(22, 16), {\tt Euclid}(16, 6), {\tt Euclid}(6, 4), {\tt
Euclid}(4, 2), {\tt Euclid}(2, 0).  The final call returns 2.  The
value 2 propagates all the way back up the recursion and is output as
the final answer.  Sure enough, $GCD(22, 16) = 2$.

Here is the theorem that we want to prove about Euclid's algorithm:

\begin{theorem}
If {\tt Euclid}$(x, y)$ terminates, then it returns $GCD(x, y)$.
\end{theorem}

We can use the state machine/invariant approach to prove this theorem.
The first problem is to define the three components of the state
machine, $Q$, $Q_0$, and $\delta$:

%  I think putting a and b in R is a problem because then the statement
%  GCD(a, b) = GCD(x, y) is not a valid predicate; if none of a, b, x, and
%  y are integers, then is the statement true or false?  I'm not sure
%  what to do...

\begin{eqnarray*}
Q & = & \{ (a, b) \mid a, b \in {\cal R} \} \\ Q_0 & = & \{ (x, y) \}
\\
\delta & = & \{ (a, b) \rightarrow (b, a \bmod b) \mid b \neq 0 \}
\end{eqnarray*}

Two aspects of these definitions might be disturbing.  First, the
start state contains variables, $x$ and $y$.  This will not be a
problem; we will treat $x$ and $y$ as constants in our analysis.  The
upshot is that we are defining a somewhat different state machine for
each input.

Second, we have not defined a transition for the case when $b = 0$,
even though this corresponds to step 1 of the algorithm.  This is the
termination condition, which we are deferring.

The only remaining preparatory work before the proof is choosing a
predicate.  Looking back at the example execution suggests the
predicate $GCD(a, b) = GCD(x, y)$.  That is, any stage the $GCD$ of
the remaining numbers is equal to the $GCD$ of the original two
numbers.  Now we are ready to prove the theorem.

{\em Proof. }
The proof uses the Invariant Theorem.

Let $P((a, b))$ be the predicate that $GCD(a, b) = GCD(x, y)$.

First, we must show that the predicate holds for all start states.
This is trivial because the only start state is $(x, y)$ and $GCD(x,
y) = GCD(x, y)$.

Next, for each transition $(a, b) \rightarrow (a', b') \in \delta$,
assume $GCD(a, b) = GCD(x, y)$ to prove $GCD(a', b') = GCD(x, y)$.  It
is sufficient to show that $GCD(a', b') = GCD(a, b)$.  Futhermore,
since all transitions in $\delta$ are of the form $(a, b) \rightarrow
(b, a
\bmod b)$, we have only to check that $GCD(b, a \bmod b) = GCD(a,
b)$.

Let $s = GCD(a, b)$ and $t = GCD(b, a \bmod b)$.  We will prove that
$s = t$ by showing that each divides the other.

First, we show that $s$ divides $t$.  By definition of $GCD$, $s \mid
a$ and $s \mid b$.  For some integer $c$, $a \bmod b = a - bc$, and so
$s \mid a \bmod b$.  Since $s \mid b$ and $s \mid a \bmod b$, $s \mid
t$.

Now, we show that $t$ divides $s$.  Again, by definition of $GCD$, $t
\mid b$ and $t \mid (a - bc)$.  These facts imply $t \mid a$, and so
$t \mid GCD(a, b)$ and $t \mid s$.
\qed

This proves that at every stage the algorithm stores two numbers
whose $GCD$ is the same as the original input pair.  If the second
number ever becomes zero, then the correct answer will be returned by
step 1 of the algorithm.


Now we address the question of whether the algorithm terminates, and
if so how quickly it terminates.
Recall from lecture the theorem about decreasing derived variables.

\begin{theorem}
If $f : Q \rightarrow {\cal N}$ is a decreasing derived variable then
the length of any execution starting at $q_0$ is at most $f(q_0)$.
\end{theorem}

We will now use this to show that Euclid's algorithm terminates in at
most $x$ steps. 

First let us establish a suitable invariant.

\begin{claim}
If $x > y$ then $P((a,b)): a > b$ is an invariant.
\end{claim}

{\em Proof. } To prove that $P$ is an invariant, we must show that it
hold for all start states and is preserved by all transitions.  The
invariant holds trivially in the start state, since by assumption $x >
y$.

Next, we have to show that for each transition $(a, b) \rightarrow
(a', b') \in \delta$, $P(a, b) \Rightarrow P(a', b')$.  That is, we
asum $a > b$ to prove $a' > b'$, where the algorithm specifies that
$a' = b$ and $b' = a \bmod b$.  This holds because $a \bmod b < b$ by
definition of the $\bmod$ operator.
\qed 

Let $f$ be the derived variable $f((a,b)) = a$.

\begin{claim}
If $x > y$ then $f$ is a decreasing derived variable.
\end{claim}

{\em Proof. }
Consider a transition from $(a,b)$ to $(b,a\bmod b)$.
In the state $(a,b)$ we know from the invariant that $a > b$.

Therefore $f((a,b)) = a > b = f((b, a\bmod b))$.
\qed

From the the second claim and the theorem proven in lecture, we
conclude that if we start in a state where $x > y$ then the algorithm
terminates in at most $f((x,y)) = x$ steps.

\section{Fast Exponentiation}

Exponentiation simply corresponds to computing $r^n$, where
$r$ is a real number, and $n$ is a natural number.  Of course,
we can compute $r^n$ using $n-1$ multiplications.  A faster
algorithm is described below.

Fast Exponentiation: compute $r^n$ for $r \in \reals, n\in\naturals$.

State machine with states in $(a,b,k) \in \reals \times \reals \times \naturals$.

Initial state: $(1,r,n)$

Next state:\\
if $k>0$ and $k$ is even, then $(a,b,k)\to (a,b^2,k/2)$;\\
if $k>0$ and $k$ is odd, then $(a,b,k)\to (ab,b,k-1)$.

Invariant: $a b^k = r^n$

Termination: $k$ decreases.


\section{15 Puzzle}

In a 15 puzzle, square tiles numbered $1,\dots,15$ in a $4\times4$ array
with one blank square.  Any tile adjacent to the blank square can slide
into it.

The state machine model of the puzzle has states consisting of a sequence
(permutation), $p$, of $1,\dots,15$ (indicating the positions of the
numbered tiles reading left-to-right and then top-to-bottom), with a
nonnumerical token, $b$, inserted somewhere in the permutation to indicate
where the blank square is.  For example, the initial position
\[\begin{array}{|c|c|c|c|}
\hline 1 & 2 & 3 & 4\\
\hline 5 & 6 & 7 & 8\\
\hline 9 & 10 & 11 & 12\\
\hline 13 & 14  & 15 & b\\
\hline
\end{array}\]
is represented by $1,2,\dots,15,b$, and the target position
\[\begin{array}{|c|c|c|c|}
\hline 15 & 14 & 13 & 12\\
\hline 11 & 10 & 9 & 8\\
\hline7 & 6 & 5 & 4\\
\hline3 & 2 & 1 & b\\
\hline
\end{array}\]
is represented by $15,14,\dots,1,b$.

Next state: Exchange the blank square and an adjacent tile.
For example blank at square $(2,2)$ exchanges position with tile above at $(1,2)$:
\[\begin{array}{|c|c|c|c|}
\hline n_1 & n_2 & n_3 & n_4\\
\hline n_5 & b & n_6 & n_7\\
\hline n_8  & n_9 & n_10 & n_11\\
\hline n_12 & n_13 & n_14  & n_15\\
\hline
\end{array} \longrightarrow
\begin{array}{|c|c|c|c|}
\hline n_1 & b & n_3 & n_4\\
\hline n_5 & n_2 & n_6 & n_7\\
\hline n_8  & n_9 & n_10 & n_11\\
\hline n_12 & n_13 & n_14  & n_15\\
\hline
\end{array} 
\]
corresponds to the state change
\[(n_1n_2n_3n_4 n_5\ b\ n_6 n_7 \dots n_{15}) \to (n_1\ b\ n_3 n_4 n_5 n_2 n_6 n_7 \dots n_{15})\]

We prove that starting from the initial state, there is no way to reach
the target state.  For any permutation, $p$, of the integers $1,\dots,n$,
let $\mbox{inversions}(p)$ be the number of out-of-order pairs there are
in $p$.  For example, with $n=5$, the permutation 12453 has two
out-of-order pairs: 43 and 53.  The in-order sequence 12345 has no
out-of-order pairs.  More generally,
\[\mbox{inversions}(1,2,\dots, n) = 0\mbox{  and  }
\mbox{inversions}(n,n-1,n-2,\dots,1) = n(n+1)/2.\]

{\bf Invariant}: The parity of $k ::= \mbox{inversions}(p) + r$ where $p$
is the permutation of $1,2,\dots, 15$ (ignoring the $b$), and $r$
is the row number of the blank square.  (Row one is at the top, and the
blank is initially at the bottom, so initially $r=4$.)

Notice that for the initial position, $\mbox{inversions}(1\ 2\ \dots 15) =
0$ and $r=4$, so $k_{\text{init}}$ is even.  For the target position,
$\mbox{inversions}(15\ 14 \dots 2\ 1) = 14 + 13 + \dots +1 = (15\cdot
14)/2 = 105$ and $r=4$ so $k_{\text{target}}$ is odd, so the invariant
implies the target pattern is not reachable from the initial one.

To show that the value of $k$ is constant, note that horizontal moves
change nothing, and vertical moves both change $r$ by 1, and move a tile
three places forward or back in the current permutation, $p$.  This
reverses the order of three pairs in $p$, changing the number of
inversions by 3 or 1, but always by an odd amount.

 \iffalse
 We thought we could use this invariant.  It is invariant, but
 ALL positions have it, so it doesn't help prove anything about reachability.

 {\bf BUGGY Invariant}: With the squares initially filled with tiles 1,\dots,15
 and the blank last, assign red and black colors to the squares AND the
 tiles in checkerboard pattern, treating blank as tile 16.  Then the
 \emph{parity of the number of tiles sitting on a square of the same color}
 is invariant under a move -- because a move is a switch of the blank tile
 with an adjacent tile, changing the color match/mismatch count by 0, 2, or
 -2.

 Initial pattern has 0 clashes, even.  We originally thought Target pattern 
 had 15 clashes, based on extrapolation that 15,14,13 all clashed; of course
 12 doesn't clash, and the target pattern in fact has 12 clashes, even.
 \fi

\iffalse
\item Think-a-dot: flip-flops the three rows of 3,2,3 (need picture to
show connections).  Invariant is parity of total number of left-leaning
flip-flops in the top and bottom rows -- because a marble dropped in any
of the three holes on top must fall thru, and therefore flip, exactly one
flip-flop in each of the top and bottom rows (skips the middle row half
the time).  In fact, if two patterns of the 8 flip-flops have the same
parity, one can be turned into the other by a series of marble drops.
\fi


\section{Extended GCD}

\textbf{Extended GCD} may have been done in some recitations instead
of the one of the previous ones.  It is an interesting example of the
invariant method, and it also establishes a very useful fact about gcd's:
the gcd of two integers, $a$ and $b$, can be expressed as a linear
combination with integer coefficients of $a$ and $b$.

Given integers $a,b$ the following procedure returns the gcd of $a$ and
$b$, and also coefficients $k,l\in \naturals$ so $ka+lb=\mbox{gcd}(a,b)$.
(This procedure and its invariants are taken from Aho, Hopcroft, and
Ullman's text on algorithms.)
\begin{verbatim}
u := 1; v := 0; k := 0; l := 1; x := a; y := b; 
loop:
if y|x DONE;
q := floor(x/y);
** SIMULTANEOUS ASSIGNMENT:
 x := y,
 y := x - q * y   (This is the same as y =  x mod y )
 u := k,
 v := l,
 k := u - q * k,
 l := v - q * l;
goto loop;
\end{verbatim}
NOTE: $x,y$ behave exactly as in the standard Euclidean algorithm from
lecture, except that this procedure stops one step sooner.  This procedure
terminates for the same reason as the Euclidean algorithm: $y$
decreases (fast actually) each time around the loop.

The invariants we need to justify this procedure are:
\begin{enumerate}
\item %\label{gcd}
$\mbox{gcd}(x,y) = \mbox{gcd}(a,b)$,
\item % \label{kl}
$ka+lb = y$, and
\item % \label{uv}
$ua+vb= x$.
\end{enumerate}
The procedure terminates when $y | x$.  Then invariants (a) and
(b) imply $\mbox{gcd}(a,b) = \mbox{gcd}(x,y) = y = ka +lb$.  So we have
the gcd in register \texttt{y} and the desired coefficients in \texttt{k},
\texttt{l}.  To verify the invariants:
\begin{proof}
Invariant (a) is the same one as for the Euclidean algorithm, which
we proved in lecture.  To check the other two invariants, note that at the
start $k=0, l=1, y = b$ and $0a+1b=b$ as required; also $u=1, v=0, x = a$
and $1a+0b=a$ as required.

So we now assume all the invariants hold for $u,v,k,l,x,y$, and prove they
hold for new values $u',v',k',l',x',y'$.  Invariant (c) holds for
$u'=k,v'=l,x'=y$ because of invariant (b) for $k,l,y$.  Now $k'= u - qk$
and $l'= v - ql$, where $q = \floor{x/y}$, so
\[k'a+l'b = (u-qk)a + (v-ql)b =ua+vb - q(ka+lb) = x - qy = y',\]
so invariant (b) holds for $k',l'$.
\end{proof}

\iffalse

\section*{Team Problems}

\begin{problems}

\problem Fast multiplication by adding and doubling from F97 pset4,
problem 2.

Consider the following multiplication algorithm, known as the ``Russian
peasant's multiplication'' to multiply numbers $x,y \in \naturals$.

The accumulator for the answer is register \texttt{a}; registers
\texttt{r}, \texttt{s} are for temporary storage.

\begin{verbatim}
r:=x; s:=y; a:=0;
Do until s=0:
 if even(s) then {r := 2r; s := s/2};
 if odd(s) then {a := a + r; r := 2r; s := (s-1)/2};
\end{verbatim}
The answer $xy$ will be left in the accumulator \texttt{a} when the
procedure terminates.

Here is an example of the execution of the algorithm.
\begin{verbatim}
 x     y     r     s     a
 -------------------------
 5     9     5     9     0
            10     4     5
            20     2     5
            40     1     5
            80     0    45
\end{verbatim}

Model the computation as a state machine.  Prove it terminates using a
derived variable.  Prove that it is correct using an invariant.

\textbf{Solution}: The state is given by the value in $(r,s,a)$.  $x$ and
$y$ can be included as part of the state or viewed as universal constants.

There are two types of state transitions (even or odd) as described in the
algorithm. The set of initial states consists of the single state $q_0 =
(x,y,0)$.

\begin{theorem}
The algorithm terminates in at most $\lceil \log_2 y \rceil$ steps.
\end{theorem}

\begin{proof}
Define the derived variable $f(r,s,a) = \lceil \log_2 s \rceil$.  Notice
that since at each step $s'$ becomes $s \over 2$ if $s$ is even and $s-1
\over 2$ if $s$ is odd, $f$ is decreasing.  So the length of an execution
is $\leq f(q_0) = f(x,y,0) \leq \lceil \log_2 y \rceil$.
\end{proof}

We prove the invariant $P(r,s,a): xy = rs+a$.

{\bf Base case: } In the initial state $r=x$ and $s=y$, so $P(x,y,0)$
asserts that $xy = xy +0$, which is true.

{\bf Inductive step:}
Consider a transition from $(r,s,a)$ to $(r',s',a')$.  We need to prove that
$P(r,s,a) \implies P(r',s',a')$.
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)/ 2$, and $a' = a + r$.
So $r's' + a' = 2r(s - 1)/ 2 + a + r$.
Reorganizing terms yields $r's'+a' = rs+a = xy$. \qed

{\bf Corollary:}
When $s=0$, $a = xy$.

\begin{proof}
By our invariant, we have
$P(r,0,a)$, that is $r0 + a = xy$, so $a=xy$.
\end{proof}


\problem Unisex Marriage stability counterexample.

We might better call this the Buddy Pairing Problem: an even number of
men, each with a preference ranking of all the others, to be paired as
``buddies'' in a stable way.

Derive an example of preferences for this unisex version of the mating
problem which shows that it is \emph{not} possible to always pair all the
players so that the marriages satisfy the stability criterion.  \hint
Consider just four men.


{\bf Solution}:  Let the buddy preferences of four men A, B, C, D be\\
A: BCD\\
B: CAD\\
C: ABD\\
D: $?\: ?\: ?$

Let Y and Z be any two among A, B, and C, and let X be the remaining one.
Notice that the first choices of A, B, C are arranged in a cycle, so that
X must be the first choice of either Y or Z.

Now for any matching into pairs, let Y and Z be the two among A, B, C who
are paired, and X be the one paired with D.  So one of Y and Z, say Y, has X
as his first choice.  But since A, B, C each rank D last, X prefers Y to
his own buddy, D.  So X, Y are a rogue couple.  Notice that the ranking of
A, B, C by D doesn't matter.

\problem

The judge says to the guilty defendant,
\begin{quotation}
\noindent ``Here is what is called a \emph{Petition Process}:
\begin{quotation}
\noindent You may name a number of times you may petition me.  Your
petitions may request a number of days to wait until you file your next
petition, or until this whole petition process ends.  Your petitions will
be granted.  When the number of days named in your last petition is
reached, the process will end.
\end{quotation}

\noindent Now you may request a number of petition processes in which you
would like to participate.  Your request will be granted, but at the end
of the last process, your head will be cut off.''
\end{quotation}
The defendant responds, ``I want to participate in 2 processes.''  The
judge says ``OK'', and the defendant asks to submit 4 petitions.  The
judge says ``OK,'' and the defendant files a petition asking for 10 days.
The judge says ``OK.''  10 days later, the defendant files a petition
asking for 20 days.  20 days later the defendant asks for 30 days, and 30 days
later for 40 days.

40 days later, he starts his second petition process, this time asking to
submit 3 petitions.  The first petition is for 100 days.  100 days later,
he asks for 200 days.  200 days later he asks for 300 days.  300 days
later his head gets cut off \texttt{:-(}.

Of course a smarter prisoner could have named much larger numbers and
lived out his natural lifetime.  But for the sake of argument, suppose the
prisoner (and the judge and hatchetman) will live as long as it takes to
get executed.  Prove that the prisoner will always eventually get his head
cut off.

{\bf Solution}:  By induction on the number of petition processes the
defendant first chooses.  The induction hypothesis is itself proved by
a subinduction on the number of petitions chosen at the start of a process.
The subinduction hypothesis is proved by induction on the number of days
the defendant chooses to wait before submitting the next petition.

\problem  Consider the Stable Marriage Problem when there are more men than
women.  Define what a set of stable marriages should mean in the presence
of bachelors.  Show that the Morning-Afternoon-Evening Protocol described
in lecture solves this Marriage Problem.

{\bf Solution}: The definition of \emph{rogue couple} is extended to
include a pair consisting of a bachelor and a married woman who prefers
the bachelor to her spouse.  A solution is a set of marriages in which all
woman are married (so all bachelors are men) and there are no rogue
couples.  The proof that the protocol yields a solution is now a routine
repeat of the case of equal numbers of men and women from lecture.

\end{problems}
\fi

 
\section*{Team Problems}

\begin{enumerate}
\item {\em Efficiency of Euclid's algorithm. } 
\begin{enumerate}
\item Show that Euclid's GCD algorithm uses at most $2 \log_2 x$ 
modulo operations. Assume that $x > y$. [Use derived variables]

Derived variable: $f((a,b)) = a$

\begin{claim}
If $x > y > 0$ then
for any pair of transitions, $q \rightarrow q_1 \rightarrow q_2$, 
$f(q_2) \leq \frac{1}{2}f(q)$, i.e. $f$ halves every two steps.
\end{claim}
{\em Proof. }
We consider two cases: 
\begin{enumerate}
 \item $f(q_1) \leq f(q)/2$. 

In this case, since $f$ is a decreasing variable, 
$f(q_2) \leq f(q_1)\leq f(q)/2$.

 \item $f(q_1) > f(q)/2$. 

Let $q = (a,b)$ with $a > b$. Then $q_1 = (b, a \bmod b)$ and
$q_2 = (a \bmod b, b \bmod a \bmod b)$. Therefore $f(q) = a, f(q_1) = b$
and $f(q_2) = a \bmod b$. We know that $ b > a/2$. Hence $a \bmod b < a/2$.
That is $f(q_2) \leq f(q)/2$.
\end{enumerate}
\qed

\item Let $F_n$ denote the $n^{th}$ Fibonacci number. Show that: 
   \begin{enumerate}
    \item If $2 \leq x \leq F_n$ then the algorithm uses at most 
          $n-2$ modulo operations.  Assume $x > y$.

 By Strong Induction.

{\em I. H. } If $2 \leq x \leq F_n$ then the algorithm uses at most 
          $n-2$ modulo operations.

{\em Base. } $x = 3$, $F_4 = 3$. 

{\em Step. }  Assume $P(z)$ for all $z < x$. We will prove $x$.

Suppose $2 \leq x \leq F_n$. Consider the next two transitions.
$$(x,y) \rightarrow (y, x \bmod y) \rightarrow (x \bmod y, y \bmod (x \bmod y))$$
Then $y + x \bmod y \leq x \leq F_n = F_{n-1} + F_{n-2}$.
We consider two cases:
\begin{enumerate}
\item $y \leq F_{n-1}$. 

Then the number of steps is at most 1 + number of steps from the 
state $(y,x \bmod y)$, which is at most $1 + n - 3$ by the 
induction hypothesis applied to $y$.

\item $y > F_{n-1}$. Therefore, $x \bmod y \leq F_{n-2}$. 

The number of steps to termination is at most 2 + number of steps
from the state $(x \bmod y, y \bmod (x \bmod y))$, which is at most 
$2 + n-4 = n-2$ steps by the I.H. applied to $x \bmod y$. 
\end{enumerate}  


    \item For $n \geq 2$, $F_n \geq (\frac{3}{2})^{n-2}$.

By strong induction on $n$.

I.H. $P(n) : F_n \geq (\frac{3}{2})^{n-2}$.

Base: $n=2$: $F_2 = 1 \geq (3/2)^0 = 1$.

Ind. Step: Assume $P(k)$ is true for $2 \leq k \leq n$.
To prove $P(n+1)$. 

$F_{n+1} = F_n + F_{n-1} \geq (\frac{3}{2})^{n-2} + (\frac{3}{2})^{n-3}$

$\geq (\frac{3}{2})^{n-3}(\frac{5}{2}) > (\frac{3}{2})^{n-3} (\frac{3}{2})^2$

$ \geq (\frac{3}{2})^{n-1}$
   
    \item Using the previous two results show that Euclid's algorithm
actually uses at most $1.71 \log_2 x$ modulo operations if $x \geq 2$.


Let $k$ be the smallest integer such that 
$(\frac{3}{2})^{k} \leq x \leq (\frac{3}{2})^{k+1}$
Therefore $x \leq F_{k+3}$, and we know that Euclid's algorithm takes
$k+1$ steps. But this is at most $\log_{3/2} x \leq 1.71 \log_2 x$.

\qed

    \end{enumerate}

\end{enumerate}

  
\item {\em Choosy mating. }

Note that in this question,
boys are assumed to be the aggressors, and they serenade the girls.

\begin{enumerate}
\item We have the mating problem again, but now both boys and girls are
more choosy about their partners. That is, among a set of $n$ boys
and $n$ girls, each boy is unwilling to 
drop below his $k^{th}$ choice and each girl is unwilliling to below
her $m^{th}$ choice. So it is possible that some of them are not 
married. How many pairs can we be sure of having in general ?


No, in general we cannot guarantee any marriages.
E.g. Let $n = 10, k = m = 5$. $B_1,B_2,..,B_5$ rank only $G_1,\ldots, G_5$,
$B_6,\ldots, B_{10}$ rank only $G_6,..,G_{10}$ and $G_1,\ldots,G_5$ rank
only $B_6,\ldots,B_{10}$ and $G_6,\ldots,G_{10}$ rank only $B_1,\ldots,B_5$.

\item What if only the boys were choosy, i.e., the girls are willing
to marry anyone (they still have a ranked list of preferences), but
the boys will not go below their $k^{th}$ choice?  How many pairs
will the algorithm from class (TMA) assure us?
\end{enumerate}

Set up a state machine as in the lecture. Each state is the set of
ranking lists with names possibly crossed off. Each transition
is one step of the algorithm, i.e. all boys who get a ``no'' answer
cross off the girl who said ``no'' off their lists.

Recall also the derived variables from lecture.

$n(q)$ number of names not crossed off on all the boys lists put together.   

$f_i(q)$ is the rank of girl that boy $i$ is currently pursuing.

$g_i(q)$ is the rank of the boy that girl $i$ said ``maybe'' to.

{\em Termination. }
 $n(q)$ is a decreasing variable. It starts at $nk$ so, the algorithm
terminates in $nk$ steps at most.

{\em At least $k$ marriages. }
$f_i(q)$ is a non-decreasing variable while $g_i(q)$ is a non-increasing 
variable.
If boy $j$ remains unmarried
then $f_j(q) = k+1$. But this means that boy $j$ serenaded all $k$
girls on his list. So at least $k$ girls have rejected him, because
they have been serenaded by boys with higher rank (according to them).
Consider any girl $i$ in this set of $k$ girls.  Girl $i$ has been serenaded
by a boy $p$ with $g_p(q) \leq n-1$ (since girl $i$ has rejected at least
one boy).  Further, boy $p$ clearly has girl $i$ within his top $k$
choices, else he would not have serenaded her.  Therefore girl $i$ is
definitely married at the end, either to boy $p$, or a higher-ranked boy.
%These $k$ girls have $g_i(q) \leq n$.
So $k$ girls are all definitely married at the end.

{\em No rogue couples. }
Identical to lecture.


Okay, so the TMA guarantees at least $k$ marriages. Is this the best
possible?  Yes, consider e.g., $n = 10, k=5$. For $i = 1$ to $5$
$B_i$ and $G_i$ have each other at the top of their lists. And for
$i = 6$ to $10$, $B_i$ has the list $G_1,..G_5$. So $B_6,..B_{10}$
will stay unmarried as all the girls on their lists have found 
better partners.

\end{enumerate}

\end{document}

