\documentclass[12pt]{article}   
\usepackage{latex-macros/course}% !! use the macros

%\showsolutions	 		% !! use to force solutions & skip query
%\hidesolutions			% !! use to force no solutions & skip query

\newcommand{\mfigure}[3]{\bigskip\centerline{\resizebox{#1}{#2}{\includegraphics{#3}}}\bigskip}

\instatements{
\renewcommand{\exampreamble}{	% !! renew \exampreamble 
  \textbf{Circle the name of your Tutorial Instructor}:
  \begin{center}
  \renewcommand{\arraystretch}{1.5}
  \begin{tabular}{lllll}
Ching & Christos & Grant & Paul & Zardosht
  \end{tabular}
  \end{center}
  \begin{itemize}
  \item 
  This quiz is \textbf{closed book}, but you may have one sheet of paper with
  notes on both sides.
  \item 
  There are four problems totaling 100 points. Total time is 80 minutes. 
  \item 
  Write your solutions in the space provided.  If you need more
  space, write on the back of the sheet containing the problem.
  Please keep your entire answer to a problem on that problem's page.
  \item 
  You may assume all of the results presented in class and in the
  assigned reading.
  \item  
  \textbf{Be neat and write legibly}.  You will be graded not only on
  the correctness of your answer, but also on the clarity with which
  you express it.
  \item 
  GOOD LUCK!
  \end{itemize}}}

\begin{document} 
\quiz{1}			% !! start the paper

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

\begin{examproblem}{25}
Recall that the Fibonacci numbers are defined as follows:

\begin{eqnarray*}
F_0 & = & 0 \\
F_1 & = & 1 \\
F_{n} & = & F_{n-1} + F_{n-2} \hspace{0.5in} \text{(for all $n \geq 2$)}
\end{eqnarray*}

The first few Fibonacci numbers are 0, 1, 1, 2, 3, 5, 8, and 13.
Define the matrix $M$ as follows:

\begin{eqnarray*}
M & = &
\left[
\begin{array}{cc}
1 & 1 \\
1 & 0
\end{array}
\right]
\end{eqnarray*}

Let $M^n$ denote the product of $n$ copies of the matrix $M$.  Use
induction to prove that the equation below holds for all $n \geq 1$:

\begin{eqnarray*}
M^n & = &
\left[
\begin{array}{cc}
F_{n+1} & F_n \\
F_n & F_{n-1}
\end{array}
\right]
\end{eqnarray*}

If you do not know how to multiply matrices, ask for help.  Some hints
are included to help you structure your argument, but \textbf{YOUR
TEXT ALONE MUST FORM A COMPLETE PROOF}.

\bigskip

\begin{fminipage}
\centerline{{\small State your proof method here.}}
\solution[\vspace{1.5in}]{We use induction on $n$.}
\end{fminipage}

\bigskip

\begin{fminipage}
\centerline{{\small State your induction hypothesis here.}}
\solution[\vspace{1.5in}]{The induction hypothesis is that:

\begin{eqnarray*}
M^n & = &
\left[
\begin{array}{cc}
F_{n+1} & F_n \\
F_n & F_{n-1}
\end{array}
\right]
\end{eqnarray*}
}
\end{fminipage}

\centerline{(continued on next page)}

\instatements{\newpage}

\begin{fminipage}
\centerline{{\small Address the base case here.}}
\solution[\vspace{2in}]{
The induction hypothesis holds for $n = 1$, because:

\begin{eqnarray*}
M^1 & = &
\left[
\begin{array}{cc}
1 & 1 \\
1 & 0
\end{array}
\right] \\
& = &
\left[
\begin{array}{cc}
F_2 & F_1 \\
F_1 & F_0
\end{array}
\right]
\end{eqnarray*}
}
\end{fminipage}

\bigskip

\begin{fminipage}
\centerline{{\small Address the inductive step here.}}
\solution[\vspace{4.25in}]{Now suppose that the induction hypothesis
holds for some $n \geq 1$.  Then we can show that it also holds for $n
+ 1$ as follows:

\begin{eqnarray*}
M^{n+1}
  & = & M \cdot M^n \\
  & = &
\left[
\begin{array}{cc}
1 & 1 \\
1 & 0
\end{array}
\right] \cdot 
\left[
\begin{array}{cc}
F_{n+1} & F_n \\
F_n & F_{n-1}
\end{array}
\right] \\
 & = & \left[
\begin{array}{cc}
F_{n+1} + F_n & F_n + F_{n-1} \\
F_{n+1} & F_n
\end{array}
\right] \\
 & = & \left[
\begin{array}{cc}
F_{n+2} & F_{n+1} \\
F_{n+1} & F_n
\end{array}
\right]
\end{eqnarray*}

The first step uses the definition of $M^n$.  The second step uses the
definition of $M$ and the induction assumption.  We carry out the
matrix multiplication in the third step and use the definition of
Fibonacci numbers in the final step.}
\end{fminipage}

\bigskip

\begin{fminipage}
\centerline{{\small Explain here why the claim follows from what you
showed above.}}  \solution[\vspace{1.5in}]{By the principle of
induction, what we have shown implies that the induction hypothesis
holds for all $n \geq 1$, which is the claim.}
\end{fminipage}

\end{examproblem}

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

\newpage

\begin{examproblem}{25} Five logic formulas are listed below.  The
domain of discourse is the natural numbers.  Indicate whether each
formula is a statement of:

\begin{description}

\item[I:] the \textbf{I}nduction Axiom

\item[S:] the \textbf{S}trong Induction Axiom

\item[L:] the \textbf{L}east Number Principle

\item[N:] \textbf{N}one of these

\end{description}

\vspace{0.25in}

\newcommand{\logsol}[1]{\instatements{\hfill\brule{0.5in}}\insolutions{\hfill#1}}

\bparts

\ppart[5] $[P(0) \wedge \forall n \geq 1\ ((\forall k < n\ P(k))
\implies P(n))] \implies \forall n\ P(n)$ \logsol{S}

\vspace{0.5in}

\ppart[5] $[P(0) \wedge \forall k\ (P(k) \implies P(k+1))] \implies
\forall k\ P(k)$ \logsol{I}

\vspace{0.5in}

\ppart[5] $[\forall n\ ((\forall k < n\ P(k)) \implies P(n))] \implies \forall n\ P(n)$ \logsol{S}

\insolutions{In the strong induction axiom, the base case is a special
case of the general case, so there is no need to state the base case
explicitly.  (Sorry for the tongue twister!)  This is discussed
further in the course notes on induction.}

\vspace{0.5in}

\ppart[5] $\exists n\ (P(n) \wedge \forall k < n\ \bar{P(k)})$ \logsol{N}

\insolutions{This looks like the least-number principle, but an
essential ingredient is missing.  In words, the statement above says,
``Every predicate is true for some smallest value of $n$.''  However,
this is a false assertion; some predicates are not true for any value
of $n$!}

\vspace{0.5in}

\ppart[5] $(\exists n\ P(n)) \implies \exists n\ (P(n) \wedge \forall k < n\ \bar{P(k)})$ \logsol{L}

\insolutions{This is a proper statement of the least-number principle.
In words, it says, ``{\em If a predicate is sometimes true}, then it
is true for some smallest value of $n$.''}

\eparts

\end{examproblem}

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

\newpage

\begin{examproblem}{25}
Each year, Santa's reindeer hold ``Reindeer Games'', from which
Rudolph is pointedly excluded.  The Games consist of a sequence of
matches, where one reindeer competes against another.  Draws are not
possible.

On Christmas Eve, Santa produces a linear ranking of all his reindeer.
If reindeer $p$ lost a match to reindeer $q$, then $p$ appears below
$q$ in Santa's ranking.  To prevent confusion, two reindeer may not
play a match if either outcome would lead to a cycle of reindeer,
where each lost to the next.  Here is an example of a cycle:

\mfigure{!}{1.75in}{figures/cycle}

Though it is only March, the 2004 Reindeer Games have already begun.
We can describe the results so far with a binary relation $L$ on the
set of reindeer.  Let $p L q$ mean that reindeer $p$ lost a match to
reindeer $q$.  Let $L^+$ be the corresponding positive-length path
relation\footnote{Thus, reindeer $p$ is related to reindeer $q$ by
$L^+$ if $p$ lost to $q$ or if $p$ lost to a reindeer who lost to $q$
or if $p$ lost to a reindeer who lost to a reindeer who lost to $q$,
etc.}.  Note that $L^+$ is a partial order.

\bigskip

On the following page you'll find a list of terms and a sequence of
statements.  Add the appropriate term to each statement.

\newpage

\begin{center}
\underline{Terms}

\begin{tabular}{rlrlrl}
1. & incomparable element &  6. & minimum element             & 11. & antichain \\
2. & comparable element   &  7. & chain               & 12. & maximal antichain \\
3. & maximal element     &  8. & total order         & 13. & irreflexive partial order \\
4. & maximum element     &  9. & topological sort    & 14. & reflexive partial order \\
5. & minimal element     & 10. & empty partial order
\end{tabular}
\end{center}

\centerline{\underline{Statements}}

\bparts

\ppart[2] An unbeaten reindeer is a \brule{3in} of

the partial order $L^+$. \solution{maximal element}

\ppart[2] A reindeer who has lost every match so far is

a \brule{3in} of the partial order $L^+$. \solution{minimal element}

\ppart[2] Two reindeer can not play a match if they are

\brule{3in}s of $L^+$. \solution{comparable element}

\ppart[2] A reindeer assured of first place in Santa's ranking is a

\brule{3in} of $L^+$. \solution{maximum element}

\ppart[2] A set of reindeer whose rankings relative to each other are
already

determined is a \brule{3in}. \solution{chain}

\ppart[3] A set of reindeer such that any two could still play a match

is a \brule{3in}. \solution{antichain}

\ppart[3] The fact that no reindeer loses a match to himself implies
that $L^+$

is a \brule{3in}.  \solution{irreflexive partial order}

\ppart[3] Santa's final ranking of his reindeer on Christmas Eve must
be

a \brule{3in} of $L^+$.  \solution{topological sort}

\ppart[3] No more matches are possible if and only if $L^+$ is

a \brule{3in}.

\solution{total order}

\ppart[3] Suppose that Santa has 8 reindeer.  If no more matches can
be played, what is the smallest possible number of matches already
played?  (No justification is required.)

\solution{7.  Call the reindeer $r_1, \ldots, r_8$.  Then no more
matches can be played if $r_1$ lost to $r_2$, $r_2$ lost to $r_3$,
etc.  If only six matches have been played, then the corresponding
digraph can not be even weakly connected.  In other words, there must
be two disjoint sets of reindeer $S$ and $T$ such that no reindeer in
$S$ has played a match against a reindeer in $T$.  Therefore, more
matches can be played; in particular, any reindeer in $S$ can play
against any reindeer in $T$.}

\eparts

\end{examproblem}

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

\newpage

\begin{examproblem}{25}
Define a {\em halfgraph} to be a graph with $2n$ vertices, all of
degree exactly $n$, for some $n \geq 1$.  (Here, the term ``graph''
refers to an undirected graph without self-loops and with at most one
edge between each pair of vertices.)

\bparts

\ppart[5] Can a halfgraph be bipartite?  If so, draw an example.  If
not, explain why not in 2-4 sentences.

\solution[\vspace{2.25in}]{Yes.  A single edge joining two vertices is
an example.}

\ppart[5] Can a halfgraph have more than one connected component?  If
so, draw an example.  If not, explain why not in 2-4 sentences.

\solution[\vspace{2.25in}]{No.  If the graph has two or more connected
components, then some connected component must have $n$ or fewer
vertices.  (Otherwise, there would be more than $2n$ vertices in all.)
Each vertex in this component can have degree at most $n - 1$.}

\ppart[5] For which values of $n$ must a halfgraph have an Euler tour,
assuming that it is connected?

\solution{All even $n$.  Recall that a connected graph has an Euler
 tour if and only if every vertex has even degree.}

\eparts

\newpage

GraphTech corporation has built cell phone towers all across the
United States.  Now they need your help with a couple technical
problems.

\bparts

\ppart[5] Each tower uses a certain frequency.  Two towers can not use
the same frequency if they are within 100 miles of each other.
GraphTech needs to know how many frequencies they must purchase.

Model this as a graph problem.  What are the vertices?  What are the
edges?  What graph-related quantity determines the minimum number of
frequencies required?

\solution[\vspace{2.5in}]{The vertices are towers.  There is an edge
between two towers if they are within 100 miles.  The minimum number
of frequencies is the chromatic number of the graph.}

\ppart[5] Callers across the United States will try to use GraphTech's
cell phone service the moment that service is activated.  A caller can
only contact a tower that is within 20 miles.  Each tower can support
up to 5 callers.  GraphTech must try to handle the load.

Model this as a graph problem.  What are the vertices?  What are the
edges?  State a necessary and sufficient condition based on Hall's
Theorem for GraphTech's network to be able to handle all the callers
in the first moment of operation.

\solution{There is one vertex for each caller, and there are five
vertices for each tower.  There is an edge between a caller and all
five vertices of each tower within 20 miles.  A matching for the
callers now assigns each caller to a tower such that no tower is
assigned more than 5 callers.  Thus, by Hall's Theorem, all callers
can be serviced if and only if every set of callers is within range of
at least one-fifth as many towers.}

\eparts

\end{examproblem}

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

\end{document}


