\documentclass[11pt, twoside]{article}

\usepackage{multirow}

\usepackage{graphics}
\usepackage{psfig}

\input{macros-course}

%\newcommand{\nand}{|}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Printing the page layout parameters

\printlayout

\askaboutsolutions

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

\ifshowsolutions
  \newcommand{\reading}[1]{}
%
  \newcommand{\handoutlabel}{sol7-5}
  \newcommand{\handouttitle}{Problem Set 7.5 Solutions}
  \newcommand{\handoutdate}{April, 2000}
  \newcommand{\collaboration}{}
  \newcommand{\titlebar}{\handout{\handoutlabel}{\handouttitle}{\handoutdate}}
%
\else 

  \newcommand{\reading}[1]{%
%    \mbox{}\\ %
    \hrule\mbox{} \\ %\bigskip %
    #1%
%    \mbox{} \\ %\bigskip %
    \hrule %
    %\vfill\mbox{}\newpage%
    }
%
  \renewcommand{\reading}[1]{}
  \newcommand{\handoutlabel}{ps7-5}
  \newcommand{\handouttitle}{Problem Set 7.5}
  \newcommand{\handoutdate}{April 4, 2000}
  \newcommand{\duedate}{Never}
  \newcommand{\collaboration}{\collaborationnote}
  \newcommand{\titlebar}{%
    \handout{\handoutlabel}{\handouttitle}{\handoutdate}
    \centerline{{\bf Due  Date: \duedate.}}
    \vspace*{\baselineskip}}
%
\fi

\renewcommand{\solution}[1]{%
  \ifshowsolutions %
  \textbf{\newline Solution.} \par %
  #1
  \mbox{} \\
  \mbox{}\hrulefill\hspace*{1ex}\ignorespaces%
  \raisebox{-0.25\baselineskip}{$\square$}%
  \hspace*{1ex}\ignorespaces\hrulefill%
  \nopagebreak%
  \fi}


%\newcommand{\solutionname}{Solution}
%\renewenvironment{solution}[1][\solutionname]{%
%  \par
%  \normalfont
%  \topsep6\p@\@plus6\p@ \trivlist
%  \item[\hskip\labelsep\bfseries
%    #1\@addpunct{.}]~~\ignorespaces
%}{%
%\mbox{} \\
%\mbox{}\hrulefill\hspace*{1ex}\ignorespaces%
%\raisebox{-0.25\baselineskip}{$\square$}%
%\hspace*{1ex}\ignorespaces\hrulefill%
%\nopagebreak%
%}

%\renewcommand{\solution}[1]{%
%  %\begin{solution}
%    #1
%  %\end{solution}
%  }

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

\begin{document}

\titlebar

\reading{%
  \vspace{-2\baselineskip}
  \begin{description}\itemsep 0\baselineskip
  \item[Self-study:] \mbox{} \\
    Rosen, Section 1.7, starting at Cardinality (beginning p.76) \\
    Self-study problems: 31, 32, 33, 34, 35
  \item[Reading:] \mbox{} \\[-\baselineskip]
    \vspace*{-0.5\baselineskip}
    \begin{description}\itemsep 0\baselineskip
    \item[Rosen:] Section 4.6
    \end{description}
  \end{description}
  }

\section*{Problems:}

\begin{problems}

\emph{NOTE:} There is no need to simplify sums, binomial coefficients, and 
factorials in your answers.

% Problem 1

%%%%%%% Problem %%%%%%%%
% source: spring96 ps7
% topic: combinatorics, balls in boxes, stars and bars

\problem 

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

\bparts

% add a new simpler part without the restriction of ``with the first two 
% boxes having collectively at most four balls''?

\ppart the balls are identical?

\solution{
\noindent
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{
\noindent
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{.}
\]
}

\eparts

%%%%%%% Problem %%%%%%%%
% source: spring98 ps8
% topic: combinatorics, some stars and bars

\problem 
Solve the following counting problems.

\begin{problemparts}
\problempart Suppose that Math Moose starts at position $(0, 0)$.  At
any time, he can step north (incrementing the first coordinate) or
step east (incrementing the second coordinate).  In how many different
ways can he reach position $(n, n)$, where $n$ is a non-negative
integer?

\solution{Math Moose must take $2n$ steps in total.  Of these, he must
choose a subset of $N$ to be north steps.  This gives $\binom{2n}{n}$
different ways to reach $(n, n)$.}

\problempart 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{ 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.
}

\problempart Describe a bijection that maps each one of Math Moose's
paths to a listing of the numbers $1, 2, \ldots 2n$ with even numbers
increasing and odd numbers decreasing.

\solution{Each time Math Moose take a step north, write down an even
number, starting with 2 and working up.  Each time Math Moose takes a
step east, write an odd number, starting with $2n-1$ and working down.}

\end{problemparts}

%%%%%%% Problem %%%%%%%%
% source: spring95 ps7
% topic: basic combinatorics, stars and bars

\problem
A pizza house is having a promotional sale. Their commercial reads:\\
``\ldots buy $2$ large pizzas at regular price, get up to $11$ different 
toppings for 
each pizza absolutely free. That's $4,194,304$ different ways to design your
order! \ldots''
\newline
\emph{Note:} $\displaystyle \left( \sum_{k=0}^{11}{11 \choose k} \right)^2
= \displaystyle \left(2048 \right)^2 = 4,194,304$

\bparts %

\ppart Show that $4,194,304$ is actually wrong and give the right
answer for the number of ways that you can choose toppings for the two
pizzas.

\solution{
The number of ways to choose different toppings for one pizza is
clearly $A \equiv \displaystyle \sum_{k=0}^{11}{11 \choose k} = 2^{11}
= 2,048$.  However, when they say there are $A^2$ different ways to
choose toppings for two pizzas, they are making the mistake of
counting the combination ``one mushroom pizza, and one cheese pizza"
as different from the combination ``one cheese pizza, and one mushroom
pizza."

The right solution is $ \displaystyle A+{A \choose 2} = \frac{1}{2}
(A^2+A) = 2,098,176 $, where $A$ is the number of ways to choose $2$
pizzas with the same toppings, and ${A \choose 2} $ is the number of
ways to choose $2$ different pizzas.
}

%To clarify, a valid choice of 2 pizzas
%does not allow multiple copies of the same topping on the same pizza, and does
%not require that the two pizzas themselves be distinct.
%comment on the fact that ordering of the 2 pizzas obviously doesn't matter???
%\solution{
%The problem double counts some pairs of pizzas, as ordering does not matter.
%For instance, a ``pepperoni pizza and a mushroom pizza'' is counted 
%differently from a ``mushroom pizza and a pepperoni pizza.''
%\newline
%Once you have your total number of possible single pizza types, you must 
%choose any two of them, allowing repition.
%\newline
%The correct formula is $\displaystyle { {\left( \sum_{k=0}^{11}{11 \choose k} 
%\right) + 2 - 1} \choose 2}$, which gives \bf{NEED TO FILL IN} combinations.
%}

\ppart  Now assume that you can choose any number of the same 
topping as long as the total number of toppings is no more than $11$.
(That is, you can have $2$ meatball, $4$ ham and $5$ sausage toppings if 
you are truly a meat lover.) How many different ways can you now choose
toppings for your two pizzas?

\solution{
For a single pizza, this is the ``stars and bars'' problem in disguised
form.  If $k$ is the total number of toppings you want on a pizza then
the number of ways of throwing $k$ identical balls into $11$ bins is
identical to choosing a total of $k$ toppings out a total of $11$
different topping-possibilities.  

Hence the number of ways to order one pizza is $B \equiv \displaystyle
\sum_{k=0}^{11}{10+k \choose k} = {22 \choose 11} = 705,432$.  
Using the same argument as in part
(a), we see that the number of ways to order two pizzas is
$\displaystyle B+ {B \choose 2}=\frac{B^2+B}{2} = 248,817,506,028$.
}

\eparts

% Problem 4

%%%%%%% Problem %%%%%%%%
% source: fall94 ps7, adapted
% topic: combinatorics; easy confidence builder

%%              from M&R, # 4.3.21 and 4.3.22
\problem 
A computer operating system requires file names to be exactly four letters
long; uppercase and lowercase letters are distinct.
\begin{problemparts}
\problempart
How many possible file names are there?
\solution{
%\newline
$52^4 = 7311616$.
}
\problempart
The operating system is changed so that uppercase and lowercase are no
longer distinct.  Figure out the new number of file names in two ways:
applying the division rule to {\bf (a)} and directly.
\solution{
%\newline
$52^4 \div 2^4 = 456976 = 26^4$.
}
\problempart
The operating system is changed so that file names may be {\em at least} one 
letter and {\em up to\/}
four letters long.  Repeat {\bf (a)} and {\bf (b)}.  Can the division
rule still be used?
\solution{
%\newline
$\sum_{i=1}^4 52^i = (52^5-52)/(52-1) = 7454980$; $\sum_{i=1}^4
26^i = (26^5-26)/(26-1) = 475254$.  The division rule can be applied only to
the individual terms of the summation.
}
\end{problemparts}


% Problem 5

%%%%%%% Problem %%%%%%%%
% source: spring95, ps7
% topic: basic combinatorics

\problem 

\bparts
\ppart How many ways can $2n$ people be divided into $n$ pairs?

\solution{
$\displaystyle (2n)!/ n! 2^n$.

Consider all the ways of ordering the $2n$ people 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 persons, group the third
and fourth persons,..., group the $(2n-1)$th and $2n$th persons. 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$ people can be divided into
$n$ pairs is $ (2n)!/ n! 2^n$.

\iffalse
First we pick $n$ leaders from the $2n$ people. 
There are ${2n \choose n}$ ways to do this. 
Then we pair the remaining $n$ people with the $n$ leaders. That gives
us $n!$ different ways for each choice of leaders. However,
${2n \choose n}n!$ will be overcounting, since for any fixed pairing,
we count each pair twice depending on who is the leader.
 So for any valid pairing, we counted it $2^n$ times.
Therefore, the answer should be
 $\displaystyle {2n \choose n} n! /2^n$.

\fi
}

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

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

\eparts

% Problem 6

%%%%%%% Problem %%%%%%%%
% source: parts from fall95 ps7, parts from fall94 ps7
% topic: binomial coefficients in large polynomials

\problem
Find the coefficients of 
\begin{problemparts}
\problempart $x^5$ in $(1+x)^{11}$
\solution{
%\newline
${11\choose 5} = 462$
}
\problempart $a^2b^8$ in $(a+b)^{10}$
\solution{
%\newline
${10 \choose 2} = 45$
}
\problempart $a^6b^6$ in $(a^2+b^3)^5$
\solution{
%\newline
  $a^6b^6 = (a^2)^3 (b^3)^2$, so the coefficient is ${5 \choose 3} =
  10$
}
\problempart $x^3$ in $(3+4x)^6$
\solution{
%\newline
${6 \choose 3}3^3 4^3 = 34560$
}
\problempart $x^{10}$ in $(x+(1/x))^{100}$
\solution{
%\newline
${100 \choose 55}$
}
\problempart $x^8y^9$ in $(3x+2y)^{17}$
\solution{
%\newline
${17 \choose 8}3^82^9$
}
\problempart $x^k$ in $(x^2 - (1/x))^{100}$
\solution{
%\newline
$x^k$ has a nonzero coefficient iff $-100 \leq k \leq  200$ and $k = 2$ mod $3$. In such a case the coefficient is ${100\choose (100 + k)/3}(-1)^{(200 - k)/3}$.
}
\end{problemparts}

% Problem 7

%%%%%%% Problem %%%%%%%%
% source: fall94 ps7
% topic: combinatorics, binomial theorem

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

\begin{problemparts}
\problempart Use the binomial theorem and the fact that
\[(1+x)^n(1+x^{-1})^n = x^{-n}(1+x)^{2n}\] to prove the identity.
%\newline
\solution{
\begin{eqnarray*}
x^{-n}(1+x)^n x^n (1+x^{-1})^n &=& x^{-n}(1+x)^n (x+1)^n \\
(1+x)^n (1+x^{-1})^n &=& x^{-n}(1+x)^{2n}\\
\sum_{i=0}^n {n\choose i}x^i \sum_{j=0}^n {n\choose j}x^{-j} &=& x^{-n}\sum_{i=0}^{2n} {2n\choose i}x^i\\
\sum_{i=0}^n {n\choose i}^2 &=& {2n\choose n}
\end{eqnarray*}
by equating the coefficients of $x^0$.
}

\problempart Consider a set of $2n$ objects, of which $n$ are red and
$n$ are blue.  Use the fact that \[{n\choose r}^2 = {n\choose
r}{n\choose n-r}\] to give a combinatorial proof of the identity.
%\newline
\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.
}
\end{problemparts}

% Problem 8

%%%%%%% Problem %%%%%%%%
% source: spring98 ps7
% topic: binomial coefficients & product rule; difficult, but straightforward

\problem

Prove that

\[ \sum_{a=0}^n \sum_{b=0}^{n-a} \frac {n!}{a!b!(n-a-b)!} = 3^n \ . \]

\medskip

[Hint: find a formula for $(x+y+z)^n$ and then set $x=y=z=1$.]

\solution{
We can write $(x+y+z)^n$ as follows:

\begin {equation} 
 \label{eq1} \begin {array}{lcr}
 (x+y+z)^n & =& (x+y+z) (x+y+z) \cdots
(x+y+z)\\ &=& \displaystyle
\sum_{  \begin{array}{c} \scriptstyle a,b,c\\ 
\scriptstyle a\geq 0, b \geq 0, c\geq 0\\
\scriptstyle a + b+ c = n \end {array}} C_{a,b,c} x^a y^b z^c 
\end {array} \ . \end {equation}
where $C_{a,b,c}$ is the number of ways to partition a set
of $a+b+c$  elements into three 
subsets of size, respectively, $a$, $b$, and $c$. 

We compute $C_{a,b,c}$ using the product rule. A
partition can be obtained by first choosing $a$ elements
out of $a+b+c$ ones, and then choosing $b$ elements out of the remaining
$b+c$ ones. The number of ways to make such choices is

\begin {equation} \label{eq2}
 C_{a,b,c} = {a +b +c \choose a} \cdot {b+c \choose b} = 
\frac{ (a+b+c)!}{a!(b+c)!} \cdot \frac{(b+c)!}{b!c!} = \frac {(a+b+c)!}{a!
b!c!}\ .  \end {equation}
% We could have found the same expression using the division rule.
Substituting Equation~(\ref{eq2}) into Equation~(\ref{eq1}) we
have

\begin{eqnarray*} 
(x+y+z)^n & = &  \sum_{ \begin{array}{c} \scriptstyle a,b,c\\ 
\scriptstyle a\geq 0, 
b \geq 0, c\geq 0\\
\scriptstyle a + b+ c = n \end {array}} \frac {n!}{a!b!c!}
x^a y^b z^{c} \\
& = & \sum_{a=0}^n \sum_{b=0}^{n-a} \frac {n!}{a!b!(n-a-b)!}
x^a y^b z^{n-a-b} \ .
\end {eqnarray*}

If we set  $x=y=z=1$
we derive

\[ 3^n = (1+1+1)^n = \sum_{a=0}^n \sum_{b=0}^{n-a} \frac {n!}{a!b!(n-a-b)!}
1^a 1^b 1^{n-a-b}\ . \]
}

% Problem 9

%%%%%%% Problem %%%%%%%%
% source: fall98 ps7
% topic: infinity, sets

\problem 
 Prove or disprove the following statements
about sets.  (We use ``collection'' as a synonym for ``set'' to make
some of the statements easier to read.)

\begin{problemparts}

\problempart The product of a finite collection of countable sets is
countable.

\solution{
The statement is true.  

\begin{proof}
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.
\end{proof}
}

\problempart The product of a countable collection of finite sets is
countable.

\solution{ 
The statement is false.

We will construct a bijection between the product of a
countable number of finite sets and the power set of the natural
numbers.  Since the latter is uncountable, the former must be
uncountable as well.

Consider the countable collection of finite sets $S_1 = S_2 = \ldots =
\{ 0, 1 \}$.  The product $S_1 \times S_2 \times \ldots$ consists of
all infinite binary sequences, e.g. $( 0, 1, 1, 0, 1, \ldots)$.  There
is a natural bijection between such infinite binary sequences and the
power set of the natural numbers.  In particular, let the sequence
$(b_0, b_1, \ldots)$ correspond to the set of all natural numbers $i$
such that $b_i = 1$.  This bijection implies that the set of infinite
binary sequences is uncountable.
}

\problempart The set of all finite subsets of a countable set is
countable.

\solution{
The statement is true.

\begin{proof}
Let $S$ be a countable set.  For $k \geq 0$, let $S_k$ be the set of
$k$-element subsets of $S$.  The set of all finite subsets of $S$ is
then the union of the sets $S_k$ for $k \geq 0$.  We will prove below
that every set $S_k$ is countable.  This will imply that the set of
all finite subsets of $S$ is a union of a countable collection of
countable sets and is therefore countable.

All that remains is to show that $S_k$, the set of $k$-element subsets
of $S$, is countable for all $k \geq 0$.  We prove this by
establishing an injection from $S_k$ to $S^k$, the product of the set
$S$ with itself taken $k$ times.  In particular, the injection maps
the set $\{ s_1, s_2, \ldots s_k \} \in S_k$ to the tuple $(s_1, s_2,
\ldots, s_k) \in S^k$, where the elements in the tuple are ordered in
an arbitrary way.  Since $S^k$ is countable, the injection implies
that $S_k$ is also countable.


\end{proof}
}

\problempart Suppose that the intersection of a countable collection
of sets is finite.  Then there exists a finite subcollection of the
sets with finite intersection.

\solution{ 
The statement is false.

Let $S_k$ be the set of integers divisible by $k$, for $k \geq 1$.
The intersection of this countable family of sets is finite; in fact,
the intersection is $\{ 0 \}$, since zero is the only integer
divisible by every positive integer.  However, there is no finite
subfamily of sets $S_k$ with finite instersection.  In particular, the
intersection of the finite subfamily

\[
S_{a_1} \cap S_{a_2} \cap \ldots \cap S_{a_n}
\]

contains all integers of the form $m \cdot a_1 \cdot a_2 \cdots a_n$
where $m \in \mathbb{Z}$.  
}

\end{problemparts}

% Problem 10

% source: fall97 ps7, Rosen? sec. 1.8, problem 30
% topic: infinity

\problem
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.
\newline
\solution{
\begin{proof}
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{proof}
}

% Problem 11

%%%%%%% Problem %%%%%%%%
% source: fall98 ps7, fall97 ps7, spring97 ps7
% topic: infinity, algebraic numbers, diagonalization, Cantor

\problem A real number is {\em algebraic} if it is the root of a
polynomial with rational number coefficients.  Algebraic numbers form
an important part in the study of (what else) modern algebra.  A
number that is not algebraic is called {\em transcendental}.
\bparts

% ?should we exclude this ?next ppart? to shorten the problem?

\ppart Let $S_1,S_2,S_3,\ldots$ be a collection of countably many
sets.  Suppose each $S_i$ is countable.  Prove $\bigcup S_i$ is
countable.

\solution{
\begin{proof}
Since each $S_i$ is countable there is a surjection
$f_i$ from the naturals to $S_i$.
Now define the function 
$f\colon \naturals\times \naturals \to \bigcup_{i\in\naturals}S_i$
by $f(i,j) = f_i(j)$.
Clearly, $f$ is a surjection and since $\naturals\times \naturals$
is countable, also $\cup S_i$ is countable.
\end{proof}
}

\ppart Prove that for any particular $d \in \naturals$, the set of degree $d$
polynomials with rational coefficients is countable, for all $d \geq 1$.

\solution{
\begin{proof}
There is a natural bijection between degree $d$ polynomials
and elements of the set $(\mathbb{Q} \setminus \{ 0 \}) \times
\mathbb{Q}^d$.  Specifically, a degree $d$ polynomial is mapped to an
element of this set by arranging the coefficients in a $(d+1)$-tuple.
The set of rational numbers, $\mathbb{Q}$, was shown to be countable in
lecture.  In the preceding problem, we showed that a finite product of
countable sets is countable.  Therefore, the set $(\mathbb{Q} \setminus
\{ 0 \}) \times \mathbb{Q}^d$ is countable.  The bijection then implies
that the degree $d$ polynomials are countable.
\end{proof}
}

\ppart Prove that the set of all roots of degree $d$ polynomials with
rational coefficients is countable.  (You may use the fact that a degree
$d$ polynomial has at most $d$ roots).

\solution{
\begin{proof}
Since each degree $d$ polynomial has at most $d$ roots we can give a 
surjection from $P_d\times\{1,\ldots, d\}$ to the set of all 
roots of degree $d$ polynomials with rational coefficients.
For example we can define $f(p(x),i) = x_i$,
where $x_1,\ldots, x_d$ are the roots of $p(x)$
(if $p(x)$ has less then $d$ roots, just repeat the last 
one many times).
\end{proof}
}

\ppart Prove that the set of algebraic numbers, which is just the
union of the sets in the previous part, is countable.

\solution{
\begin{proof}
The set of algebraic numbers is the union of the sets 
of the roots of polynomials with rational coefficients
of degree $d$, for all $d$.
This is a countable union of countable sets,
and from the result in part (a) it is countable.
\end{proof}
}

\ppart Prove that there is a trancendental number.

\solution{
\begin{proof}
The set of real number is uncountable.  The subset of
algebraic numbers is countable.  Therefore, the algebraic numbers form
a proper subset of the real numbers, and so there is at least one
transcendental number.
%If there were no transcendental numbers, all numbers would be 
%algebraic, i.e., the set of algebraic numbers equals $\reals$.
%But this is not possible because the reals are not countable.
\end{proof}
}

\eparts

% Problem 12

%%%%%%% Problem %%%%%%%%
% source: spring99 ps8
% topic: infinity, incomputable functions

\problem 
In this problem we will prove the remarkable fact that
there exist mathematical functions that computers, no matter how powerful,
simply cannot compute.  We will do this through countability arguments.
\bparts
\ppart 

Show that the set of finite length binary strings is countable.

\solution{
Let $B_n$ denote the set of binary strings of length $n$.
This set has exactly $2^n$ elements.  Therefore the set of finite
length binary strings $B=\bigcup_{n\in\naturals}B_n$ is a union of
countable number of finite sets.  We know from Lecture 13 that such
union is countable.

Namely, one can easily list all elements of $B$ by first listing the
elements of $B_1$, then the elements of $B_2$, then the elements of
$B_3$, etc,.  We can do this since each set $B_i$ has a finite number
of elements.
}

\ppart 

From your answer to the previous part, 
what can you conclude about the countability of the set of all
computer programs?  

\solution{
Since every computer program can be represented as a finite string of
bits (e.g. machine language code), it follows that the set of all
computer programs is countable.

Namely, the mapping which represents computer programs as finite
strings of bits is an injection.  Hence there is a surjection from the
set of finite strings of bits to the set of computer programs.  From
(a) we know that there is a surjection from the set of natural numbers
to the set of finite strings of bits.  By transitivity of surjective
mapping, there is a surjection between natural numbers and computer
programs.  Hence the set of all comptuer programs is countable.  
}

\ppart 
Show that the set of {\em infinite} length binary strings is uncountable.

\solution{
We construct a bijection from the set of infinite length binary
strings to the power set of the natural numbers.  Since the power set
of the natural numbers is uncountable, it will then follow that the
set of all infinite length binary strings is uncountable.

We need to associate a subset of the naturals with each infinite
length binary string.  Let $b=b_0 b_1 b_2 b_3\ldots $ be an infinite
length binary string (here each $b_i \in \{0,1\}$).  We associate with
this string the set $f(b) = S = \{ i \ | \ b_i = 1 \}$.  That is, we
include $i$ in $S=f(b)$ if and only if the $i$-th bit position (from
the left) of $b$ is 1.  Such mapping $f$ is a bijection: It is an
injection because if two infinite length binary strings are different,
then clearly they map to different subsets.  Furthermore, it is a
surjection because for every subset $S\subset\naturals$, there is a
binary string $b$ s.t. $f(b)=S$, namely $b=b_0b_1b_2b_3\ldots$ where
$b_i$ is defined as $0$ if $i\not\in{S}$ and $1$ if $i\in{S}$.

{\bf Alternative Solution:}
One can also show that the set $B'$ is uncountable directly by a
diagonalization argument.

Assume $B'$ is countable and let $b^{(1)},b^{(2)},b^{(3)},b^{(4)},...$
be a list of all elements of $B'$.  By diagonalization, we will
construct an element $b=b_0b_1b_2b_3...\in{B'}$ s.t. $b\neq b^{(i)}$
for all $i\in\naturals$ as follows: $j$-th bit of $b$ is defined as
the opposite of the $j$-th bit of string $b^{(j)}$.  Obviously, so
defined $b$ is not equal to any $b^{(i)}$ from the list because for
every $i$, the $i$-th bit of $b^{(i)}$ is different than the $i$-th
bit of $b$.  Therefore, the list $b^{(1)},b^{(2)},b^{(3)},b^{(4)},...$
is {\it not} a list of all elements in $B'$, and thus the assumption
that $B'$ is countable leads to a contradiction.  
}

\ppart 
A function is a {\em decision function} if it maps finite length bit
strings into the range $\{0,1\}$.  
% In other words, the function assigns a single bit to every finite length bit string.  
Let $F$ be the set consisting of {\em all possible} decision
functions.  Show that set $F$ is uncountable.

\solution{From part (a), we know that there is a bijection from the set of
all finite length bit strings to the set of natural numbers, hence we
can think of decision functions as mapping natural numbers to single
bits.  

It is an easy bijection between a set of such mappings and a power set
of the natural numbers.  Namely, we associate with a decision function
$f$ a set $S=\{i\in\naturals\mbox{ s.t. }f(i)=1\}$.  Clearly, this is
an injection and a surjection.  Therefore, since the power set of the
set of natural numbers is uncountable then so is the set of decision
functions.

{\bf Alternative Solution:} We can give a bijection between the set of
all decision functions and the set of all infinite length bit strings,
which by part (c), implies that the set of decision functions is
uncountable.  Let $f$ be a decision function.  We map $f$ to an
infinite length string as follows.  We set bit $i$ of the string to be
$f(i)$.  That is, our infinite length bit string will be $f(1) f(2)
f(3) \ldots $.  Now, observe that this mapping is a bijection.  In
particular, suppose we have two different decision functions $f$ and
$g$.  Since they are different, they must give a different output on
some particular input.  Suppose that this particular input is the
number $j$.  That is, $f(j)
\neq g(j)$.  Then, the corresponding infinite length binary strings
will differ in the $j-th$ position.  This shows that the function is
injective.  Now, if we have an infinite length bit string $b_0 b_1 b_2
\ldots$, then a decision function $f$ defined as
$f(0) = b_0, f(1) = b_1, f(2) = b_2, \ldots$, will be mapped to that
string.  Therefore, the mapping function is surjective.  Since it's
injective and surjective, it must be bijective.
{\bf Alternative Solution 2:} 

Some students gave a diagonalization argument for why $F$ is
uncountable: Assume otherwise and let $\{f_1,f_2,f_3,...\}$ be the
list of all elements of $F$.  From part (a) we know that $B$, the set
of all finite length binary strings is countable, so there must exist
a bijection $g:B\rightarrow\naturals$.  Now, define a decision
function $f:B\rightarrow\{0,1\}$ as follows:
\[
f(s)=\mbox{ the opposite of }f_{g(s)}(s)
\]
Then $f$ is different from all $f_i$'s because for all
$i\in\naturals$, $h$ differs from $f_i$ on string $s=g^{-1}(i)$.


{\bf Alternative Solution 3:} 

One can also argue, as some students did, that $F$ is uncountable by
showing the bijection between $F$ and the set, $P(B)$, of all subsets of
$B$.  The bijection associates with $f\in{F}$ a set of strings $b \in B$
s.t. $f(b)=1$.  Then, since by part (a) there is a bijection between $B$
and $\naturals$, there must be a bijection between $P(B)$ and
$P(\naturals)$.  By transitivity of bijective relation between sets, there
is a bijection then between $F$ and $P(\naturals)$.  Hence $F$ is
uncountable.
}

\ppart 

A function is computable if there is a computer program that computes
it.  From your answers to the previous parts, prove that there is a
decision function that is not computable.
% STAS: repetitions...
% That is, there is no computer program that computes it.  

% \ignore{ % STAS: Too much spoonfeeding...
% (Hint: compare your answer from the second part to the the answer you
% just got from the previous part)}

\solution{
Since there are only countably many computer programs,
but uncountably many decision functions, there can be no surjection
from the set of computer programs to the set of decision functions (In
fact, this means that there is {\it more} decision functions than
computer programs).  In particular, if we associate a computer program
to a decision function which this program is computing\footnote{If a
program is not computing any decision function, associate it with a
trivial decision function $f(b)=0$, for all finite bit strings $b$.},
this association is not a surjection either.  Therefore there must be
some decision function which is not computed by any computer program.
}

\eparts


%%%%%%% Problem %%%%%%%%


\end{problems}

\end{document}

\endinput

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% DONE !!! %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%









































%%%%%%% Problem %%%%%%%%
% source: fall94 ps7 bonus problem
% topic: combinatorics, geometry

\problem  
Consider $n$
points located on a circle, and consider the $n\choose 2$ chords
connecting the points.  Assuming that no three chords with distinct
endpoints intersect at a single point, how many points of intersection
among the chords are there in the interior of the circle?

\solution{
If two chords intersect in the interior of the circle, then their endpoints
must be four distinct points.  Since no three chords intersect, any
intersection in the interior corresponds to precisely one set of four points on
the circle.  Furthermore, for any set of four points on the circle, there
is precisly one way to draw a pair of chords which intersect in the interior.
Hence there is a bijection between the intersections in the interior and the
set of four-tuples of points, so there are ${n \choose 4}$ intersections in the
interior.
}


%%%%%%% Problem %%%%%%%%
% source: fall95 ps7
% topic: combinatorics, summations

\problem
Prove that 
\[ {\displaystyle \sum_{k=1}^n}k\left(\begin{array}{c} n\\ k\end{array}\right) = n2^{n-1} \]
\bparts
\ppart using a combinatorial argument.
\ppart by finding a closed form for $ {\displaystyle \sum_{k=1}^n}\left(\begin{array}{c} n\\ k\end{array}\right)kx^k$ and evaluating it at $x=1$.
\eparts


%%%%%%% Problem %%%%%%%%
% source: spring96 ps7
% topic: combinatorics, algebraic manipulation

\problem Prove the following identities both by algebraic manipulation and
by giving a combinatorial argument:
\bparts
\ppart \[{n \choose r}{r \choose k} = {n \choose k}{n-k \choose r-k}\]
\ppart \[{2n \choose 2} = 2{n \choose 2} + n^2\]
\ppart \[ \sum_{k=0}^n 2^k {n \choose k} = 3^n\]
\eparts


%%%%%%% Problem %%%%%%%%
% source: fall97 ps7
% topic: infinity

\problem
Let ${\cal S}_i, 1 \leq i \leq \infty$ be a 
family of countable sets.
Prove that ${\displaystyle \bigcup}^\infty_{i=1} {\cal S}_i$ is countable.

\solution{
\begin{proof}
Since each  $S_i$ is countable, it's elements can be listed in a sequence.
Let $s_{ik}$ be the $kth$ element in the listing of $S_i$. 
We list the sets in the following array

\[ \begin{array}{ccccc}
s_{11} & s_{12}  & s_{13} & s_{14} & \cdots \\
s_{21} & s_{22}  & s_{23} & s_{24} & \cdots \\
s_{31} & s_{32}  & s_{33} & s_{34} & \cdots \\
s_{41} & s_{42}  & s_{43} & s_{44} & \cdots \\
\cdots & \cdots  & \cdots & \cdots & \cdots \\
\end{array} \]

We can count the elements using the
dove-tailed interleaving shown in class, to get the listing for their
union. The resulting list is $\{ s_{11}, s_{12}, s_{21}, s_{13},
s_{22}, s_{31}, \ldots \}$. 

Since we have been able to give a valid listing, $ {\displaystyle
\bigcup}^\infty_{i=1} {\cal S}_i $ is countable.
\end{proof}
}


%%%%%%% Problem %%%%%%%%
% source: spring99 ps8
% topic: infinity, digraphs

\problem 

Show that any set of finite digraphs, no two of which are isomorphic to
each other, is countable.

\solution{
Let's define an \emph{integer digraph} to be a digraph whose
vertices are precisely the set of integers $\set{1,2,\dots,n}$ for some $n
\in \naturals$.  Every finite digraph is obviously isomorphic to an
integer digraph.  So if $A$ is some set of finite digraphs no two of which
are isomorphic, then there is an injection from $A$ to the set, $D$, of
all integer digraphs.  Hence, if we show that $D$ is countable, it will
follow that $A$ is countable.

To show that $D$ is countable, let $D_n$ be the set of all integer
digraphs with $n$ vertices.  But each graph in $D_n$ can be uniquely
represented by an $n \times n$ adjacency matrix.  Since there are $n^2$
single bit entries in the adjacency matrix ($0$ or $1$), it follows that
there can be at most $2^{n^2}$ adjacency matrices.  So $D_n$ is of finite
size $2^{n^2}$.  But $D= \bigcup_{n\in\naturals} D_n$, and we know, by a
similar argument to problem (1a), that the union of a countable number of
finite sets is countable.

{\bf Alternative Solution:}

Some students argued this claim a little differently.  Namely, if $D'$
is some set of finite digraphs, no two of which are isomorphic to each
other, then there $D' \,\mbox{\it inj}\, M$, where $M$ is a set of all
binary matrices.  An injection $f:D'\rightarrow{M}$ associates each
digraph with its adjacency matrix.  If no two digraphs in $D'$ are
isomorphic to each other, $f$ is an injection.  Furthermore,
$M\,\mbox{\it inj}\, B$, where $B$ is the set of finite binary strings,
where the injection between $M$ and $B$ concatenates all rows (or
columns) of the binary matrix in a single binary string.  And now
since we know that $B$ is countable, i.e. $B\,\mbox{\it inj}\, \naturals$
(problem 1 part (a)), it follows that $D'\,\mbox{\it inj}\, \naturals$,
i.e.  $D'$ is countable.
}       


%%%%%%% Problem %%%%%%%%
% source: spring99 ps8
% topic: infinity, sets

\problem 

Let $A_1,A_2,\dots$ be an infinite sequence of nonempty, finite sets.
For any $k\in \naturals$, the product $A_1 \times A_2 \times \cdots
\times A_k$ is finite, and hence countable.  In this problem we
consider countability of the \emph{infinite} product $P ::= A_1 \times
A_2 \times A_3 \times \cdots$, which is a set of infinite strings
$(a_1,a_2,a_3,...)$ such that $a_i\in{A_i}$ for all $i \in \mathbb{N}$.

\bparts 

\ppart State a simple necessary-and-sufficient condition for $P$ to be
finite.

\solution{
The product can be finite exactly when some finite number, $n$,
of the sets $A_i$ have more than one element, and the others have one
element.  It is easy to see that the condition is necessary, i.e. that
if there is no such number $n$ then $P$ is infinite.  To show that our
condition is also sufficient, say that $A_{i_1},\dots,A_{i_n}$ are the
sets with more than one element.  Let $f$ be the function which maps
any element of the infinite product into the $n$-tuple consisting of
the elements in positions $i_1,\dots,i_n$.  It is easy to see that $f$
is a bijection from the infinite product to the finite product
$A_{i_1} \times \dots\times A_{i_n}$.  Since a finite product of
finite sets is itself a finite set, we conclude from the bijection
that the infinite product is also a finite set.
}

\bigskip
\ppart
Show that $P$ is countable iff it is finite.

\solution{
Clearly, if $P$ is finite then it is countable.  We need to show also
that if it is countable than it is finite.  We will prove the
counterpositive of that claim, i.e. that if it is infinite than it is
uncountable.  Because the condition stated in part (a) was sufficient
for $P$ to be finite, it follows that if $P$ is infinite than there is
an infinite number of sets $A_i$ with more than one element.

We show that if an infinite number of sets $A_i$ have more than one
element, then the set $P$ which is the product of all $A_i$'s is
uncountable.  Let $A'_1, A'_2, \ldots$ denote the sets among the
$A_i's$ that have more than one element.  That is each, $A'_i$
uniquely corresponds to some set $A_j$ that has more than one element.
Now, if we can show that $P'=A'_1\times A'_2\times\cdots $ is
uncountable, then this implies that $P=A_1\times A_2\times\cdots$ is
uncountable too: It is easy to construct a bijection between $P$ and
$P'$, similar to the one used in part (a).

For every $i$, we can denote the elements of $A'_i$ as $\{a^i_0,a^i_1,
\dots, a^i_{k_i}\}$, where $|A'_i|=k_i+1$ and $k_i \geq 1$.  We will give an
injection $f$ from the set $B'$ of infinite length binary strings to set
$P'$.  Since from problem (1c) we know that the set $B'$ is uncountable,
this will imply that $P'$ is also uncountable.\footnote{In case this is
not obvious: We know that a set $A$ is countable if and only if there is
an injection from $A$ to $\naturals$ (e.g. Problem 1 in section 6 of
Handout 38).  Therefore, if $P'$ was countable than there would be an
injection $g$ from $P'$ to $\naturals$ and then $g\circ{f}$ would be an
injection from $B'$ to $\naturals$, and hence $B'$ would be countable too.
Contradiction.} Define $f:B'\rightarrow{P'}$,
$f(b_1b_2b_3\dots)=(a^1_{b_1},a^2_{b_2},a^3_{b_3},\dots)$.  Clearly, $f$
is an injection, which ends the proof.  }

\eparts

%%%%%%% Problem %%%%%%%%
% source: fall94 ps7
% topic: binomial theorem

\problem Let $n, r\in\naturals$.
Use the binomial theorem to evaluate the expressions
\[\sum_{k=0}^{n}{n\choose k}r^k 
\;\;\mbox{ and }\;\;
\sum_{k=0}^{n}{n\choose k}(-r)^k\ .\]
%       (\hint $(-1)^k = \pm (-1)^{n-k}$.)
Use your analysis to conclude that if $r$ is odd, then
\[\left. 2^{n-1} \;\right| \sum_{\stackrel{\scriptstyle k=0}{k {\mathrm{\ even}}}}^{n}{n\choose k}r^{k}\ .\]

Note that if $r=1$, this sum simply counts the number of even-sized
subsets of an $n$-set, which we know is exactly $2^{n-1}$.


%%%%%%% Problem %%%%%%%%
% source: fall95 ps7
% topic: combinatorics, morse code

\problem 
Morse code is a system for representing an alphabet with dots and
dashes.  The arrangements of dots and dashes is then transmitted using
eletrical pulses of varying lengths or analogous mechanical or visual
signals. For example, the letter A may be represented by dash-dot-dot
and the letter B by dash-dot.  Since it takes time and effort to
transmit, the code must be as compact as possible. For a compact code
what is the maximum number of dots/dashes required by any character if
we wish to represent
\bparts
\ppart the letters A,B,$\ldots$,Z?
\ppart the letters A,B,$\ldots$,Z,a,b,$\ldots$,z,0,1,$\ldots$,9? 
\ppart Given that two dots in a row can get confused with a dash, how many 
different characters can you represent with $k$ dots/dashes that have no consecutive dots?
\ppart Suppose a dot takes 1 seconds, a dash takes 3 seconds, and each must
be followed by a 1 second interval of silence.  How many morse symbol
sequences have sending times less than k seconds (including the last
interval of silence)? 
\eparts
Hint: For parts c) and d) determine and solve a recurrence
conditioning on the value of the first symbol.


%%%%%%% Problem %%%%%%%%
% source: fall94 ps7
% topic: combinatorics

\problem
Without using the formula for $n \choose k$,
give a combinatorial argument to prove that the identity
\[
{s-1\choose 0} + {s\choose 1} + \cdots + {s+n-2\choose n-1}+ {s+n-1\choose n} 
= 
{s+n\choose n}
\]
holds, where $s$ and $n$ are positive integers.
(\hint If $X$ is an $(s+n)$-set\footnote{That is, a set containing
$s+n$ elements}
and $Y=\{ y_1, y_2, \ldots, y_n\}$ is a specific $n$-subset of $X$, 
what is the number of $n$-subsets of $X$ for which $y_r$ is the first member
of $Y$ not in the subset?)


%%%%%%% Problem %%%%%%%%
% source: spring98 ps7
% topic: combinations, standard stars and bars

\problem

Calculate the number of ways to place 11 {\em indistinguishable} balls in four 
{\em distinguishable} boxes so that each box contains at least one,
but no  more than four, balls.

\solution{
First place one ball in each box.  Then we must distribute 7 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 7 balls in 4 boxes:
${7+4-1 \choose 7} = {10 \choose 7}$.

Number of ways to place 7 balls in 4 boxes such that there are four balls
in a box =  number of ways to choose box with four balls * number of ways
to place remaining three balls in remaining three boxes =
$4 \cdot {5 \choose 3}$.

Number of ways to place 7 balls in 4 boxes such that there are five balls
in a box = $4 \cdot {4 \choose 2}$.

Number of ways to place 7 balls in 4 boxes such that there are six balls
in a box = $4 \cdot {3 \choose 1}$.

Number of ways to place 7 balls in 4 boxes such there are seven
balls in a box = 4.

So the total number of ways is

${10 \choose 7} - 4 \left({5 \choose 3} +
{4 \choose 2}+{3 \choose 1} +1 \right) = 40$
}


%%%%%%% Problem %%%%%%%%
% source: fall95 ps7
% topic: combinatorics, counting relations

\problem
On a set of $n$ elements how many of the following are there
\bparts
\ppart relations?
\ppart symmetric relations?
\ppart reflexive relations?
\ppart symmetric and reflexive relations?
\ppart symmetric or reflexive relations?
\ppart equivalence relations (this problem is for extra credit)?
\eparts


