\documentclass[12pt]{article}
\usepackage{light}

\showsolutions

\begin{document}

\recitation{2}{February 4, 2005}

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

\section{Case Analysis}

The proof of a statement can sometimes be broken down into several
cases, which then can be tackled individually.

\subsection{The Method}

In order to prove a proposition $P$ using case analysis:
%
\begin{itemize}
\item Write, ``We use case analysis.''
\item Identify a sequence of conditions, at least one of which must
hold.  (If this is not obvious, you must prove it.)
\item For each condition:
\begin{itemize}
\item State the condition.
\item Prove $P$ assuming that the condition holds.
\end{itemize}
\end{itemize}
%
Often case-analysis arguments extend to several levels.  The most
difficult challenge in a case-analysis argument is try to decide
\textit{how} to break up the problem.  The most common error is
failing to construct a \textit{complete} set of cases.

\subsection{Example}

\begin{theorem}
There exist irrational numbers $p$ and $q$ such that $p$ raised to the
power $q$ is rational.
\end{theorem}

This is an ingenious proof, not the sort of thing one would think up
in a few minutes.

\begin{proof}
We use case analysis.  Let $v = \sqrt{2}^{\sqrt{2}}$.  There are two
cases:
%
\begin{itemize}
\item \underline{Case 1}: $v$ is rational.  Let $p = q = \sqrt{2}$.
Then $p^q = v$ is rational, so the claim holds.

\item \underline{Case 2}: $v$ is irrational.  Let $p = v$ and $q =
\sqrt{2}$.  Then:
%
\[
p^q = v^{\sqrt{2}} = \paren{\sqrt{2}^{\sqrt{2}}}^{\sqrt{2}} = \sqrt{2}^2 = 2
\]
%
Since 2 is rational, the claim holds.
\end{itemize}
\end{proof}

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

\newpage

\section*{Team Problem:  An Indirect Proof}

Here is the format of an indirect proof of a proposition $P$.

\begin{enumerate}

\item ``We use proof by contradiction.''

\item ``Suppose $P$ is false.''

\item Show this implies some sort of contradiction.

\item ``This is a contradiction.  Therefore, $P$ is true.''

\end{enumerate}

Give an indirect proof of the following theorem.

\begin{theorem}
$\log_5{8}$ is irrational.
\end{theorem}

\solution{
We use proof by contradiction.  Suppose that $\log_5 8$ is rational.
Then there exist integers $a$ and $b$ such that:
%
\[
\log_{5} 8 = \frac{a}{b}
\]
%
This implies that:
%
\begin{align*}
8 & = 5^{a/b} \\
8^b & = 5^a
\end{align*}
%
(Raising the first equation to the $b$-th power gives the second.)
Now the left side of the last equation is even and the right side is
odd.  This is a contradiction.  Therefore, $\log_{5} 8$ is
irrational.}

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

\newpage

\section*{Team Problem: A Case Analysis}

Four castaways must escape from an island to the mainland on a
makeshift raft.  Their weights are 5, 10, 20, and 25.  The raft can
hold at most two people.  The number of minutes required to paddle the
raft between the island and the mainland is equal to the weight of the
heaviest passenger aboard.  For example, if 10 and 25 cross together,
25 minutes are used.  If 10 then returns alone, another 10 minutes are
used.

\begin{claim}
It takes at least 65 minutes for all four castaways to escape.
\end{claim}

\begin{bogusproof}
At least three trips and two return trips are required.  Since the
lightest person has weight 5, a minimum of $2 \cdot 5 = 10$ minutes
are required for the two return trips.  The three forward trips then
require a total of 55 minutes: 10 minutes for 5 and 10, 20 minutes for
5 and 20, and 25 minutes for 5 and 25.  Therefore, the total time for
all four people to cross is at least 10 + 55 = 65 minutes as claimed.
\end{bogusproof}

\bparts

\ppart Where is the error in this argument?

\solution[\vspace{1in}]{The ``proof'' considers only the possibility
that person 5 shuttles everyone else to shore.}

\ppart Find a way to get everyone to shore in 60 minutes.

\solution[\vspace{1in}]{
\begin{itemize}
\item 5 and 10 cross
\item 5 returns
\item 20 and 25 cross
\item 10 returns
\item 5 and 10 cross
\end{itemize}
}

\newpage

\ppart Flesh-out the case-analysis proof of the following
theorem:
%
\begin{theorem}
The four castaways can not escape in 55 or fewer minutes.
\end{theorem}
%
Specifically, explain why there is no way for the four castaways to
escape in 55 or fewer minutes in each case.

\begin{proof}  We use case analysis.  We first consider the total number of
boat trips.
%
\begin{itemize}
\item \underline{Case 1}.  There are an even number of trips.

\solution[\vspace{0.6in}]{Then the boat ends up on the island.
Whoever brought it over last is stuck there.}

\item \underline{Case 2}.  There are three or fewer trips.

\solution[\vspace{0.6in}]{Then at most three people can escape the
island.}

\item \underline{Case 3}.  There are seven or more trips.

\solution[\vspace{0.6in}]{At least one trip takes 25 minutes.  This
trip excludes either 20 or 10, so another trip takes at least 10
minutes.  The remaining trips take at least 5 minutes each.  So the
total time is at least $25 + 10 + 5 \cdot 5 = 60$ minutes.}

\item \underline{Case 4}.  There exactly five trips.  Now we consider
trips involving 20 and 25.

\begin{itemize}
\item \underline{Case A}.  Multiple trips involve either 20 or 25.

\solution[\vspace{0.6in}]{Then there is at least one 25 minute trip
and at least one 20 minute trip.  The remaining trips require at least
5 minutes each for a total of $25 + 20 + 3 \cdot 5 = 60$ minutes.}

\item \underline{Case B}.  No trips involve either 20 or 25.

\solution[\vspace{0.6in}]{Then they are stuck on the island.}

\item \underline{Case C}.  Exactly one trip involves both 20 and 25.
We now consider trips involving person 10.

\begin{itemize}
\item \underline{Case i}.  An even number of trips involve 10.

\solution[\vspace{0.6in}]{Then 10 ends up on the island.}

\item \underline{Case ii}. Exactly one trip involves 10.

\solution[\vspace{0.6in}]{This implies that 5 is the only passenger on
one trip off the island.  Thus, there are at most five departures from
the island.  Someone must be in the boat for both trips back to the
island, so there are at least two returns.  But that means that
someone is left stuck on the island.}

\item \underline{Case iii}. Three or more trips involve 10.

\solution[\vspace{0.6in}]{Then the total time for all four castaways
to escape is at least $25 + 3 \cdot 10 + 5 = 60$.}

\end{itemize}
\end{itemize}
\end{itemize}

\end{proof}

\eparts

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

\end{document}
