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

%\backwardscompatibility	% !! use for backwards compatibility
%\showsolutions	 		% !! use to force solutions & skip query
%\hidesolutions			% !! use to force no solutions & skip query


%\def\brule#1{\instatements{\enskip\vrule width#1 height -1.1pt depth 1.5pt\relax}}

\newenvironment{closeitemize}{\begin{list}%
{$\bullet$}%
{\setlength{\itemsep}{-0.2\baselineskip}%
\setlength{\topsep}{0.2\baselineskip}}}%
{\end{list}}

\def\etree{\ang{}}

\instatements{
\renewcommand{\exampreamble}{	% !! renew \exampreamble 
  \textbf{Circle the name of your Tutorial Instructor}:
  \begin{center}
  \renewcommand{\arraystretch}{1.5}
  \begin{tabular}{llllll}
Ching & Edmond & Karen & Kilian & Mana & Min
  \end{tabular}
  \end{center}
  \begin{closeitemize}
  \item 
  This quiz is \textbf{closed book}, but you may refer to one page of
  personal notes.
  \item 
  There are five problems totaling 100 points. Total time is 80 minutes. 
  %% Problems are labeled with their point values.
  \item 
  Put your name on the top of {\bf every} page -- \emph{these
  pages may be separated for grading}.
  \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.
\iffalse
  \item 
  You may assume any of the results presented in class or in the
  assigned reading.
\fi
  \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{closeitemize}}}

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

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

\instatements{\newpage}

\begin{examproblem}{15}
We usually describe \emph{rooted trees} as a kind of graph, but we can
represent them formally as nested $n$-tuples.  Namely, rooted trees will
be defined recursively as follows:
\begin{itemize}

\item the \emph{empty tuple}, $\etree$, is a rooted tree.

\item if $T_1, T_2,\dots,T_n$ is a sequence of $n \ge 1$ rooted trees,
then the $n$-tuple $T\eqdef \ang{T_1, T_2,\dots,T_n}$ is a rooted tree.  

\end{itemize}
We define the function, $\emph{numleaves}(T)$, recursively on the
definition of rooted trees:
\begin{itemize}
\item $\emph{numleaves}(\etree) \eqdef 1$,
\item $\emph{numleaves}(\ang{T_1,\dots,T_n}) \eqdef \sum_{i=1}^n \emph{numleaves}(T_i)$.
\end{itemize}

\begin{problemparts}

\problempart[5] Give a similar recursive definition of the function,
$\emph{numinternal}(T)$, that equals the number of ``internal'' nodes of
the rooted tree $T$; that is, $\emph{numinternal}(T)$ is the number of
nodes of the tree that are not leaves.

\solution[\vspace{2in}]{
\begin{itemize}
\item  $\emph{numinternal}(\etree) \eqdef 0$,

\item $\emph{numinternal}(\ang{T_1,\dots,T_n}) \eqdef 1 + \sum_{i=1}^n
\emph{numinternal}(T_i)$.
\end{itemize}
}

\instatements{\newpage}

\problempart[10] We also define the function $\emph{numedges}(T)$
recursively on the definition of rooted trees:
\begin{itemize}
\item $\emph{numedges}(\etree) \eqdef 0$,
\item $\emph{numedges}(\ang{T_1,\dots,T_n}) \eqdef n+\sum_{i=1}^n \emph{numedges}(T_i)$.
\end{itemize}


Prove by structural induction that for any rooted tree, $T$,
\[
1 + \emph{numedges}(T) = \emph{numleaves}(T) + \emph{numinternal}(T).
\]

\solution{We prove the proposition, $P(T)$, above by structural induction.

\begin{proof}
\textbf{base case} ($T = \etree$):
\begin{align*}
1 + \emph{numedges}(\etree) & = 1 + 0 & \text{(by def of \emph{numedges})}\\
& = \emph{numleaves}(\etree) + \emph{numinternal}(\etree). & \text{(by def of
\emph{numleaves} \& \emph{numinternal})}
\end{align*}

\textbf{inductive case} ($T = \ang{T_1,\dots,T_n}$) for $n\ge 1$:

We may assume by induction that $P(T_i)$ holds for $i=1,\dots,n$.  Now
\begin{align*}
\lefteqn{1 + \emph{numedges}(\ang{T_1,\dots,T_n})}\\
& = 1+ n+\sum_{i=1}^n  \emph{numedges}(T_i)
         & \text{(by def of \emph{numedges})}\\
& = 1+ \sum_{i=1}^n (1 + \emph{numedges}(T_i))\\
& = 1 + \sum_{i=1}^n (\emph{numleaves}(T_i) + \emph{numinternal}(T_i))
   & \text{(by induction hypothesis)}\\
& = \paren{\sum_{i=1}^n \emph{numleaves}(T_i)} + \paren{1 + \sum_{i=1}^n
 \emph{numinternal}(T_i)}\\
& = \emph{numleaves}(\ang{T_1,\dots,T_n}) +
\emph{numinternal}(\ang{T_1,\dots,T_n})
  & \text{(by def of \emph{numleaves} \& \emph{numinternal})}.
\end{align*}
This proves $P(\ang{T_1,\dots,T_n})$.
\end{proof}

\textbf{Notes:} The most common error, and a serious one, in answers to
this problem were attempts to use induction on $n$ instead of structural
induction.  This approach breaks down at $n=1$ unless some other,
stronger, result is used as an induction hypothesis (which no one did).
Even if there had been a correct proof by induction on $n$, it would have
gotten little credit, since the problem explicitly asked for
\emph{structural} induction, which was the concept being tested in this
problem.  }

\end{problemparts}
\end{examproblem}


\instatements{\newpage}

\begin{examproblem}{20}
A newlywed couple want to borrow $d$ dollars from a mortgage company so
that they can purchase a small condo.  After a grace period of $g$ years
(that is, the first payment will be made exactly $g$ years after the money
is borrowed), they will make $n$ annual payments, after which the loan will
be considered to be paid off.  The mortgage company will immediately
invest each payment it receives at an $a$\% annual rate of return, \eg a
\$1 investment will yield $\$R$ after one year, where $R \eqdef 1+ a/100$.

When the loan is paid off, the mortgage company wants to wind up with at
least as much money from investing the newlywed's payments as they would
have if they had invested the whole $d$ dollar loan at $a$\% starting on
the day of the loan.

\bparts

\ppart[15] Write a closed form formula in $d, g, n$ and $R$ for the least
annual payment, $p$, that the mortgage company must ask from the
newlyweds.


\solution[\vspace{4in}]{
The company requires
\[
p = \frac{dR^{g+n-1}(R-1)}{R^n - 1}.
\]
We derive this bound as follows:

Suppose the couple pays $p$ dollars at the end of each year.  The company
can invest the first payment for $n-1$ years, the second payment for $n-2$
years, \etc, so that after $n$ payments their total cash is:
\begin{align}
\sum_{i=1}^{n} p \cdot R^{i-1}
& =  \sum_{i=0}^{n-1} p \cdot R^i\notag\\
& =  p \frac{R^n - 1}{R - 1}.\tag{*}
\end{align}

On the other hand, the last payment is made after $g+n-1$ years.  If the
company invested the $d$ dollars today, then their total cash is $d
R^{g+n-1}$.  The amount~(*) must be at least as large as this, so
\begin{eqnarray*}
p \frac{R^n - 1}{R - 1} & \geq & dR^{g+n-1}\\
p &\geq& \frac{dR^{g+n-1}(R-1)}{R^n - 1}.
\end{eqnarray*}
}

\ppart[5] Suppose the numbers, $d,n,$ and $a$ are fixed.  Then the
required payment is a function, $p(g)$, of the number of years, $g$, in
the grace period.  Assuming (unrealistically) that $g$ could be
arbitrarily large, give the least real number, $k$, such that $p(g) =
O(g^k)$, or explain why there is no such $k$.

\solution{No such $k$, because $(dR^{g+n-1}(R-1))/(R^n - 1)=
\Theta(R^g)$ which grows exponentially in $g$ and so is not bounded by any
polynomial in $g$.}

\eparts

\end{examproblem}


\instatements{\newpage}

\begin{examproblem}{15}
Note: Use of a calculator or other computational aid is \emph{unnecessary}
for this problem and is \textbf{not permitted}.

\bparts

\ppart[7] Explain why the fact that $7^{1111110} \equiv 96368
\pmod{1111111}$ directly implies that 1111111 cannot be prime, without the
need to find the factors of 1111111.

\solution[\vspace{2.5in}]{Suppose 1111111 was prime.  Then since 7 is
obviously not divisible by 1111111, we have by Fermat's Theorem:
\[
7^{1111110} = 7^{1111111 -1} \equiv 1 \pmod{1111111}.
\]
But
\[
7^{1111110} \equiv 96368 \not\equiv 1 \pmod{1111111},
\]
a contradition.}

\iffalse

\ppart[6] What is the value of $3^{1025} \text{ rem } 40$?  Show your
work.

\solution[\vspace{2in}]{
\[
\begin{array}{l}
3^2 \equiv 9 \pmod{40} \\
3^4 \equiv (3^2)^2 \equiv 9^2 \equiv 81 \equiv 1 \pmod{40} \\
3^8 \equiv (3^4)^2 \equiv 1^2 \equiv 1 \pmod{40} \\
3^{16} \equiv (3^8)^2 \equiv 1^2 \equiv 1 \pmod{40}
\end{array}
\]

Similarly, 3 raised to all higher powers of 2 must be congruent to 1
modulo 40.  Therefore:

\[
3^{1025} \equiv 3^{1024} \cdot 3 \equiv 1 \cdot 3 \equiv 3 \pmod{40}
\]
}
\fi


\ppart[8] Recall that for all $u, v \in \mathbb{N}$, there exist
integers $x$ and $y$ such that:
\begin{equation}\label{xy}
xu + yv = \gcd(u, v)
\end{equation}
Suppose that $r$ and $n$ are positive integers such that $\gcd(r, n) = 1$.
Use~(\ref{xy}) to give a short proof that there must exist an integer, $s$,
such that $r \cdot s \equiv 1 \pmod{n}$.

\solution{By the fact given, there are integers $x$ and $y$ such that $xr
+ yn = 1$.  This implies $yn = 1 - xr$ and so $n \mid (1 - xr)$ which
means that, by definition, $xr \equiv 1 \pmod{n}$.  So let $s \eqdef x$.}

\eparts

\end{examproblem}

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

\instatements{\newpage}

\begin{examproblem}{30}
Solve the following counting problems.  You may leave factorials and
binomial coefficients in your solutions.  No explanation is required.

\bparts

\ppart[6] Suppose that two identical 52-card decks of cards are mixed
together.  In how many ways can the cards in this double-size deck be
arranged?

\solution[\vspace{3in}]{
\[
\frac{(52 \cdot 2)!}{2^{52}}
\]
}

\ppart[6] How many different solutions are there to the following
equation, if all variables must be \textbf{even}, nonnegative integers?
\[
y_1 + y_2 + y_3 + y_4 + y_5  =  1000.
\]

\solution[\vspace{3in}]{There is a bijection between solutions to this
equation and ways of assigning 500 identical balls to 5
distinguishable bins.  (If $k$ balls are assigned to bin $i$, then
$y_i = 2k$.)  Therefore, the number of solutions is:

\[
\binom{500 + 4}{4} = \binom{500 + 4}{500} = \frac{(500 + 4)!}{4!\ 500!}
\]
}

\instatements{\newpage}

\ppart[6] Theory Hippo wants to travel from point (0, 0) to point (20,
20) using only steps that either increment the first coordinate by 1
or else increment the second coordinate by 1.  How many different
paths can he choose from?

\solution[\vspace{3in}]{He must choose 20 of the 40 steps of the first
type and the remainder are of the second type.  Therefore, the number
of different paths is:

\[
\binom{40}{20} = \frac{40!}{20!\ 20!}
\]
}

\ppart[6] Suppose there are Bottomless Pits of Utter Annihilation at
points (5, 5) and (10, 10).  How many of the paths available to Theory
Hippo do not cross a Bottomless Pit?

\solution{By inclusion-exclusion, the number of paths that cross a pit
is:
\[
\binom{10}{5} \cdot \binom{30}{15} + \binom{20}{10} \cdot \binom{20}{10}
- \binom{10}{5} \cdot \binom{10}{5} \cdot \binom{20}{10}.
\]

Consequently, the number of paths that do not cross a Bottomless Pit of
Utter Annihilation is:
\[
\binom{40}{20} - 
\binom{10}{5} \cdot \binom{30}{15} - \binom{20}{10} \cdot \binom{20}{10}
+ \binom{10}{5} \cdot \binom{10}{5} \cdot \binom{20}{10}.
\]
}

\instatements{\newpage}

\ppart[6] Below is a combinatorial proof of an equation.  Fill in the
empty boxes in the Theorem statement with the proper expressions.

\begin{theorem*}
\begin{eqnarray*}
\fbox{\begin{minipage}{2.5in}
\vspace{1in}
\hspace{1in}
\end{minipage}}
& = &
\fbox{\begin{minipage}{2.5in}
\vspace{1in}
\hspace{1in}
\end{minipage}}
\end{eqnarray*}
\end{theorem*}

\begin{proof}
Stinky Peterson owns $n$ newts, $t$ toads, and $s$ slugs.
Conveniently, he lives in a dorm with $n + t + s$ other students.
(The students are distinguishable, but creatures of the same variety
are not distinguishable.)  Stinky wants to put one creature in each
neighbor's bed.  Let $W$ be the set of all ways in which this can be
done.

On one hand, he could first determine who gets the slugs.  Then, he
could decide who among his remaining neighbors has earned a toad.
Therefore, $|W|$ is equal to the expression on the left.

On the other hand, Stinky could first decide which people deserve
newts and slugs and then, from among those, determine who truly merits
a newt.  This shows that $|W|$ is equal to the expression on the
right.

Since both expressions are equal to $|W|$, they must be equal to each
other.
\end{proof}

\solution{
\begin{eqnarray*}
\binom{n + t + s}{s} \cdot \binom{n + t}{t}
& = &
\binom{n + t + s}{n + s} \cdot \binom{n + s}{n}
\end{eqnarray*}
}

\eparts
\end{examproblem}



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

\instatements{\newpage}

\begin{examproblem}{20}
Sally Smart just graduated from high school.  She was accepted to
three top colleges.

\begin{itemize}

\item With probability $4/12$, she attends Yale.

\item With probability $5/12$, she attends MIT.

\item With probability $3/12$, she attends Little Hoop Community College.

\end{itemize}

Sally will either be happy or unhappy in college.

\begin{itemize}

\item If she attends Yale, she is happy with probability $4/12$.

\item If she attends MIT, she is happy with probability $7/12$.

\item If she attends Little Hoop, she is happy with probability
$11/12$.

\end{itemize}

\bparts

\ppart[4] A tree diagram for Sally's situation is shown below.  On the
diagram, fill in the edge probabilities and at each leaf write the
probabilty of that outcome.

\vspace{0.5in}
\centerline{\includegraphics[height=4in]{q2-sally}}
\bigskip

\instatements{\newpage}

\ppart[4] What is the probability that Sally is happy in college?

\solution[\vspace{2in}]{The probability that she is happy is equal to
the sum of the probabilities of the outcomes marked with an H: $16/144
+ 35/144 + 33/144 = 84/144 = 7/12$.}

\ppart[4] What is the probability that Sally Smart attends Yale, given
that she is happy in college?

\solution[\vspace{2in}]{
\begin{eqnarray*}
\pr{\text{attends Yale} \mid \text{happy}}
	& = & \frac{\pr{\text{attends Yale} \cap \text{happy}}}
		{\pr{\text{happy}}} \\
	& = & \frac{(4/12) \cdot (4/12)}{(7/12)} \\
	& = & 4 / 21
\end{eqnarray*}
}

\ppart[4] Show that the event that Sally attends Yale is \textbf{not}
independent of the event that she is happy.

\solution[\vspace{2in}]{These events are independent only if:

\begin{eqnarray}
\pr{\text{attends Yale} \mid \text{happy}} & = & \pr{\text{attends Yale}}
\end{eqnarray}

or $\pr{\text{happy}} = 0$.  However, the left side is $4/21$, the
right is $4/12$, and the probability that she is happy is nonzero.}

\ppart[4] Show that the event that Sally Smart attends MIT \textbf{is}
independent of the event that she is happy.

\solution{These events are independent if:

\begin{eqnarray*}
\pr{\text{attends MIT}} \cdot \pr{\text{happy}}
	& = & \pr{\text{attends MIT} \cap \text{happy}}
\end{eqnarray*}

The left side is equal to $(5/12) \cdot (7/12) = 35/144$.  According
to the tree diagram, the right side is equal to $35/144$ as well.}

\eparts

\end{examproblem}


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

\end{document}

