\documentclass[12pt,twoside]{article}
\input{macros-course}

\askaboutsolutions

\begin{document}

%% TUTORIAL 8: Pigeon-hole, Inclusion-exclusion, sum rule, product rule

\ifshowsolutions
  \tutsol{8}{October 25, 2001}{\stamp}
\else
  \tutprobn{8}{October 25, 2001}{\stamp}
\fi

\begin{problems}

% Pigeonhole Principle
% from Spring 99 pset 7

% source: http://www.math.ucla.edu/~burchard/113.2.00s/midterm1.pdf
% sum/product rule

\problem In each case, state whether the argument is correct or incorrect,
and explain why.  If incorrect, try to fix 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$.

\solnospace{Incorrect.  Not every four letter sequence is an English word,
\eg ``xxxx'' is not English.  In fact, there are considerably fewer
four-letter English words than $26^4$.  There is no fix to this mistaken
application of the Product Rule.}

\problempart The number of 4-digit (decimal whole) 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
numbers can have leading zeros)

\solnospace{Incorrect, since it double counts numbers containing more than
one 7 (for example 7707 is counted 3 times).  The sum rule does not apply.
Correct answer is the number of all possible 4-digit number minus the
number of those which do \emph{not} contain 7, namely, $10^4 - 9^4$.}

\end{problemparts}

\problem State the Principle of Inclusion-Exclusion for the case of three
sets $A_1,A_2,A_3$ (without looking it up first, if possible).

\solnospace{
$\card{A_1 \union A_2 \union A_3} =  \card{A_1} + \card{A_2} + \card{A_3} -
\card{A_1 \intersect A_2} - \card{A_1 \intersect A_3} - \card{A_2
\intersect A_3} + \card{A_1 \intersect A_2 \intersect A_3}$.
}


%%Fall 99, Tutorial 9

\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}

\bparts

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

\solnospace{
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.
}

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

\solnospace{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$.}

\eparts 


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

\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$.

\solnospace{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}$.

}


\iffalse

% Spring '01, Tutorial 8 Problem 5
% Another Inclusion-Exclusion
\problem Recall that $F_n$ denotes the $n$th Fibonacci number.

\bparts

\ppart Which Fibonacci numbers are even?  Prove it!

\solnospace{Every third one is even, starting from $F_0 = 0$.  Prove this
by proving that $F_n$ is even iff $3 \mid n$ by strong induction on $n$.
The base cases are that $F_0$ is even and $F_1$ is odd.  Now consider
\[
F_{n+1} \eqdef F_n + F_{n-1}.
\]
There are three cases, depending on what $n$ is congruent to modulo 3.

\emph{Case 0}: $n \equiv 0 \pmod 3$.  Then $n+1 \equiv 1 \not\equiv 0
\pmod 3$.  So we must prove that $F_{n+1}$ is odd.  Now $n - 1 \not\equiv 0
\pmod 3$, so by hypothesis, $F_n$ is even and $F_{n-1}$ is odd, so $F_{n+1}$
is odd as required.
\emph{Case 1}: $n \equiv 1 \pmod 3$.  Then $n+1 \equiv 2 \not\equiv 0
\pmod 3$.  So we must prove that $F_{n+1}$ is odd.  Now $n-1 \equiv 0 \pmod
3$, so by hypothesis, $F_n$ is odd and $F_{n-1}$ is even, so $F_{n+1}$ is
odd as required.

\emph{Case 2}: $n \equiv 2 \pmod 3$.  Then $n+1 \equiv 0 \pmod 3$.  So we
must prove that $F_{n+1}$ is even.  Now $n-1 \equiv 1 \pmod 3$, so by
hypothesis, $F_n$ is odd and $F_{n-1}$ is odd, so $F_{n+1}$ is even as
required.}

\ppart The previous result is a special case for $m=3$ of the assertion
that $F_m \mid F_n$ iff $m \mid n$ for all $m,n \in \naturals, m > 0$.
Assuming this assertion for the time being, how many Fibonacci numbers
up to $F_{100}$ are \emph{not} multiples of 3 or 8 or 13?

\solnospace{Every 4th number is multiple of $F_4 = 3$, every 6th number is
multiple of $F_6 =8$, and every 7th number is multiple of $F_7 = 13$.

Now, total = 100 (starting with $F_1$ and going to $F_{100}$)\\
mult of 3 = $\floor{100/4} = 25$,\\
mult of 8 = $\floor{100/6}= 16$,\\
mult of 13 = $\floor{100/7}=14$,\\
mult of 3 and 8 = $\floor{100/12}=8$, (since 12 is lcm$(4,6)$),\\
mult of 3 and 13 = $\floor{100/28}=3$ (since 28 is lcm$(4,7)$),\\
mult of 8 and 13 = $\floor{101/42}=2$, (since 42 is lcm$(6,7)$),\\
mult of 3 and 8 and 13 = $\floor{101/84}=1$, (since 84 is lcm$(4,6,7)$).

So the answer is $100 - 25 - 16 - 14 + 8 + 3 + 2 - 1 = 57$.
}

\eparts

\fi

\iffalse

%%%%%%%%%%%% NOT INCLUDED - POSSIBLE %%%%%%%%%%%%%%%%%%%%%%
% Final Exam, Spring 01 , Problem 4
% pigeon hole

\problem 
A professor teaching 6.042 gives a multiple choice quiz that has 10
questions, each of which has 4 possible answers (a,b,c,d). What is the
\emph{minimum} number of students that must be in the professor's
class in order to guarantee that at least three answer sheets must be
identical? (assume that no answers are left blank).  Justify your
answer.

\solnospace{There are $4^{10}$ possible answers. By the strong pigeonhole
principle, in order to have the desired property, we need at least $2\cdot
4^{10}+1$ students.}

\ppart Let $s_1, s_2,\ldots, s_{101}$ be 101 strings of 1's and 0's that
are at most 9 digits long. Prove that there exist 2 strings, $s_i$ and
$s_j$, with $i\neq j$, that contain the same number of 0's and the same
number of 1's. (For example, strings 110001001 and
%101000110 contain the same number of 0's and the same number of 1's)
[Note: You actually need much fewer than 101 strings to prove the
above---you can give a proof using a lower number of strings if you
would like to (for equal credit).]

\solnospace{\ssl We can associate a pair $(a,b)$ with each string, where
$a$ is the number of 0's and $b$ is the number of 1's. There are
% \emph{at most} 100 such pairs (actually, the constraint about the
length of the string implies that there are fewer than 100). We can
consider the pairs to be the holes and the strings to be the
pigeons. Since there are more pigeons than holes, one hole must have
at least 2 pigeons. Two strings that are associated with the same
pair will have the same number of 0's and the same number of 1's.
}
\fi

\iffalse
% ps8 : f95 : 3

\problem

Consider placing $n$ distinguishable books on $r$ distinguishable
shelves.

\bparts

\ppart If the order of books on each shelf doesn't matter, how many
distinct placements are there?

\solnospace{Product rule: $r$ shelves for each of $n$ books, so $r^n$.}

\ppart If order on the shelf matters, how many distinct placements
are there?

\solnospace{ For the first book there are $r$ choices. For the next book
there are $r+1$ choices since we can think of the first book as splitting
the shelf it is put on into two shelves. Similarly for the third book
there are $r+2$ choices. In this way we see that the total number of ways,
by the product rule, is $r\times (r+1) \times (r+2) \ldots (n+r-1) $.}

\eparts
\fi

\end{problems}

\end{document}


