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

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

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

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

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

\begin{itemize}

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

\item 5 letters (vanity plate)

\item 2 characters -- letters or numbers (big shot 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{
\[
L = (A^3 \times D^3) \union A^5 \union (A\union D)^2
\]
}

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

\solution{
\begin{align*}
\card{L}
  & = \card{(A^3 \times D^3) \union A^5 \union (A\union D)^2} \\
  & = \card{(A^3 \times D^3)} + \card{A^5} + \card{(A\union D)^2}  &  \text{Sum Rule} \\
    & = \card{A}^3 \cdot \card{D}^3 + \card{A}^5 + \card{A\union D}^2 & \text{Product Rule} \\ 
    & = \card{A}^3 \cdot \card{D}^3 + \card{A}^5 + (\card{A}+\card{D})^2 & \text{Sum Rule} \\ 
    & = 26^3 \cdot 10^3 + 26^5 + 36^2 = 29458672
\end{align*}
}

\eparts

\end{problem}

\begin{problem}
Let $p$ be a prime and $k$ a positive integer.
\bparts

\ppart\label{pk} How many positive integers less than $p^k$ are divisible by $p$?

\solution{
Every $p$th integer is divisible by $p$, namely $p,2p,3p,\dots (p^{k-1} -1)p$, so the answer is $p^{k-1}-1$.
}

\ppart What is the value, $\phi(p^k)$, of the Euler function at $p^k$?

\solution{
There are $p^k-1$ positive integers less than $p^k$, of which $p^{k-1}-1$
are divisible by $p$ by part~\eqref{pk}, and $\phi(p^k)$ are relatively
prime to $p^k$ by definition of Euler's function.  But a number is
relatively prime to $p^k$ iff it is not divisible by $p$, so
\[
(p^{k-1}-1) + \phi(p^k) = p^k-1
\]
by the Sum Rule.  Therefore,
\[
\phi(p^k) = p^k-p^{k-1}.
\]
}

\eparts
\end{problem}


\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[\vspace{2in}]{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$.}

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


\begin{problem}
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}
If $n=2$, stop---the code is the empty sequence.  Otherwise, write down
the \emph{father} of the largest leaf\footnote{The necessarily unique node
adjacent to a leaf is called its \emph{father}}, 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 
the Figure~\ref{codetrees}.

\begin{figure}[htb]
\begin{center}
\includegraphics[width=4in]{figures/n-2}
\end{center}
\caption{}
\label{codetrees}
\end{figure}

\bparts

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

%This paragraph is correct, but would benefit from a rewrite:

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?  Justify
your answer assuming the result of the previous problem part.

\solution{There are exactly as many $n$-vertex numbered trees as the
number of possible code words, that is, the number of length $n-2$
sequences integers between 1 and $n$.  So there are $n^{n-2}$ numbered
trees.
  
The reason is that the map from trees to codes is a bijection.  To see
this, note that the tree reconstruction procedure finds \emph{the only
possible tree} with that code.  So there can't be two trees with the same
code, i.e., the map from a tree to its code is an injection.  But since
the reconstruction procedure finds a tree for every possible codeword, the
map from trees to codes is also a surjection.}

\eparts
\end{problem} 

\end{document}
