\documentclass[12pt]{article}
\usepackage{light}

%\hidesolutions
\showsolutions

\begin{document}

\recitation{13}{March 30, 2005}

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

\section*{Basic Counting Notions}

A \term{bijection} or \term{bijective function} is a function $f : X
\to Y$ such that every element of the codomain is related to exactly
one element of the domain.  Here is an example of a bijection:

\begin{center}
\unitlength = 2pt
\begin{picture}(50,60)(-10,-5)
\thinlines
\put(-30,30){\makebox(0,0){domain}}
\put(60,30){\makebox(0,0){codomain}}
\put(-5,50){\makebox(0,0){$X$}}
  \put(15,50){\makebox(0,0){$f$}}
  \put(35,50){\makebox(0,0){$Y$}}
\put(-5,40){\makebox(0,0){a}}
  \put(0,40){\vector(3,-1){28}}
  \put(35,40){\makebox(0,0){1}}
\put(-5,30){\makebox(0,0){b}}
  \put(0,30){\vector(3,-1){28}}
  \put(35,30){\makebox(0,0){2}}
\put(-5,20){\makebox(0,0){c}}
  \put(0,20){\vector(3,-1){28}}
  \put(35,20){\makebox(0,0){3}}
\put(-5,10){\makebox(0,0){d}}
  \put(0,10){\vector(1,1){28}}
  \put(35,10){\makebox(0,0){4}}
\put(-5,0){\makebox(0,0){e}}
  \put(0,0){\vector(1,0){28}}
  \put(35,0){\makebox(0,0){5}}
\end{picture}
\end{center}

\begin{mathrule}[Bijection Rule]
If there exists a bijection $f : A \to B$, then $\size{A} = \size{B}$.
\end{mathrule}

\begin{mathrule}[Sum Rule]
If $A_1, \dots, A_n$ are disjoint sets, then:
%
\[
\size{A_1 \cup \cdots \cup A_n} = \sum_{k=1}^n \size{A_k}
\]
\end{mathrule}

\begin{mathrule}[Product Rule]
If $P_1, P_2, \dots P_n$ are sets, then:
%
\begin{align*}
\size{P_1 \times P_2 \times \cdots \times P_n}
    & = \size{P_1} \cdot \size{P_2} \cdots \size{P_n}
\end{align*}
\end{mathrule}

\begin{mathrule}[Pigeonhole Principle]
If $\size{X} > \size{Y}$, then for every function $f : X \to Y$ there
exist two different elements of $X$ that are mapped to the same
element of $Y$.
\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}

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

\newpage

\section*{Sum and Product Rules}

\begin{problem}
A license plate consists of either:

\begin{itemize}

\item 3 letters followed by 3 digits (standard plate)

\item 5 letters (vanity plate)

\end{itemize}

Let $L$ be the set of all possible license plates.

\bparts

\ppart Express $L$ in terms of
%
\begin{align*}
{\cal A} & = \set{ A, B, C, \dots, Z} \\
{\cal D} & = \set{ 0, 1, 2, \dots, 9} \\
\end{align*}
%
using unions ($\cup$) and set products ($\times$).

\solution[\vspace{2.5in}]{
\[
L = (A^3 \times D^3) \cup A^5
\]
}

\ppart Compute $\size{L}$, the number of different license plates,
using the sum and product rules.

\solution{
\begin{align*}
\size{L}
    & = \size{(A^3 \times D^3) \cup A^5} \\
    & = \size{(A^3 \times D^3)} + \size{A^5} & \text{Sum Rule} \\
    & = \size{A}^3 \cdot \size{D}^3 + \size{A}^5 & \text{Product Rule} \\
    & = 26^3 \cdot 10^3 + 26^5
\end{align*}
}

\eparts

\end{problem}

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

\instatements{\newpage}

\section*{Bijections}

\begin{problem}
For each part below, describe a bijection between the two sets
mentioned.  The existence of such a bijection proves that the two sets
are the same size.

A good approach is to describe an element of the first set using
variables and then describe the corresponding element of the second
set in terms of those variables.  For example, we might describe a
bijecton from ways of selecting a dozen doughnuts from five varieties
to a 16-bit string with four 1's as follows:

\begin{quotation}
\noindent Map a dozen doughnuts consisting of:
%
\[
\text{$c$ chocolate, $l$ lemon-filled, $s$ sugar, $g$ glazed, and $p$ plain}
\]
%
\noindent to the sequence:
%
\[
\underbrace{\ 0 \dots 0\ }_{\text{$c$}} \quad 1 \quad
\underbrace{\ 0 \dots 0\ }_{\text{$l$}} \quad 1 \quad
\underbrace{\ 0 \dots 0\ }_{\text{$s$}} \quad 1 \quad
\underbrace{\ 0 \dots 0\ }_{\text{$g$}} \quad 1 \quad
\underbrace{\ 0 \dots 0\ }_{\text{$p$}}
\]
\end{quotation}

\noindent \textit{Everyone in your group should write out complete
answers--- you'll all benefit from the practice!}

\bparts

\ppart Describe a bijection between the set of $30$-bit sequences with
10 zeros and 20 ones and paths from $(0, 0)$ to $(10, 20)$ consisting
of right-steps (which increment the first coordinate) and up-steps
(which increment the second coordinate).

\solution[\vspace{2in}]{Map the 30-bit sequence $b_1 b_2 \dots
b_{30}$ to a path where the $i$-th step is right if $b_i = 0$ and up
if $b_i = 1$.}

\ppart Find a bijection between the set of $n$-bit sequences and the
set of all subsets of $\set{x_1, x_2, \dots, x_n}$.

\solution{Map the $n$-bit sequence $b_1 b_2 \dots b_n$ to a subset
that contains $x_i$ if and only if $b_i = 1$.}

\instatements{\newpage}

\ppart Mr. and Mrs. Grumperson have collected 13 identical pieces of
coal as Christmas presents for their beloved children, Lucy and Spud.
Describe a bijection between the set of all ways of distributing the
13 coal pieces to the two children and the set of 14-bit sequences
with exactly 1 one.

\solution[\vspace{2in}]{Map a distribution in which Lucy get $l$
pieces and Spud gets $s$ pieces to a 14-bit sequence with $l$ zeros, a
one, and then $s$ zeros.}

\ppart On Christmas Eve, Mr. and Mrs. Grumperson remember that they
have a third child, little Bottlecap, locked in the attic.  Describe a
bijection between the set of all ways of distributing the 13 coal
pieces to the three children and the set of 15-bit sequences with
exactly 2 ones.

\solution[\vspace{2in}]{Map a distribution in which Lucy gets $l$
pieces, Spud gets $s$ pieces, and Bottlecap gets $b$ pieces to a
15-bit sequence with $l$ zeros, a one, $s$ zeros, a one, and $b$
zeros.}

\ppart On reflection, Mr. and Mrs. Grumperson decide that each of
their three children should receive {\em at least two} pieces of coal
for Christmas.  Describe a bijection between the set of all ways of
distributing the 13 coal pieces to the three Grumperson children given
this constraint and the set of 9-bit sequences with exactly 2 ones.

\solution[\vspace{2in}]{Map a distribution in which Lucy gets $l \geq 2$
pieces, Spud gets $s \geq 2$ pieces, and Bottlecap gets $b \geq 2$ pieces
to a 9-bit sequence with exactly $l - 2$ zeros, a one, $s - 2$ zeros, a
one, and $b - 2$ zeros.}

\ppart Describe a bijection between the set of 110-bit sequences with
exactly 10 ones and solutions over the natural numbers to the
equation:

\begin{eqnarray*}
x_1 + x_2 + \cdots + x_{10} & \leq & 100
\end{eqnarray*}

\solution[\vspace{2in}]{Let $x_1$ be the number of zeros before the
first 1, $x_2$, be the number of zeros between the first and second 1,
etc.  Note that zeros after the tenth 1 do not contribute to the value
of any of the variables $x_1, \dots, x_{10}$; this allows us to count
solutions to the inequality ($\leq 100$) rather than the equality ($=
100$).}

\ppart Describe a bijection between solutions to the inequality in the
preceding problem part and sequences $(y_1, y_2, \dots, y_{10})$ such
that:
%
\[
0 \leq y_1 \leq y_2 \leq \dots \leq y_{10} \leq 100
\]

\solution{Let $y_i = x_1 + \cdots + x_i$ for each $i$ from 1 to 10.}

\eparts
\end{problem}

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

\instatements{\newpage}

\section*{Pigeonhole Principle}

\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[\vspace{2.5in}]{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 75 students in 6.042 sums the nine digits of his or her ID
number.  Must two people arrive at the same sum?

\solution[\vspace{2.5in}]{Yes.  The students are the pigeons, the
possible sums are the pigeonholes, and we map each student to the sum
of the digits in his or her MIT ID number.  Every sum is in the range
from $9 + 8 \cdot 0 = 9$ to $9 + 8 \cdot 9 = 81$, which means that
there are 73 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 sum.}

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

\solution[\vspace{2.5in}]{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 in a unit square, there are two points at
distance less than $\frac{1}{\sqrt{2}}$.

\solution[\vspace{2.5in}]{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, so more than one point
  must be in the same subsquare.  Points in the same subsquare are at
  distance at most $\frac{1}{\sqrt{2}}$.}

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

\solution[\vspace{2.5in}]{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 in the same sub-equilateral
  triangle are at distance at most $1$.}

\ppart Let $\{a_1, \ldots, a_{201}\}$ be a set of natural numbers less
than 300.  Then there are $i,j$ such that $\frac{a_i}{a_j} = 3^k$ for
some $k > 0$.

\solution[\vspace{2.5in}]{The pigeons are the numbers.  The pigeonholes are the 200
  numbers less than 300 that are not divisible by 3.  Write each
  number $a_i = 3^{c_i} \cdot b_i$, where $b_i$ is not divisible by 3.
  Place $a_i$ in the pigeonhole $b_i$.  Then there are two numbers
  $a_i, a_j$ placed in the same pigeonhole, i.e. $b_i = b_j$, so
  $\frac{a_i}{a_j} = 3^{c_i-c_j}$. (Assume $c_i > c_j$ without loss of
  generality)}

\eparts

\end{problem}

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

\end{document}
