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

\renewcommand{\coursecopyrightnames}
{\href{http://theory.csail.mit.edu/~meyer}{Prof.~Albert~R.~Meyer}}
\renewcommand{\coursecopyrightyear}{2005}

\newtheorem{mathrule}{Rule}
\newtheorem*{mathrule*}{Rule}

\newcommand{\rem}{\operatorname{\,rem\,}}


\begin{document} 
\inclassproblems{9, Fri.}

%Pigeonholing

\begin{problem}
Solve the following problems using the Pigeonhole Principle.  For each
problem, try to identify the {\em pigeons}, the {\em pigeonholes}, and
a {\em rule} assigning each pigeon to a pigeonhole.

\bparts

\ppart In a room of 500 people, there exist two who share a birthday.

\solution{The pigeons are the 500 people.  The
pigeonholes are 366 possible birthdays.  Map each person to his or her
own birthday.  Since there 500 people and 366 birthdays, some two
people must have the same birthday by the Pigeonhole Principle.}

\ppart Every MIT ID number starts with a 9 (we think).  Suppose that each
of the 101 students in 6.042 sums the nine digits of his or her ID number
and doubles the result.  Explain why two students' results must be the
same.

\solution{The students are the pigeons, the possible results are the
pigeonholes, and we map each student to the result calculated from his or
her MIT ID number.  Every sum is in the range from $9$ to $9 + 8 \cdot 9 =
81$, and since results are obtained by doubling these sums, there are also
81 possible pigeonholes.  Since there are more pigeons than pigeonholes,
there must be two pigeons in the same pigeonhole; in other words, there
must be two students with the same result.}

\ppart In every set of 100 integers, there exist two whose difference
is a multiple of 37.

\solution{The pigeons are the 100 integers.  The pigeonholes are the
numbers 0 to 36.  Map integer $k$ to $k \rem 37$.  Since there are 100
pigeons and only 37 pigeonholes, two pigeons must go in the same
pigeonhole.  This means $k_1 \rem 37 = k_2 \rem 37$, which implies
that $k_1 - k_2$ is a multiple of 37.
}

\ppart For any five points inside a unit square, there are two points at
distance less than $\frac{1}{\sqrt{2}}$.

\solution{The pigeons are the points. The pigeonholes are the four
  subsquares of the unit square, each of side length $\frac{1}{2}$.  There
  are five pigeons and four pigeonholes, and a pigeon maps to the
  subsquare it is in (points on a boundary get assigned to the leftmost
  lowest possible subsquare) so more than one point must be in the same
  subsquare.  The points in the same subsquare are at distance less than
  $1/\sqrt{2}$, because the most distant points in the quadrant are at
  opposite corners at exactly this distance, but only one of these corners
  can be \emph{inside} the square (not on the boundary), so the
  distance between the points in the quadrant must actually be less than
  $1/\sqrt{2}$.}

\ppart For any five points inside an equilateral triangle of side length
2, there are two points at distance less than $1$.

\solution{The pigeons are the points.  The pigeonholes are the four
  sub-equilateral triangles of side length 1.  There are five pigeons
  and four pigeonholes, so more than one point must be in the same
  sub-equilateral triangle.  Points inside the same sub-equilateral
  triangle are at distance less than $1$.}


\ppart Prove that every finite undirected graph with two or more vertices
has two vertices of the same degree.

\solution{Suppose a graph has $n \geq 2$ vertices.  Hence, the vertex
degrees must be between 0 and $n-1$, inclusive.  However, both 0 and $n-1$
cannot both occur: if there is an isolated (degree 0) vertex, then the
remaining vertices can have degree at most $n-2$.  So in no graph are
there ever more than $n-1$ possible degree values.  Since there are $n$
vertices, and at most $n-1$ degrees, the Pigeonhole Principle implies
there must be two vertices with the same degree.}

\eparts
\end{problem}


%Division Rule

\begin{problem}

Your 6.001 tutorial has 12 students, who are supposed to break up into 4
groups of 3 students each.  Your TA has observed that the students waste
too much time trying to form balanced groups, so he decided to pre-assign
students to groups and email the group assignments to his students.

\bparts

\ppart Your TA has a list of the 12 students in front of him, so he
divides the list into consecutive groups of 3.  For example, if the list
is ABCDEFGHIJKL, the TA would define a sequence of four groups to be
$(\set{A,B,C}, \set{D,E,F}, \set{G,H,I}, \set{J,K,L})$.  This way of
forming groups defines a mapping from a list of twelve students to a
sequence of four groups.  This is a $k$-to-1 mapping for what $k$?

\solution{
Two lists map to the same sequence of groups iff the first 3 students are
the same on both lists, and likewise for the second, third, and fourth
consecutive sublists of 3 students.  So for a given sequence of 4 groups,
the number of lists which map to it is
\[
(3!)^4
\]
because there are $3!$ ways to order the students in each of the
4 consecutive sublists.
}

\ppart A group assignment specifies which students are in the same group,
but not any order in which the groups should be listed.  If we map a
sequence of 4 groups,
\[
(\set{A,B,C}, \set{D,E,F}, \set{G,H,I},\set{J,K,L}),
\]
into a group assignment
\[
\set{\set{A,B,C}, \set{D,E,F}, \set{G,H,I}, \set{J,K,L}},
\]
this mapping is $j$-to-1 for what $j$?

\solution{$4!$.}

\ppart How many group assignments are possible?

\solution{
\[
\frac{12!}{4!\cdot(3!)^4}=15400
\]
different assignments.

There are $12!$ possible lists of students, and we can map each list to an
assignment by first mapping the list to a sequence of four groups, and
then mapping the sequence to the assignment.  Since the first map is 
$(3!)^4$-to-1 and and the second is $4!$-to-1, the composite map is
$(3!)^4\cdot 4!$-to-1.  So by the Division Rule, $12! = \paren{(3!)^4\cdot 4!}A$
where $A$ is the number of assignments.
}

\ppart In how many ways can $3n$ students be broken up into $n$ groups of
3?  
\solution{
\[
\frac{(3n)!}{(3!)^n n!}.
\]
This follows simply but replacing ``12'' by ``3n'' in the solution to the
previous problem parts.
}

\eparts

\end{problem}


%Generalized Product

\begin{problem} Answer the following quesions using the Generalized
Product Rule.

\bparts

\ppart{Next week, I'm going to get really fit!  On day 1, I'll
exercise for 5 minutes.  On each subsequent day, I'll exercise 0, 1,
2, or 3 minutes more than the previous day.  For example, the number
of minutes that I exercise on the seven days of next week might be 5,
6, 9, 9, 9, 11, 12.  How many such sequences are possible?}

\solution{The number of minutes on the first day can be selected in 1 way.
The number of minutes on each subsequent day can be selected in 4 ways.
Therefore, the number of exercise sequences is $1 \cdot 4^6$ by the
extended product rule.}

\ppart An \term{$r$-permutation} of a set is a sequence of $r$
distinct elements of that set.  For example, here are all the
2-permutations of $\set{a, b, c, d}$:
%
\[
\begin{array}{ccc}
(a, b) & (a, c) & (a, d) \\
(b, a) & (b, c) & (b, d) \\
(c, a) & (c, b) & (c, d) \\
(d, a) & (d, b) & (d, c)
\end{array}
\]
%
How many $r$-permutations of an $n$-element set are there?  Express
your answer using factorial notation.

\solution{There are $n$ ways to choose the first element, $n - 1$ ways to
choose the second, $n - 2$ ways to choose the third, \dots, and
$n - r + 1$ ways to choose the $r$-th element.  Thus, there are:
\[
n \cdot (n-1) \cdot (n-2) \cdots (n - r + 1)  =  \frac{n!}{(n - r)!}
\]
$r$-permutations of an $n$-element set.
}

\ppart How many $n \times n$ matrices are there with \textit{distinct}
entries drawn from $\set{1, \ldots, p}$, where $p \geq n^2$?

\solution{There are $p$ ways to choose the first entry,
$p - 1$ ways to choose the second for each way of choosing the first,
$p - 2$ ways of choosing the third, and so forth.  In all there are
%
\[
p (p - 1) (p - 2) \cdots (p - n^2 + 1) = \frac{p!}{(p - n^2)!}
\]
%
such matrices.  Alternatively, this is the number of
$n^2$-permutations of a $p$ element set, which is $p! / (p - n^2)!$.}


\eparts

\end{problem}


%Inclusion-exclusion

\begin{problem}
A certain company wants to have security for their computer systems.  So
they have given everyone a name and password.  A length 10 word containing
each of the characters:
\begin{quote}
a, d, e, f, i, l, o, p, r, s,
\end{quote}
is called a \emph{cword}.  A password will be a cword which does not
contain any of the subwords "fails", "failed", or "drop".

For example, the following two words are passwords:
\begin{quote}
adefiloprs, srpolifeda,
\end{quote}
but the following three cwords are not:
\begin{quote}
a\textbf{drop}eflrs, \textbf{failedrop}s, \textbf{drop}e\textbf{fails}.
\end{quote}
\bparts

\ppart How many cwords contain the subword ``drop''?

\solution{Such cwords are obtainable by taking the word ``drop'' and the
remaining 6 letters in any order.  There are $7!$ permutations of these 7
items.}

\ppart How many cwords contain both ``drop'' and ``fails''?

\solution{
Take the words ``drop'' and ``fails'' and the remaining letter ``e'' in
any order.  So there are $3!$ such cwords.
}

\ppart Use the Inclusion-exclusion Principle to find a simple formula for
the number of passwords.

\solution{
There are $7!$ cwords that contain ``drop'', $6!$ that contain ``fails'',
and $5!$ that contain ``failed''.  There are $3!$ cwords containing both
``drop'' and ``fails''.  No cword can contain both ``fails'' and
``failed''.  The cwords containing both ``drop'' and ``failed'' come from
taking the subword ``failedrop'' and the remaining letter ``s'' in any
order, so there are $2!$ of them.  So by Inclusion-exclusion, we have the
number of cwords containing at least one of the three forbidden subwords is
\[
(7! + 6! + 5!) - (3! + 0 + 2!) + 0 = 5!(48) - 8.
\]
Among the  $10!$ cwords, the remaining ones are passwords, so the number
of passwords is
\[
10! - 5!(48) + 8 = 3,623,048.
\]
}

\eparts
\end{problem}


\instatements{
\newpage

\section*{Counting Principles}

\begin{mathrule*}[Pigeonhole Principle]
If $\card{A} > \card{B}$, then for every function $f : A \to B$ there
exist two different elements of $A$ that are mapped to the same
element of $B$.
\end{mathrule*}

\begin{quotation}
\noindent ``If more than $n$ pigeons are assigned to $n$ holes, then
there must exist two pigeons assigned to the same hole.''
\end{quotation}

A \term{$k$-to-1 function} maps exactly $k$ elements of the domain to
every element of the range.  For example, the function mapping ears of
6.042 students to their owners is 2-to-1.

\begin{mathrule*}[Division Rule]
If $f : A \to B$ is $k$-to-1, then $\card{A} = k \cdot \card{B}$.
\end{mathrule*}


\begin{mathrule*}[Generalized Product Rule]
Let $S$ be a set of length-$k$ sequences.  If there are:
%
\begin{itemize}
\item $n_1$ possible first entries,
\item $n_2$ possible second entries for each first entry,
\item $n_3$ possible third entries for each combination of first and
second entries,\\
\vdots
\end{itemize}
then:
\[
\card{S} = n_1 \cdot n_2 \cdot n_3 \cdots n_k
\]
\end{mathrule*}

\begin{mathrule*}[Inclusion-Exclusion for Three Sets]
\begin{align*}
\card{S_1 \cup S_2 \cup S_3} & = \card{S_1} + \card{S_2} + \card{S_3} \\
  & \quad - \card{S_1 \cap S_2} - \card{S_1 \cap S_3} - \card{S_2 \cap S_3} \\
  & \quad + \card{S_1 \cap S_2 \cap S_3}
\end{align*}
\end{mathrule*}
}

\end{document}
