\documentclass[12pt,twoside]{article}
\input{macros-course}

\usepackage{amsmath}
\usepackage{latexsym}
\usepackage{graphics}
\usepackage{amsfonts}

\addtolength{\textheight}{.05in}

\begin{document}

\pset{1}{February 4, 2003}{Start of class on February 11}

%\newcommand{\solution}[1]{}                          % hide solutions
\newcommand{\solution}[1]{\textbf{Solution.} #1}    % show solution

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

\begin{problems}

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

\problem Suppose that you flip four coins.  Assume that each coin is
equally likely to come up heads or tails, regardless of how the other
three coins turn up.  The goal of this problem is to determine which
of the following two events is more likely:

\begin{enumerate}

\item Two coins come up one way and two come up the other.

\item Three coins come up one way and one comes up the other.

\end{enumerate}

\begin{problemparts}

\problempart What is the sample space for this experiment?

\solution{
Since this experiment has such a regular structure, we'll
dispense with the tree diagram.

The sample space consists of sixteen outcomes, each of which specifies
the outcomes of the four coin flips:

\[
\begin{array}{lccccr}
\{ & HHHH & HHHT & HHTH & HHTT \\
   & HTHH & HTHT & HTTH & HTTT \\
   & THHH & THHT & THTH & THTT \\
   & TTHH & TTHT & TTTH & TTTT & \}
\end{array}
\]
}

The outcome $HHHT$, for example, corresponds to the case where the
first three coins come up heads and the last comes up tails.

\problempart What subsets of this sample space constitute the two
events listed above?

\solution{
The first event consists of outcomes containing an equal number of
$T$'s and $H$'s.  There are six of these:

\[
\{ HHTT, HTHT, HTTH, THHT, THTH, TTHH \}
\]

The second event consists of outcomes containing three of one
orientation and one of the other.  There are eight of these:

\[
\{ HTTT, THTT, TTHT, TTTH, THHH, HTHH, HHTH, HHHT \}
\]
}

\problempart What is the probability of each outcome in the sample
space?

\solution{
Each outcome has probability $1/16$.
}

\problempart What are the probabilities of the two events?

\solution{
Recall that the probability of an event is defined to be
the sum of the probabilities of the outcomes in that event.
Therefore, we have:

\begin{eqnarray*}
\lefteqn{\Pr(\text{two one way, two the other})} \hspace{0.5in} \\
	& = &	\Pr\{HHTT\} + \Pr\{HTHT\} + \Pr\{HTTH\} \\
        &   &	+ \Pr\{THHT\} + \Pr\{THTH\} + \Pr\{TTHH\} \\
	& = &	\frac{1}{16} + \frac{1}{16} + \frac{1}{16} + 
		\frac{1}{16} + \frac{1}{16} + \frac{1}{16} \\
	& = &	\frac{3}{8}
\end{eqnarray*}

\begin{eqnarray*}
\lefteqn{\Pr(\text{three one way, one the other})} \hspace{0.5in} \\
	& = &	\Pr\{HTTT\} + \Pr\{THTT\} + \Pr\{TTHT\} + \\
	& &	\Pr\{TTTH\} + \Pr\{THHH\} + \Pr\{HTHH\} + \\
	& &	\Pr\{HHTH\} + \Pr\{HHHT\} \\
	& = &	\frac{1}{16} + \frac{1}{16} + \frac{1}{16} + \frac{1}{16} + 
		\frac{1}{16} + \frac{1}{16} + \frac{1}{16} + \frac{1}{16} \\
	& = &	\frac{1}{2}
\end{eqnarray*}
}

\problempart Which event is more likely?

\solution{
The second event, that three coins come up one way and one
comes up the other, is more likely.
}

\end{problemparts}

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

\problem A tournament consists of a sequence of matches between Team A
and Team B.  The winner of the tournament is the first team to win a
total of two matches.  In each match, the home team wins with
probability 0.6 and the away team wins with probability 0.4,
regardless of the outcomes of other matches.  The first match is
played on Team A's home field, the second match on Team B's field, and
the third match (if there is one) on Team A's field again.  We want to
determine the probability that Team A wins the tournament.

\begin{problemparts}

\problempart What is the sample space for this experiment?


\solution{
A tree diagram for this experiment is shown below.

\bigskip
\centerline{\resizebox{!}{3.5in}{\includegraphics{pset1-prob2.eps}}}
\bigskip

The sample space consists of six outcomes:

\begin{eqnarray*}
\{ AA, ABA, ABB, BAA, BAB, BB \}
\end{eqnarray*}

The outcome $BAB$, for example, corresponds to the situation where Team B
wins the first game, Team A wins the second, and Team B wins the third.
}

\problempart What subset of the sample space constitutes the event
that Team A wins the tournament?

\solution{
The event that Team A wins the tournament consists of three outcomes:

\begin{eqnarray*}
\{ AA, ABA, BAA \}
\end{eqnarray*}
}

\problempart What is the probability of each outcome in the sample space?

\solution{
The outcome probabilities are indicated in the tree diagram above.
}

\problempart What is the probability of the event that Team A wins the
tournament?

\solution{

Since the probability of an event is the sum of the outcome
probabilities, we have:

\begin{eqnarray*}
\Pr\{\text{Team A wins}\}
	& = & \Pr\{ AA \} + \Pr\{ ABA \} + \Pr\{ BAA \} \\
	& = & \frac{6}{25} + \frac{27}{125} + \frac{12}{125}
\end{eqnarray*}

}

\end{problemparts}

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

\problem For each of the following relations, determine whether it is
reflexive, whether it is symmetric, and whether it is transitive.

\begin{problemparts}

\problempart The relation ``$x$ is an ancestor of $y$'' on the set of humans.

\solution{
Reflexive: no \quad Symmetric: no \quad Transitive: yes
}

\problempart The relation ``$x$ is taking a class that $y$ is taking''
on the set of MIT students.

\solution{
Reflexive: yes \quad Symmetric: yes \quad Transitive: no

(The relation is not transitive because students $A$ and $B$ might be
taking one class together, $B$ and $C$ might be taking another class
together, but $A$ and $C$ are taking no classes together.)
}

\problempart The relation ``$x$ is an integral multiple of $y$'' on the set of positive integers.

\solution{
Reflexive: yes \quad Symmetric: no \quad Transitive: yes
}


\problempart The relation ``$x$ was born in the same month as $y$'' on the set of 6.042 students.

\solution{
Reflexive: yes \quad Symmetric: yes \quad Transitive: yes

(Since all three properties hold, this is an {\em equivalence
relation}.)
}

\problempart The relation defined below on the set $\{1, 2, 3\}$.

\[
\{ (1, 1), (2, 2), (3, 3), (1, 2), (2, 1), (1, 3), (3, 1) \}
\]

\solution{
Reflexive: yes \quad Symmetric: yes \quad Transitive: no

(The relation is not transitive because $(3, 1)$ and $(1, 2)$ are in
the relation, but $(3, 2)$ is not.)
}

\end{problemparts}

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

\problem Consider the following false claim and invalid proof:

\textbf{False Claim} {\em If a relation $R$ on a set $S$ is symmetric
and transitive, then it is also reflexive.}

{\em Invalid Proof.}
Let $x$ be an arbitrary element of $S$.  Choose another element $y \in
S$ such that $xRy$ holds.  By symmetry, $yRx$ holds as well.  By
transitivity, it follows that $xRx$.
$\Box$

\begin{problemparts}

\problempart Describe a relation that is symmetric and transitive, but
not reflexive.  Your relation may be a familiar one (as in parts (a) -
(d) in the preceding problem) or a new one that you define from
scratch (as in part(e)).

\solution{

The relation ``$x$ was born in the same month as $y$'' on the set of
6.042 students together with the color purple.  The relation is not
reflexive, because the color purple was not born in the same month as
itself; it was not born at all!  On the other hand, the relation
remains both symmetric and transitive.
}

\problempart Pinpoint the error in the proof as precisely as you can.

\solution{ The error arises in the statement, ``Choose another element
$y \in S$ such that $xRy$ holds.''  It may be the case that there
exists an $x$ for which no such element $y$ exists.

This is precisely the loophole we exploited in the counterexample
above.  We adjoined a new element (the color purple) to the set of
6.042 students.  The new element is unrelated to itself or any other
element already in the set.  Thus, we have an $x$ such that $xRy$
never holds.
}

\end{problemparts}

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

\problem Let $A$, $B$, and $C$ be sets.  Assume that $A \cap B \cap C
= \emptyset$.  Prove that:

\begin{eqnarray*}
A \cup B \cup C = (A - B) \cup (B - C) \cup (C - A)
\end{eqnarray*}

(If $X$ and $Y$ are sets, then $X - Y$ denotes the set of
elements in $X$ that are not also in $Y$.)

\solution{We prove the equality by showing that the left set contains
the right set and vice versa.  Let $S$ be the set on the left, $A \cup
B \cup C$, and let $T$ be the set on the right, $(A - B) \cup
(B - C) \cup (C - A)$.  In these terms, our objective
is to prove that $S = T$.

First, we show that $S$ is contained in $T$.  Let $x$ be an element of
$S = A \cup B \cup C$.  There are then six cases:

\begin{itemize}
\item $x \in A, x \not\in B, x \not\in C$: Since $x \in A$ and
$x \not\in B$, we have $x \in A - B$, and so $x \in T$.

\item $x \not\in A, x \in B, x \not\in C$: Since $x \in B$ and
$x \not\in C$, we have $x \in B - C$, and so $x \in T$.

\item $x \not\in A, x \not\in B, x \in C$: Since $x \in C$ and
$x \not\in A$, we have $x \in C - A$, and so $x \in T$.

\item $x \in A, x \in B, x \not\in C$: Since $x \in B$ and
$x \not\in C$, we have $x \in B - C$, and so $x \in T$.

\item $x \in A, x \not\in B, x \in C$: Since $x \in A$ and
$x \not\in B$, we have $x \in A - B$, and so $x \in T$.

\item $x \not\in A, x \in B, x \in C$: Since $x \in C$ and
$x \not\in A$, we have $x \in C - A$, and so $x \in T$.
\end{itemize}

In every case, $x \in T$ as well; therefore, every element of $S$ is
also an element of $T$, and so $S \subseteq T$.  (Note that the case
$x \in A, x \in B, x \in C$ does not exist, since $A \cap B \cap C =
\emptyset$ by assumption.)

Now we show that $T$ is contained in $S$.  Let $x$ be an element of $T
= (A - B) \cup (B - C) \cup (C - A)$.  There
are then three cases:

\begin{itemize}
\item $x \in A - B$:  This implies that $x \in A$, and so $x \in S$.
\item $x \in B - C$:  This implies that $x \in B$, and so $x \in S$.
\item $x \in C - A$:  This implies that $x \in C$, and so $x \in S$.
\end{itemize}

In every case, $x \in S$ as well; therefore, every element of $T$ is
also an element of $S$, and so $T \subseteq S$.  Since set $S$
contains set $T$ and vice versa, $S$ and $T$ must be the same set;
that is, $S = T$.
}

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

\problem The following problems require you to make
back-of-the-envelope calculations.  While these problems are
contrived, the ability to make estimates and rough calculations can
serve you well in checking your work and in thinking critically about
the world at large.  Later, the mathematical tools that we develop
will increase the number of situations that you can analyze.  For
these problems, try to give reasonably accurate answers.  Show your
assumptions and the calculations that lead to your conclusions.  You
will probably have to search for some information online; {\em please
cite your sources}.

\begin{problemparts}

\problempart Could the entire world population, working together,
drink Niagara Falls?  In other words, which is greater: the average
amount of water that flows over the falls each day or the average
amount of water that the world population drinks each day?

\solution{

The average flow rate of Niagara Falls is 212,000 cubic feet of water
per second.\footnote{http://www.iaw.com/\~{
}falls/origins.html\#Power} The average amount of water that flows
over the falls each day is therefore:

\begin{eqnarray*}
212,000 \frac{\text{ft}^3}{\text{sec}} \cdot
60 \frac{\text{sec}}{\text{min}} \cdot
60 \frac{\text{min}}{\text{hr}} \cdot
24 \frac{\text{hr}}{\text{day}} & = &
18,316,800,000 \frac{\text{ft}^3}{\text{day}}
\end{eqnarray*}

\noindent Using 6.25 billion for the world
population\footnote{http://blue.census.gov/cgi-bin/ipc/popclockw}, we
can compute the necessary consumption rate per person:

\begin{eqnarray*}
\frac{18,316,800,000 \frac{\text{ft}^3}{\text{day}}}
     {6.25 \cdot 10^9 \text{ people}}
   & \approx & 3 \frac{\text{ft}^3}{\text{person} \cdot \text{day}}
\end{eqnarray*}

\noindent Drinking 3 cubic feet of water per day is far beyond the
human norm, so the answer is {\em no}.
}

\problempart How long would you have to type to fill a
current-generation hard drive?  (Assume that only the characters you
enter manually are stored; you may not automatically generate files or
download {\em The Two Towers} from Bearshare.)

\solution{

A typical hard drive holds 40 gigabytes.  A fast typist can produce
about 100 words per minute or, say, 500 bytes per minute.  This
implies a typing time of about:

\begin{eqnarray*}
\frac{40 \text{ gigabytes}}{500 \frac{\text{bytes}}{\text{min}}}
	& = &	8 \cdot 10^7 \text{ min} \\
\end{eqnarray*}

Converting to years, we find:

\begin{eqnarray*}
\frac{8 \cdot 10^7 \text{ min}}{
	60 \frac{\text{min}}{\text{hr}}
	\cdot 24 \frac{\text{hr}}{\text{day}} 
	\cdot 365 \frac{\text{day}}{\text{yr}}}
	& = & 152 \text{ years}
\end{eqnarray*}

}

\problempart Is the United States more or less densely populated than
the world as a whole, excluding Antarctica?

\solution{ The land area of the United States is about 9.2 million
square kilometers, and the population of the United States is around
280
million\footnote{http://www.cia.gov/cia/publications/factbook/geos/us.html}.
Therefore, the population density of the United States is around:

\begin{eqnarray*}
\frac{280 \cdot 10^6 \text{ people}} {9.2 \cdot 10^6 \text{ km}^2}
	& = & 30 \frac{\text{people}}{\text{ km}^2}
\end{eqnarray*}

On the other hand, the total amount of land on earth is about 150
million square
kilometers\footnote{http://www.cia.gov/cia/publications/factbook/geos/xx.html\#Geo},
of which about 13 million square kilometers is Antarctica\footnote{http://www.scar.org/Antarctic\%20Info/Ant\%20stats.html}.  The
population of the world is about 6.25 billion, so we have a world
population density, excluding Antarctica, of about:

\begin{eqnarray*}
\frac{6.25 \cdot 10^9 \text{ people}}
     {150 \cdot 10^6 \text{ km}^2 - 13 \cdot 10^6 \text{ km}^2}
& = & 46 \frac{\text{people}}{\text{ km}^2}
\end{eqnarray*}

Therefore, the United States is much more sparsely populated than the
world as a whole.
}

\problempart Let's face it: Massachusetts is wretched in winter, but
Hawaii is wonderful.  How long would it take to transport Mauna Loa to
central Massachusetts, if all the dirt and rock entering the state
must be brought in by dump truck along the Mass Pike?  (Assume that
the Hawaiians will helpfully bring material to our state line as fast
as we can pick it up.)

\solution{ The volume of Mauna Loa is about 70,000 cubic kilometers or
$7 \cdot 10^{13}$ cubic
meters\footnote{http://gsa.confex.com/gsa/2002CD/finalprogram/abstract\underline{
}34712.htm}.  A really huge dump truck can carry about 200 cubic
meters of
material\footnote{http://www.equipmentcentral.com/north\underline{
}america/new\underline{ }equipment/machine\underline{
}list.cfm? machine\underline{ }type\underline{
}id=\&ecweb=KA\underline{ }Trucks}.  Therefore, the number of
truckloads needed would be:

\begin{eqnarray*}
\frac{7 \cdot 10^{13} \frac{\text{m}^3}{\text{mountain}}}
     {200 \frac{\text{m}^3}{\text{truck}}}
	& = &
	3.5 \cdot 10^{11} \frac{\text{trucks}}{\text{mountain}}
\end{eqnarray*}

\noindent Let's optimistically suppose we roll these monsters across
the border at a rate of one per second.  The number of seconds per
year is:

\begin{eqnarray*}
60 \frac{\text{sec}}{\text{min}} \cdot
60 \frac{\text{min}}{\text{hr}} \cdot
24 \frac{\text{hr}}{\text{day}} \cdot
365 \frac{\text{day}}{\text{year}}
	& = &	3.2 \cdot 10^7
\end{eqnarray*}

\noindent Dividing these quantities suggests that we'll need about
10,000 years to get the job done.
}

\problempart It is often said that the Great Wall of China is the only
man-made structure visible from the moon.  From how far away would you
have to view a human hair so that its apparent width to you would be
the same as the apparent width of the Great Wall to someone on the
moon?  Is the original claim reasonable?

\solution{ The Great Wall is about 10 meters across, and 350,000 km
from the moon\footnote{http://stardate.org/resources/ssguide/moon.html}.  A
human hair is about 100 microns across or about 100,000 times narrower
than the Wall\footnote{http://hypertextbook.com/facts/1999/BrianLey.shtml}.
Thus, the Great Wall is about as visible as a human hair 3.5 km away.
The claim is false.  }

\problempart It is often said that human activity may significantly
raise the concentration of carbon dioxide in the atmosphere, leading
to global warming.  But the planet is huge; only a tiny percentage of
the atmosphere is carbon dioxide, but that still amounts to {\em 750
gigatons}.  Suppose, pessimistically, that everyone on earth drives
like a typical American.  What would be the total mass of carbon
dioxide released each year by automobiles?  Is the original claim
reasonable?

\solution{ Burning a gallon of gasoline burns about 20 pounds of
carbon dioxide\footnote{http://globalwarming.enviroweb.org/ishappening/sources/sources\underline{ }co2\underline{ }facts3.html}.
If a typical driver covers about 10,000 miles per year at 20 miles per
gallon, then he or she consumes about 500 gallons of gasoline per
year.  Suppose that 4 billion people drive this much each year.  Then
the annual carbon dioxide output from cars alone is:

\begin{eqnarray*}
20 \frac{\text{lbs CO2}}{\text{gal}} \cdot 500 \frac{\text{gal}}{\text{driver}} \cdot 4 \cdot 10^9 \text{ drivers}
	& = & 4 \cdot 10^{13} \text{ lbs CO2} \\
	& = & 20 \text{ gigatons CO2}
\end{eqnarray*}

\noindent Such human activity could significantly raise the
concentration of carbon dioxide in the atmosphere, albeit over a
period of decades.  This is consistent with empirical observations
done at the Mauna Loa Observatory, whose days are numbered
approximately above.
}

\end{problemparts}

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

\end{problems}
\end{document}

