\documentclass[11pt,twoside]{article}   
\usepackage{latex-macros/course}

%\hidesolutions         
%\showsolutions
\renewcommand{\coursecopyrightnames}{Dr.~Radhika~Nagpal}

\begin{document}
\inclassproblems{7M}

%% Pigeon-hole, Inclusion-exclusion, sum rule, product rule

% source: ?, problem repository
% last used: fall 01
% topics: false proofs for counting
\begin{problem} 

In each case, state whether the argument is correct or incorrect. If
incorrect, try to fix it. If correct, prove it.
\begin{problemparts}

\problempart Since there are 26 letters in the English alphabet, the
Product Rule implies that the number of four-letter English words is
$26^4$.

\solution{Incorrect. Not every four letter sequence is an English
word, \eg ``xxxx'' is not English. The best we can do here is say that
the number of four-letter English words is less than $26^4$.}

\problempart The number of 4-digit numbers which have a digit 7
somewhere is $4 * 10^3$, since by the sum rule, we must add the counts
for each position the 7 could be in; and since for each such position,
there are $10^3$ possible numbers by the product rule. (Assume that
the numbers can have leading zeros and that each digit can take values
0-9.)

\solution{Incorrect, since it double counts numbers containing more
than one 7 (for example 7707 is counted 3 times). The sum rule does
not apply if the sets being added are not disjoint. There are many
different ways of counting this, however one very elegant way of
counting this is by counting the complement --- the number of 4-digit
numbers with at least one 7 is just the number of all possible 4-digit
numbers minus the number of those which do \emph{not} contain 7,
namely, $10^4 - 9^4$. This is a common way of counting things where
{\em at least one} special event occurs.}

\end{problemparts}
\end{problem} 

% source: first part made up (RAD), second part Rosen 4.2.30 (first time used)
% topic: pigeonholing
\begin{problem} 
\begin{problemparts}

\problempart Say that I have a regular deck of 52 cards. How many
cards do I need to pull from the deck before I am guaranteed to have
two of the same suite? How many do I need to pull before I am
guaranteed to have two spades? \footnote{Note: there are four suites
(spades, clubs, diamonds and hearts) and there are 13 cards in each
suite.}

\solution{There are four suites, so by the pigeonhole principle, if I
draw five cards I am guaranteed to have two of the same suite. However
it could be a long time before I get two spades --- I could have the
bad luck of first drawing all hearts, clubs and diamonds (39 cards),
but then the next two cards I would draw would be spades. So 41 cards
would guarantee two spades.}

\problempart Prove that at a party where there are at least two
people, there are two people who know the same number of people
there. Assume that ``knowing'' is a two-way relationship.

\solution{Since there are $n$ people, the number of other people a
person could know is between 0 and $n-1$ inclusive. However, both 0
and $n-1$ cannot both occur. If there is a person who knows nobody,
then there cannot be a person who knows everybody. As a result, there
are only $n-1$ choices for how many people a person knows. By the
pigeonhole principle, since we have $n$ people and $n-1$ slots to put
them in, two must end up in the same slot.

{\em NOTE:} This problem can be restated as a graph theorem -- {\em An
undirected graph with $n$ nodes must have at least two nodes with the
same degree!}

}

\end{problemparts}
\end{problem} 

% % source: Spring '01, Tutorial 7 Problem 5
% % Pigeon-hole

% \begin{problem} 

% Let $S$ be the set of numbers $7, 77, 777, \ldots$. Prove that there
% is an element of $S$ that is divisible by $2001$.

% \solution{We use the pigeonhole principle.
% Let the pigeons be the elements $s \in S$, and
% the holes be the numbers $0 \ldots 2000$.  Let $s$ be placed in
% $s \bmod 2001$.

% Since there are more than 2001 elements of $S$, some hole must have
% two numbers, say $s_i$ and $s_j$, with $i$ and $j$ 7's respectively.
% Without loss of generality, assume that $i<j$.

% Then,
% $s_j - s_i = 77 \ldots 700\ldots0$ where there are $j-i$ 7's and $i$ 0's.
% So, $s_j - s_i = s_{j-i} \cdot 10^i$.
% Since $s_j \bmod 2001 = r = s_i \bmod 2001$,
% $s_j - s_i \bmod 2001 = 0$, so $2001 \mid (s_j - s_i)$.  But
% $gcd(2001,10^i) = 1$, so 2001 must divide $s_{j-i}$.

% }

% \end{problem} 


%%Fall 99, Tutorial 9

\begin{problem} \textbf{Counting Numbered Trees.}  

A \emph{numbered tree} is a tree whose vertex set is
$\set{1,2,\dots,n}$ for some $n \geq 2$.  We define the \emph{code} of
the numbered tree to be a sequence of $n-2$ integers from 1 to $n$
obtained by the following recursive process:
\begin{quotation}\noindent
If $n=2$, stop---the code is the empty sequence.  Otherwise, write down
the \emph{father} of the largest leaf, delete this \emph{leaf}, and
continue the process on the resulting smaller tree.
\end{quotation}
For example, the codes of a couple of numbered trees are shown in 

Figure~(\ref{fig:n-2}).
\begin{figure}[htb]
\begin{center}
\includegraphics[width=4in]{figures/n-2}
\end{center}
\caption{Coding Numbered Trees}
\label{fig:n-2}
\end{figure}

\begin{problemparts}

\problempart Describe a procedure for reconstructing a numbered tree from its
code.

\solution{
The key observation is that, given a code of length $n-2$, the numbers
between 1 and $n$ which \emph{do not appear} in the code must be leaves of
the tree.  Hence, the largest missing number is a leaf attached to the
first number of the code.  The rest of the tree can now be reconstructed
by deleting the first number in the code, henceforth ignoring the largest
leaf, and proceeding recursively on the rest of the code.  (We're using
the obvious fact that what's left after deleting a leaf from a tree is
another tree.)

More precisely, the reconstruction procedure applies to any finite tree
whose vertex set is totally ordered.  The procedure takes \emph{two}
parameters: the vertex set, $V$, and a length $\card{V}-2$ ``code''
sequence, $S$, of elements in $V$.  If $l$ is the largest element in $V$
which does not appear in $S$, and $f$ is the first element of $S$, then
the reconstructed tree is obtained by adding edge $(l,f)$ to the tree
reconstructed by calling the procedure recursively with first argument
$V-\set{l}$ and second argument equal to the code obtained by erasing the
initial $f$ from $S$.  The procedure terminates when $\card{V}=2$,
returning the edge between the two numbers in $V$.

To justify the key observation, note that any vertex that gets deleted by
the process and was not a leaf to begin with, must have been the father of
a previously deleted leaf, which means it would appear in the code.  So
the missing integers must have been leaves to begin with or must be one of
the two undeleted vertices left when the coding process terminates.  But
by the end of the process the two remaining vertices are leaves, and if
they weren't leaves to begin with, they must have become leaves by having
their sons deleted, which means they would not have been missing from the
code.  So the two vertices remaining at the end must also have been leaves
of the original tree.
}

\problempart How many numbered trees with $n$ vertices are there?

\solution{There are exactly as many $n$-vertex numbered trees a there
are length $n-2$ sequences of numbers between 1 and $n$.  So there are
$n^{n-2}$ numbered trees.
  
The reason there are the same number is that the tree reconstruction
procedure takes any such length $n-2$ sequence and returns an $n$-vertex
numbered tree whose code it is.  But the explanation above of why the
recursive reconstruction procedure is correct actually shows more: the
reconstructed tree is the \emph{unique} one with that code.

Now since every such length $n-2$ sequence is the code of some $n$-vertex
numbered tree, the coding procedure defines a surjection.  Since the tree
with that code is unique, the coding coding procedure also defines an
injection.  So the tree-coding function is a bijection.  Therefore the
number of numbered trees with $n$ vertices is the same as the number of
length $n-2$ sequences of integers between 1 and $n$.}

\end{problemparts}
\end{problem} 


\end{document}