\documentclass[12pt,twoside]{article}
\usepackage{amsmath}
\usepackage{graphics}
\input{macros-course}
\begin{document}

%\newcommand{\solution}[1]{}
%\pset{4}{September 29, 1998}{Start of class on October 6, 1998}

\newcommand{\solution}[1]{\bigskip #1}
\psol{4}{October 9, 1998}

%\centerline{\bf Read ...}

\begin{problems}

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

\problem {\bf (10 points)}
Suppose that the dating game is played as described in class.  That
is, girls pursue their favorite boys, boys reject all but their top
prospect, and the game ends when each boy has a single candidate
remaining.  Prove or disprove each of the following assertions.

\begin{problemparts}

\problempart There is always some girl who gets her favorite boy.

\solution{The claim is false.  Suppose that there are three girls
named $A$, $B$, and $C$, and there are three boys named 1, 2, and 3.
Assume that the boys and girls have the preferences shown in the table
below.

\[
\begin{array}{l|l}
\text{girls' picks} & \text{boys' picks} \\ \hline
A : 1, 2, 3	&	1 : C, A, B \\
B : 2, 3, 1	&	2 : A, B, C \\
C : 2, 1, 3	&	3 : A, B, C
\end{array}
\]

The next table shows what happens during the dating game.  There is
one row for each boy, and a column for each stage of the game.  Each
entry lists all the girls pursuing a boy at a given stage.  The girl
rejected at each stage is crossed off.

\[
\begin{array}{c|l|l|l|l}
\text{boy}
& \text{stage 1}& \text{stage 2}& \text{stage 3}
& \text{stage 4} \\ \hline
1 & A		& \not\!\!A, C	& C		& C \\
2 & B, \not\!C	& B   		& A, \not\!\!B	& A \\
3 & 		&		&		& B
\end{array}
\]

In this case, every girl gets her second-favorite boy.
}

\problempart For every number of girls and boys, it is possible for
every boy to get stuck with his least favorite girl.

\solution{The claim is true.  If every girl has a different favorite
boy, then the algorithm terminates immediately and the boys'
preferences are irrelevant.  In particular, every boy may be stuck
with his least-favorite girl.}

\end{problemparts}

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

\problem {\bf (5 points)}
There are two girls, Alice and Betty, and two boys, Steve and Tim.
Alice prefers Steve, but the others' preferences are such that every
boy-girl dating arrangement is stable.  What are Betty, Steve, and
Tim's preferences?

\solution{
Steve prefers Betty, Betty prefers Tim, and Tim prefers Alice.

The key fact is that every dating arrangement must be stable.  If
Steve preferred Alice, then they would be a rogue couple if they were
not dating.  Therefore, Steve prefers Betty.  If Betty preferred
Steve, then they would be a rogue couple if they were not dating.
Therefore, Betty prefers Tim.  If Tim preferred Betty, then they would
be a rogue couple if they were not dating.  Therefore, Tim prefers
Alice.}

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

\problem {\bf (10 points)} Prove or disprove the following claim: for
some $n \geq 3$, there exists a set of boys' and girls' preferences
such that every dating arrangement is stable.

\solution{
The claim is false.

\begin{proof} We will use letters to denote girls and numbers to denoted boys.

There must be some girl $A$ rated worst by at most $n-2$ boys.  The
reason is as follows.  Each boy can rate exactly one girl worst.  If
each of the $n$ girls was rated worst by at least $n-1$ boys, then
there would have to be at least $n (n-1)$ boys in all.  But this is
false when $n \geq 3$, because then $n (n-1)$ exceeds $n$, the actual
number of boys.

Suppose that this girl $A$ is paired with the boy, 1, that she rates
worst.  Since at most $n-2$ boys rate girl $A$ worst, there is some
other boy, 2, that rates a different girl, $B$, worst.  Suppose that
boy 2 is paired with girl $B$.

Now girl $A$ and boy $2$ form a rogue couple.  Girl $A$ prefers every
other boy to her date, 1.  Similarly, boy $2$ prefers every other girl
to his date $B$.  Therefore, $A$ and $2$ prefer one another to their
current dates.
\end{proof}
}

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

\problem {\bf (15 points)} There are $n$ girls in a tennis tournament.
The tournament director hates to see anyone unhappy.  Therefore, he
plans to adjust the outcome of the tournament according to the
following rule: if a player loses all her matches, then he will change
all her losses to wins.  Of course, changing the results in this way
might create a new player who lost all her matches.  Therefore, his
plan is to continue applying his rule until there is no player who
lost all her matches.

The tournament is played and the results are reported to the director.
It so happens that the original tournament contains no cycles.  The
director now begins to adjust the results according to his rule.

\begin{problemparts}

\problempart Use a state machine model and the Invariant Theorem to
prove that the tournament director never creates a cycle through
repeated application of his rule.

\solution{
\begin{proof}
The proof uses the Invariant Theorem.  Define a state machine as
follows.  Let the set of states $Q$ be the set of tournaments.  Let
the set of start states $Q_0$ be an arbitrary acyclic tournament.  Let
the transition relation $\delta$ consist of tournament pairs $(T, T')$
where $T'$ is obtained from $T$ by applying the tournament director's
rule one time.

We will prove that the following invariant holds: the tournament is
acyclic.  In the start state, this invariant holds trivially.  For
each transition $T \rightarrow T'$ in $\delta$, assume that the
invariant holds for $T$ to prove that the invariant holds for $T'$.

Suppose that $p$ is the player with all losses in tournament $T$ that
has all wins in tournament $T'$.  There can be no cycle in $T'$ that
does not involve player $p$, since this would imply a cycle in $T$ as
well.  However, there can be no cycle in $T'$ that does involve
player $p$, since she wins all her matches in $T'$.

Thus the invariant is established by the Invariant Theorem.
\end{proof}
}

\problempart Prove that by applying his rule, the director can never
make everyone happy.  That is, no matter how many times he applies his
rule, there is still a player that lost all her matches.

\solution{
\begin{proof}
The preceding proof implies that the director never creates a
tournament with a cycle.  We will prove that if a tournament does not
contain a cycle, then there is player who lost all her matches.
Together these facts imply that the director can never create a
tournament where every player wins at least one match.

What remains is to prove that if a tournament does not contain a
cycle, then there is a player who lost all her matches.  We will
actually prove the contrapositive: if every player won at least one
match, then the tournament contains a cycle.

Form a sequence of players $p_1, p_2, \ldots, p_{n+1}$ as follows.
Let $p_1$ be an arbitrary player.  Let $p_2$ be one of the players
beaten by $p_1$, let $p_3$ be one of the players beaten by $p_2$, and
so forth.  We can form this sequence because every player won at least
one a match by hypothesis.  Since there are only $n$ players, some
player must appear more than once in the sequence $p_1, p_2, \ldots,
p_{n+1}$.  Let $p_j$ be the first player to appear a second time in the
sequence, and let $p_i$ be the first appearance of that player.  Then
the players $p_i, p_{i+1}, \ldots, p_{j-1}$ form a cycle.
\end{proof}
}

\end{problemparts}

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

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

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

\begin{problemparts}

\problempart Model the procedure with a state machine.

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

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

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

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

\problempart Prove that the invariant holds.

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

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

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

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

\problempart Prove that the procedure terminates.

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

\end{problemparts}

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

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

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

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

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

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

\problem {\bf (10 points)}

\begin{problemparts}

\problempart  Sum the following infinite series.

\[
\sum_{i=0}^{\infty} \frac{4^i - 3^i}{5^i}
\]

\solution{
\begin{eqnarray*}
\sum_{i=0}^{\infty} \frac{4^i - 3^i}{5^i}
	& = & \sum_{i=0}^{\infty} \left(\frac{4}{5}\right)^i -
	      \sum_{i=0}^{\infty} \left(\frac{3}{5}\right)^i \\
	& = & \frac{1}{1 - 4/5} - \frac{1}{1 - 3/5} \\
	& = & \frac{5}{2}
\end{eqnarray*}

In the first step, we split the one summation into two.  The second
step uses the formula for the sum of a geometric series.  The last
step is simplification.
}

\problempart For the following summation use the integral method to find
upper and lower bounds that differ by at most 0.1.  Note that you may
need to add the first few terms explicitly and then use integrals to
bound the sum of the remaining terms.

\[
\sum_{i=1}^{\infty} \frac{1}{i^2}
\]

\solution{
We can upper bound the summation as follows:

\begin{eqnarray*}
\sum_{i=1}^{\infty} \frac{1}{i^2}
	& \leq &	\frac{1}{1} + \frac{1}{4} + \frac{1}{9} +
			\int_3^{\infty} \frac{1}{x^2} \ dx \\
	& = &		\frac{1}{1} + \frac{1}{4} + \frac{1}{9} +
			\left( - \frac{1}{x} \right)_3^{\infty} \\
	& = &		\frac{1}{1} + \frac{1}{4} + \frac{1}{9} +
			\frac{1}{3} \\
	& = &		1.694\ldots
\end{eqnarray*}

We can lower bound the summation similarly:

\begin{eqnarray*}
\sum_{i=1}^{\infty} \frac{1}{i^2}
	& \geq &	\frac{1}{1} + \frac{1}{4} + \frac{1}{9} +
			\int_3^{\infty} \frac{1}{(x+1)^2} \ dx \\
	& = &		\frac{1}{1} + \frac{1}{4} + \frac{1}{9} +
			\left( - \frac{1}{x+1} \right)_3^{\infty} \\
	& = &		\frac{1}{1} + \frac{1}{4} + \frac{1}{9} +
			\frac{1}{4} \\
	& = &		1.611\ldots
\end{eqnarray*}
}

(The actual value of the summation turns out to be $\pi^2 / 6 =
1.644\ldots$.)

\end{problemparts}

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

\problem {\bf (10 points)} A banker loans \$100,000 to the Addams
family so that they can purchase a new dilapidated mansion.  At the
end of each year for the next 20 years, Morticia Addams will drop by
the bank to make a payment on the loan.  The banker will immediately
invest this returned money at a 7\% annual rate of return.

What annual payment should the banker require of the Addams family so
that his return after 20 years is the same as if he had invested the
whole amount at 7\% today instead of making the loan?

\solution{

Suppose that Morticia pays $p$ dollars at the end of each year for 20
years.  The banker can invest the first payment for 19 years, the
second payment for 18 years, etc.  Therefore, after 20 years his total
cash is:

\begin{eqnarray*}
\sum_{i=0}^{19} p \cdot 1.07^i
	& = &	p \cdot \sum_{i=0}^{19} 1.07^i \\
	& = &	p \cdot \frac{1.07^{20} - 1}{1.07 - 1}
\end{eqnarray*}

The second equation uses the formula for the sum of a finite
geometric series.

On the other hand, if the banker invests the money at 7\% today, then
after 20 years his total cash is $100,000 \cdot 1.07^{20}$.

Equating these two expressions and solving for $p$, Morticia's annual
payment, we find:

\begin{eqnarray*}
p \cdot \frac{1.07^{20} - 1}{1.07 - 1}
	& = & 100,000 \cdot 1.07^{20} \\
p	& = &	100,000 \cdot 1.07^{20} \cdot
		\frac{1.07 - 1}{1.07^{20} - 1} \\
	& \approx & \$9439.29
\end{eqnarray*}
}

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

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

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

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

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

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

/Grzzwk
\end{verbatim}

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

\begin{problemparts}

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

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

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

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

\solution{
Earth is safe.

\bigskip

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

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

\begin{itemize}

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

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

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

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

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

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

\end{problemparts}

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

\end{problems}
\end{document}
