\documentclass[11pt, twoside]{article}
\usepackage{epsf}

\input{macros-course}

\newcommand{\nand}{|}
\renewcommand{\implies}{\longrightarrow}
\newcommand{\mathify}[1]{\ifmmode{#1}\else\mbox{$#1$}\fi}
\newcommand{\mquote}[1]{\mathify{\textrm{``$#1$''}}}
\newcommand{\mdash}{\mathify{\textrm{-}}}

\askaboutsolutions

\begin{document}
\ifshowsolutions
\psol{8.5}{Problem Set 8.5}{November 10, 2000}
\else
\handout{ps85}{Problem Set 8.5}{November 7, 2000}
\fi

\textbf{You do not have to turn in the solutions to this Problem Set.
It is designed to help you study for the second quiz.}

-----------------------------------------------------------------------------\\

\textbf{Reading:} Lecture notes 17-18.

\textbf{Quiz 2:} Wednesday, November 15 7-9pm. %% room number here
Covers lectures 11-18.

\medskip
\begin{problems}

\problem
% new
% combinatorics, stars and bars, symmetry

\textbf{Vote today } $6N$ voters show up to vote for one of three 
candidates: Bush, Gore and Nader.

\ppart Assuming that voters are indistinguishable, what is the number of
possible vote counts?

\solution{\textbf{Solution: }
We can model this problem using $6N$ stars, each representing a vote,
and two bars, to separate Gore's, Bush's and Nader's votes.  Each
election result corresponds to a unique placement of the stars and
bars.  Therefore, the number of possible election results is 
$\binom{6N + 2}{2}$.}

\ppart What is the number of possible vote counts in which Nader wins 
the popular vote?

\solution{\textbf{Solution: }
Let $T$ be the number of vote counts for which the election is
a tied race.  By symmetry, Nader can win the election in 
$\frac{1}{3} (\binom{6N + 2}{2} - T)$ ways.

To compute $T$, we use a similar trick.  A tie happens either if two
candidates tie for first place or all three candidates tie for first
place.  By symmetry, we only need to consider the case when Bush and
Gore tie for first (but Nader doesn't).  For this to happen, Bush and
Gore must each get at least $2N + 1$ votes, but no more than $3N$
votes.  This is a total of $N$ possible outcomes.  It follows that 
$T = 3N + 1$, as there is one way in which all candidates tie for first.

It follows that Nader can win the election in 
$\frac{1}{3} (\binom{6N + 2}{2} - 3N - 1) = 2N(3N + 1)$ ways.
}


\problem
% spring96 ps7
% combinatorics, balls and bins, stars and bars

How many ways are there to distribute eight balls into six distinct
boxes with the first two boxes having collectively at most four balls
if

\ppart the balls are identical?

\solution{\textbf{Solution: }
Let us consider placing $n$ balls into $k$ boxes so that exactly $r$
balls are placed in the first two boxes. This can be done in
\[
{r+2-1 \choose 2-1}{(n-r)+(k-2)-1 \choose (k-2)-1}
\]
ways, since there are ${\rm BP}(r,2) = {r+2-1 \choose 2-1}$ ways to
place $r$ balls into first two boxes and ${\rm BP}(n-r,k-2) =
{(n-r)+(k-2)-1 \choose (k-2)-1}$ ways to place the remaining $n-r$
balls into the other $k-2$ boxes. We can place the balls into boxes,
so that {\em at most} $r$ balls go into the first two boxes, in
\[
\sum_{i=0}^r{{i+2-1 \choose 2-1}{(n-i)+(k-2)-1 \choose (k-2)-1}}
\]
ways. In particular for $n=8$, $k=6$ and $r=4$ we get
\[
\sum_{i=0}^4{{i+2-1 \choose 2-1}{(8-i)+(6-2)-1 \choose (6-2)-1}} = 1056{.}
\]
}

\ppart the balls are distinct?

\solution{\textbf{Solution: }
As in the part (a), we compute the number of ways $n$ balls can be
placed into $k$ boxes so that exactly $r$ of them are placed in the
first two boxes. Since the balls are distinct, we have ${n \choose r}$
ways to choose which balls to place in the first two boxes, and then
we have $2^r$ ways to place the balls into first two boxes, and
$(k-2)^{n-r}$ ways to place the rest of the balls into the remaining
$k-2$ boxes. Thus the total number of posibilities is
\[
{n \choose r}2^r(k-2)^{n-r}{.}
\]
If we require that {\em at most} $r$ balls go into the first two boxes
we compute that the number of posibilities is
\[
\sum_{i=0}^r{{n \choose i}2^i(k-2)^{n-i}}{.}
\]
For $n=8$, $k=6$ and $r=4$ we get
\[
\sum_{i=0}^4{{8 \choose i}2^i(6-2)^{8-i}} = 1531904{.}
\]
}


\problem
% spring95, ps7
% basic combinatorics

% \ppart How many ways can $2n$ objects be divided into $n$ pairs?
%
%\solution{\textbf{Solution: }
%Consider all the ways of ordering the $2n$ objects in a line. There are
%$(2n)!$ ways of doing this. Now group them into pairs based on the
%linear order, i.e. group the first and second object, group the third
%and fourth object,..., group the $(2n-1)$th and $2n$th object. Thus
%each linear order gives us a unique grouping into pairs. But observe
%that two different linear orders could give rise to the same grouping
%into pairs. So let us now count the number of linear orders that give
%rise to the same grouping into pairs. Given a grouping into pairs, to
%generate a linear order we need to order each pair (there are $2^n$
%ways to do this) and then order the $n$ pairs (there are $n!$ ways to
%do this). Hence $n! 2^n$ linear orders give the same grouping into
%pairs. Thus the total number of ways $2n$ objects can be divided into
%$n$ pairs is $\frac{(2n)!}{n! 2^n}$.
%}

%\ppart 
How many ways can you choose $n$ out of $2n$ objects, given that
$n$ of the $2n $ objects are identical?

\solution{\textbf{Solution: }
The answer is $2^n$, since you can pick any subset from the $n$
nonidentical objects, and make up the rest with the identical ones. And the
number of subsets of $n$ different objects is $2^n$. 
}


\problem 
% spring98 ps8
% combinatorics, some stars and bars

How many different ways are there to list the numbers $1,
2, \ldots, 2n$ such that the even numbers appear in increasing order
and the odd numbers appear in decreasing order?

\solution{\textbf{Solution: }
There are $(2n)!$ ways to list the numbers $1, 2, \ldots,
n$.  We can define a $n!$-to-1 mapping that takes an arbitrary listing
to a listing in which the even numbers are sorted in increasing order
and the odd numbers remain as before.  Thus, by the quotient rule
there are $(2n)!/n!$ listings in which the even numbers appear in
increasing order.  Similarly, we can define an $n!$-to-1 mapping that
takes a listing in which the even numbers appear in increasing order
and the odd numbers are in an arbitrary order to a listing in which
the even numbers appear in increasing order (as before) and the odd
numbers appear in decreasing order.  Therefore, there are
\begin{eqnarray*}
\frac{(2n)!}{n! \ n!} & = & \binom{2n}{n}
\end{eqnarray*}

listings in which the even numbers are increasing and the odd numbers
are decreasing.
}


\problem
% fall94 ps7
% combinatorics, binomial theorem

We wish to prove the identity
\[\sum_{r=0}^n{n\choose r}^2 = {2n\choose n}\ ,\]
for $n\in\naturals$.

\ppart Use the binomial theorem and the fact that
\[(1+x)^n(1+x)^n = (1+x)^{2n}\] to prove the identity.

\solution{\textbf{Solution: }
\begin{eqnarray*}
(1+x)^n (1+x)^n &=& (1+x)^{2n} \\
\sum_{i=0}^n {n\choose i}x^i \sum_{j=0}^n {n\choose j}x^j &=&
	\sum_{i=0}^{2n} {2n\choose i}x^i
\end{eqnarray*}

Equating the coefficients of $x^n$ on both sides yields
\begin{eqnarray*}
\sum_{i+j=n} {n\choose i}{n\choose j} &=& {2n\choose n} \\
\sum_{i=0}^n {n\choose i}{n\choose n-i} &=& {2n\choose n}
\end{eqnarray*}
From where we obtain the identity using the substitution 
${n\choose n-i} = {n\choose i}$.
}

\ppart Consider a set of $2n$ objects, of which $n$ are red and
$n$ are blue.  Give a combinatorial proof of the identity.

\solution{\textbf{Solution: }
Suppose we have $2n$ objects, $n$ of which are red, and $n$ of which are blue.
How many ways can we pick $r$ red ones and $n-r$ blue ones?  Clearly this is
$${n \choose r} {n \choose n-r} = {n \choose r}^2.$$  
How many ways can we choose $n$ objects total, regardless of how many
are of each color?  This is just 
$$ \sum_{r=0}^n {n \choose r}^2.$$  
But there are  ${2n \choose n}$ ways to
choose $n$ objects, so these must be the same number.
}


\problem 
% fall98 ps7, edited
% infinity, sets

Prove or disprove the following statements about sets.

\ppart The product of a finite number of countable sets is countable.

\solution{\textbf{Solution: }
The statement is true.  The proof is by induction.  Let $P(n)$ be the 
proposition that the product of $n$ countable sets is countable.  In 
the base case, $P(1)$ is true because the product of a single countable 
set is itself.  In the inductive step, for $n \geq 1$ assume $P(n)$ to 
prove $P(n+1)$. The product of $n+1$ countable sets 
$S_1, S_2, \ldots, S_{n+1}$ can be written as shown below.
\[
(S_1 \times S_2 \times \ldots \times S_{n}) \quad \times \quad S_{n+1}
\]
The first term is a countable set by induction, and the second term is
a countable set by definition.  The product of two countable sets is
countable, as shown in lecture.  Therefore, the product of $n+1$
countable sets is countable.  This shows that $P(n)$ implies $P(n+1)$,
and the claim is proved by induction.
}

\ppart A countable union of countable sets is countable.

\solution{\textbf{Solution: }
This statement is true.  Let $\{ S_i, i \in \mathbb{N} \}$ 
be a collection of countable sets.  Write 
$S = \bigcup _{i \in \mathbb{N}} S_i$.  Since each $S_i$ is countable, 
there are bijections $f_i: \mathbb{N} \to S_i$ for all 
$i \in \mathbb{N}$.  The map $f:\mathbb{N} \times \mathbb{N} \to S$ 
given by $f(i, j) = f_i(j)$ is surjective.  Since 
$\mathbb{N} \times \mathbb{N}$ is a product of two countable sets, it is 
countable.  It follows that $S$ must be countable.
}


\problem
% fall97 ps7, Rosen 1.8 / 30
% infinity

Use a diagonalization argument to show that the set of functions from
the positive integers to the set $\{0, 1, 2, 3, 4, 5, 6, 7, 8, 9\}$ is
uncountable.

\solution{\textbf{Solution: }
Assume, for the purposes of contradiction, that this set is countable.
Then there is a listing of the function in the set,
 $f_1, f_2,\ldots$.  Now define $f$ such that $f(i) = (f_i(i)+5) \mod 10$.
Then $f$ is not in the list, because $f$ differs from each $f_i$
in the $i$th value.  We have established a contradiction.  We conclude that
the set is uncountable.
}

\end{problems}

\end{document}












