% 35 copies

\documentclass[12pt,twoside]{article}
\usepackage{psfig}

\input{macros-course}
\newenvironment{claim}{\ \vspace{0.2cm} \\ {\bf Claim: \ }}{}
\begin{document}
\handout{hw1}{Optional Homework 1}{August 1, 2005}

\begin{problems}

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

\begin{problem}

% This illustrates sloppy case analysis.  By not being systematic, we miss
% the possibility that 10 makes a return trip.
%
%  Optimal:
%
%       50,100 cross, 100 returns          100 + 100 = 200 minutes
%       200,250 cross, 50 returns          250 + 50  = 300 minutes
%       50,100 cross                                   100 minutes
%
%       TOTAL --->                                     600 minutes

Four castaways must escape from an island to the mainland on a
makeshift raft.  Their weights are 50, 100, 200, and 250.  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.

\paragraph{Example:}
If 100 and 250 cross together, 250 minutes are used.  If 100 then
returns alone, another 100 minutes are used.

\begin{claim}
The four castaways can not all escape in less than 650 minutes.
\end{claim}

\begin{proof}
At least three trips and two return trips are required.  Since the
lightest person has weight 50, a minimum of 100 minutes are required
for the two return trips.  The three forward trips then require a
total of 550 minutes: 100 minutes for 50 and 100, 200 minutes for 50
and 200, and 250 minutes for 50 and 250.  Therefore, the total time
for all four people to cross is at least 100 + 550 = 650 minutes as
claimed.
\end{proof}

Determine whether this proof is valid.  If the proof is correct,
justify each step.  If the proof is wrong, pinpoint the precise error
and either provide a correct proof or find a better lower bound than
650 minutes.

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

\begin{problem}

% The induction hypothesis is of the form p => q.  In the inductive step,
% however, we treat the hypothesis as simply q.

Find the fallacy in the following proof, pinpointing the precise error
in reasoning.

\begin{claim}
If every vertex in a graph is adjacent to some other vertex, then the
graph is connected.
\end{claim}

\begin{proof}
The proof is by induction.  The induction hypothesis is that if every
vertex in an $n$-vertex graph is adjacent to some other vertex, then
the graph is connected.  For the base case, note that every graph with
a single vertex is connected, so the hypothesis is true vacuously.

In the inductive step, assume that the induction hypothesis holds for
every graph with $n \geq 1$ vertices in order to prove that it holds
for every graph with $n+1$ vertices.  Consider an $n+1$ vertex graph
in which every vertex is adjacent to some other.  Arbitrarily select a
special vertex $v$.  Observe that, excluding vertex $v$, the graph has
only $n$ vertices and is therefore connected by induction.  (This
connected portion of the graph is represented by the blob on the right
in the figure below.)

\bigskip
\centerline{\psfig{figure=false.eps,height=1.5in}}
\bigskip

To prove that the whole graph is connected, we must show that there
exists a path between every pair of distinct vertices $x_1$ and $x_2$.
There are two cases to consider.  If neither $x_1$ nor $x_2$ is vertex
$v$, then the path exists because both lie in the connected portion of
the graph.  Otherwise, one of the vertices is $v$ (say $x_1$) and the
other is not.  By assumption, $v$ is adjacent to some other vertex
(call it $u$), which must lie in the connected portion.  Again the
path exists: it runs from $x_1$ to $u$ to $x_2$ as shown in the
figure.
\end{proof}

\end{problem}

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

\end{problem}

\problem (\textit{Hard.})  A husband and wife host a dinner party for
five other couples.  During cocktails, as people arrive, lots of
handshaking goes on, but no one shakes hands with their spouse.
During the dinner, the host asks each other person at the party how
many people they have shaken hands with.  He is surprised to discover
that the eleven answers he receives from his guests and his wife are
all distinct.  How many hands did the hostess shake?

\end{problems}

\end{document}
