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

\hidesolutions
%\showsolutions

\begin{document}

\problemset{8}{October 26, 2004}{\textit{Monday November 1 at 9 PM}}

\insolutions{}

\begin{problem}[15 points]

\bparts

\ppart Describe a bijection between the sequences $x_1,x_2, \dots, x_k$ of
positive integers such that
\begin{equation}\label{x1}
x_1 < x_2 < \cdots < x_k \leq n
\end{equation}
and the length $n$ bit-strings (i.e., strings of $\mathtt{0}$'s and
$\mathtt{1}$'s) containing exactly $k$ $\mathtt{1}$'s.

\solution{Map $(x_1,x_2, \dots, x_k)$ to
\[
\mathtt{0}^{x_1 - 1}\mathtt{1}
\mathtt{0}^{x_2 - x_1 - 1}\mathtt{1}
\mathtt{0}^{x_3 - x_2 - 1}\mathtt{1}\mathtt{0} \dots \mathtt{1}
\mathtt{0}^{x_k - x_{k - 1} - 1}\mathtt{1}
\mathtt{0}^{n-x_k}.
\]

Notice that there are exactly $k$ $\mathtt{1}$'s in the final string.
Also, the prefix of the string ending with $i$th $\mathtt{1}$ is exactly
$x_i$ letters long.  So the length of the prefix ending with the last
$\mathtt{1}$ is $x_k$, and the final string of $\mathtt{0}$'s ensures the
length of the whole string is $n$.

It's not hard to see how to recover the sequence from the bit-string it maps
to.  Also, we can recover a sequence from \emph{any} length $n$ bit-string
with $k$ \texttt{1}'s.  This means that the mapping from sequences to
bit-strings has an inverse mapping bit-strings back to sequences, which
implies that the mapping is indeed a bijection.

\medskip
Another, indirect, way to obtain a bijection is to observe that there is
bijection between the sequences satisfying~\eqref{x1} and the $k$-element
subsets of $\set{1,\dots,n}$.  Namely, map the sequence $(x_1,x_2, \dots,
x_k)$ to $\set{x_1,x_2, \dots, x_k}$.  We know there is a bijection
between these $k$-element subsets and bit-strings of length $n$ with $k$
occurrences of \texttt{1}'s.  Composing these two bijections yields a
bijection from sequences to bit-strings.}

\ppart Use the bijection to write a closed form (which may involve
factorials) for the number of sequences satisfying~\eqref{x1}.

\solution{
\[
\frac{n!}{k!(n-k)!} = \binom{n}{k}.
\]
}

\eparts

\end{problem}

\iffalse

\begin{problem}[10 points]
Calculate the number of ways to place 10 balls in four boxes with between
one and four (inclusive) balls in each box.

\solution{First place one ball in each box.  Then we must distribute six
balls in four boxes in such a way that no more than three balls are in the
same box.  We use inclusion/exclusion.

Number of ways to place six balls in 4 boxes is 
\[
\binom{6+4-1}{6} = \binom{9}{6}.
\]

Number of ways to place six balls in 4 boxes such that there are four balls
in a box =  number of ways to choose box with three balls $\times$ number of ways
to place two balls in three boxes =
\[
4 \cdot \binom{4}{2}.
\]

Number of ways to place six balls in 4 boxes such that there are five balls
in a box =
\[
4 \cdot \binom{3}{1}.
\]

Number of ways to place six balls in 4 boxes such that there are six balls
in a box = $4$.

So the total number of ways is
\[
\binom{9}{6} - 4 \cdot \binom{4}{2} - 4 \cdot \binom{3}{1} - 4 = 44.
\]
}

\end{problem}

\fi


\begin{problem}[20 points]
We will place 4 balls in 3 urns.   How many final placements are there if:

\bparts

\ppart both the balls and the urns are distinguishable?

\textit{Note:} once the balls are in an urn,
there is no way to tell the order in which they were placed.

\solution{
The answer is $81$.  We have $3$ choices for the first ball, $3$ choices
for the second ball, etc.  The product rule shows that there are $3\cdot
3\cdot 3\cdot 3=81$ ways in total.
}

\ppart \label{2b} neither the balls nor the urns are distinguishable?

\solution{The answer is $4$.  there are four
possibilities for the number of balls in the urns: all 4 balls in one urn;
3 in one urn and 1 in another; 2 in one urn and 2 in another.  We do not
care which particular balls end up in which urn, so the number of ways is
just $4$.}

\ppart the balls are distinguishable but the urns are not?

\solution{The answer is $14$. As observed in part~(\ref{2b}), there are
four possibilities for the number of balls in the urns: all 4 balls in one
urn; 3 in one urn and 1 in another; 2 in one urn and 2 in another; or 2 in
one and 1 in each of the other two.  Since the urns are not
distinguishable, there is only one way to put all 4 balls into the same
urn.  Since the balls \emph{are} distinguishable, there are $\binom{4}{3}$
ways of putting 3 balls into one urn, and this determines which ball is by
itself in the other non-empty urn.  There are $\binom{4}{2}/2$ of putting
2 balls in one urn and 2 in another.  There are $\binom{4}{2}$ ways of
putting 2 in one and 1 in each of the other two.  So the total number of
ways is
\[
1 + \binom{4}{3} + \frac{1}{2}\binom{4}{2} + \binom{4}{2} = 14.
\]}

\ppart the urns are distinguishable but the balls are not?

\solution{The answer is $15$.  This is like the problem of choosing a
dozen donuts seen in lecture.  Here the urns are the ``types of donuts''
and the balls correspond to the donuts whose type we can choose.  (This
sort of problem is also known as a ``stars and bars'' problem: the donuts
are the stars, and the bars are the separators between the types of
donuts.)  The answer is
\[
\binom{4+3-1}{4} = \binom{6}{4} = 15.
\]}

\eparts

\end{problem}


\begin{problem}[15 points]
There are $9$ members of the Red Sox starting line-up for game three of
the World Series, including the heavy-hitters Manny Ramirez and David
Ortiz.  The manager is considering how to arrange the players for the
first $6$ positions of the batting order; he is unconcerned with the last
$3$ positions.  He is wondering which players to choose for the first $6$
positions and also how to order them.  How many ways can he arrange the
first $6$ players from the $9$ players in the starting line-up if:

\bparts

\ppart Ramirez must be among the six?

\solution{There are $6$ ways to choose Ramirez's position in the ordering,
and $8 \cdot 7 \cdot 6 \cdot 5 \cdot 4$ ways to choose and arrange the others.
So the total is:
\[
6 \cdot \frac{8!}{3!} = 40320.
\]
}

\ppart Ramirez and Ortiz must both be among the six?

\solution{There are $6$ ways to place Ramirez and $5$ ways to place Ortiz.
There are $7 \cdot 6 \cdot 5 \cdot 4$ ways to choose and arrange the others.
So the total is:
\[
6 \cdot 5 \cdot \frac{7!}{3!} = 25200.
\]}


\ppart exactly one of Ramirez and Ortiz must be among the six?

\solution{There are $2$ ways to choose between Ramirez or Ortiz, $6$ ways
to place whichever one is chosen, and $7 \cdot 6 \cdot 5 \cdot 4 \cdot 3$
to choose and arrange the remaining people.  Total:
$$2 \cdot 6 \cdot \frac{7!}{2!} = 6 \cdot 7! = 30240.$$}

\eparts

\end{problem}


\instatements{\newpage}

\begin{problem}[10 points]
(The two parts of this problem are independent.)

\bparts

\ppart Describe a bijection between the length $n$ bit-strings with an
even number of \texttt{1}'s and the length $n$ bit-strings with an odd
number of \texttt{1}'s.  Explain why any such bijection leads to a simple
formula for the number of even-size subsets of any set of size $n$.

\solution{
Map a string to the same string with the first bit complemented.  This map
is its own inverse, and hence is a bijection from length $n$ bit-strings to
length $n$ bit-strings.  Restricting it to the length $n$ bit-strings with
an even number of \texttt{1}'s yields a bijection between the length $n$
bit-strings with an even number of \texttt{1}'s and the length $n$
bit-strings with an odd number of \texttt{1}'s.  So there are the same
number of strings of each kind, and therefore exactly half of the length
$n$ bit-strings have an even number of \texttt{1}'s, namely, $2^n/2 =
2^{n-1}$ strings with an an even number of \texttt{1}'s.

But with the standard bijection between bit-strings of length $n$ and
subsets of a set of size $n$, the strings with an even number of
\texttt{1}'s correspond to even-size subsets.  So the number of even-size
subsets is also $2^{n-1}$.
}

\ppart A shelf holds 12 books in a row.  How many ways are there to choose
five books so that no two adjacent books are chosen?

\solution{There are 5 bars (chosen books), and therefore there are 6
places where the 7 stars (non-chosen books) can fit (before the first bar,
between the first and second bars,..., after the fifth bar).  Each of the
second through fifth of these slots must have at least one star in it, so
that adjacent books are not chosen. Once we have placed these 4 stars,
there are 3 stars left to be placed in 6 slots. The number of ways to do
this is therefore
\[
\binom{6+3-1}{3}=\binom{8}{3}=56.
\]}


\eparts

\end{problem}

%new for F04, variant of old Karger problem

\begin{problem}[10 points]
\bparts

\ppart Describe how to place $n^2$ points in an $n \times n$ square such
that the distance between every pair of distinct points is greater than 1.

\solution{Divide the square into $1 \times 1$ subsquares, and begin by
placing a point in the middle of each these $n^2$ subsquares.  These
points are all distance $\geq 1$ from each other.  Now slightly expand the
square so the expanded distances between all the points slightly exceeds
1.  If the expansion is small enough, all the expanded points will still
be within the original square.

Formally, place points at positions
$((1+\epsilon)(i-1/2),(1+\epsilon)(j-1/2))$ for $1 \leq i,j \leq n$, where $0
< \epsilon < (2n-2)/(2n-1)$.
}

\ppart Show that this is impossible if there are $2(n+1)^2$ points, that
is, there must be at least two points of distance $\leq 1$.
\textit{Hint:} The Pigeonhole Principle.

\solution{Notice that the distance between any two points in an $s \times
s$ square is $\leq 1$, where $s = \sqrt{2}/2$.  But an $n\times n$ square
can be covered by
\[
\ceil{\frac{n}{s}}^2 = \ceil{\sqrt{2}n}^2 < (\sqrt{2}(n+1))^2 = 2(n+1)^2.
\]
such $s \times s$ squares.  So by the Pigeonhole Principle, if there
$2(n+1)^2$ points, two points must be in the same $s \times s$ square, and
so the distance between them is not $> 1$.

(We don't know what number between $n^2 + 1$ and $2(n+1)^2$ is the
\emph{largest} number of points that can be placed more than unit distance
apart.)}

\eparts
\end{problem}


%minor variant of spring01 tut8 & tutorial 9, spring 00.
       % Uses division rule.

\begin{problem}[15 points]
We want to split the class into teams of three.  Suppose there are $3n$
students in the class, so there should be $n$ teams.  Write a simple
closed-form formula (which may involve factorials) for the number of ways
the class could be split.  Explain your answer.

\solution{
\begin{equation}\label{3nf}
\frac{(3n)!}{n! \cdot 6^n}
\end{equation}

There are $(3n)!$ sequences consisting of the distinct students.  From
such a sequence, we can split into teams by teaming up the first three
students, the next three students, \dots, the last three students.

Now we observe that for a given split, there are $n!$ sequences of
\emph{teams} that describe that split.  Each team can be ordered in $3!$
ways, so there are $(3!)^n$ ways to order every one of the teams.  That
is, each split arises from exactly $n! \cdot 6^n$ sequences.
So~\eqref{3nf} follows by the Division Rule.}
\end{problem}


%``square-free'' problem, problem 8 from pset 7 from spring 00

\begin{problem}[15 points]
A positive integer is called {\em square-free} if it is not divisible by
the square of any positive integer greater than 1.  For example $35 = 5
\cdot 7$ is square-free but $18 = 2 \cdot 3^2$ is not.  $1$ is
square-free.  Use inclusion-exclusion to find the number of square-free
positive integers strictly less than 151.
  
\solution{We use inclusion-exclusion as done in lecture for the case of
prime numbers. We first compute the number of positive integers less than
150 that are not square free.

Let $A_2$ (respectively, $A_3$, $A_5$, $A_7$, $A_{11}$) be the set of
multiples of $2^2$ (respectively, $3^2$, $5^2$, $7^2$, $11^2$) less than
150. The cardinality of the union of these sets is given by
\begin {eqnarray*}
|A_2 \cup A_3 \cup A_5 \cup A_7 | & = &
 |A_2| + |A_3| + |A_5| + |A_7| + |A_{11}|
     - |A_2 \cap A_3 | - |A_2 \cap A_5|\\
                      & = & \floor{150/2^2} + \floor{150/3^2}
                          + \floor{150/5^2} + \floor{150/7^2}
                          + \floor{150/11^2}\\
                      &   &  - \floor{150/(2^23^2)} - \floor{150/(2^25^2)}\\
                      & = & 37 + 16 + 6 + 3 + 1 -4-1\\
                      & = & 58.
\end {eqnarray*}
Therefore the number of square-free positive integers less than 150 is
\[
150 - 58 = 92.
\]
}
\end{problem}


\iffalse
%%REUSED FROM Fall02 cp8W

\begin{problem}[20 points]
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, 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 $\size{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 $\size{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} 
\fi


\end{document}
