\documentclass[12pt,twoside]{article}
\usepackage{amsmath}
\usepackage{graphics}
\input{macros-course}
\newcommand{\ignore}[1]{}

\begin{document}
\psol{8}{April 6, 1999}

%\newcommand{\solution}[1]{}
\newcommand{\solution}[1]{\bigskip \textbf{Solution}:\\ #1}

{\bf Reading assignment}: Rosen sections 4.1-4.3, 5.5-5.6, and pages
76--78 (same pages in both editions); Fall 97 Lecture Notes 13 \& 14;
and Handout 38: Notes on Cardinality.

\begin{problems}

\problem {\bf (20 Points)}
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.


{\bf Alternative Solution:} 
Some students noticed that finite length binary strings can be thought
of as natural numbers represented base $2$.  Therefore, an injective mapping
from finite length binary strings to natural numbers can be constructed as
follows:
\[
f(b_0b_1b_2...b_n)= 2^{n+1}+(b_0+b_12+b_22^2+...+b_n2^n)
\]
i.e. we map a string of bits to a natural number that it represents
in binary, except that we add $2^{n+1}$ term to make sure that bit
strings of different length get mapped to a different natural number
(Otherwise strings $0010$, $010$, $10$ would all map to the same number).
You can check that $f$ is an injection from $B$ to $\naturals$ and hence
$B$ is countable.  

You can also easily modify $f$ to be a bijection if instead of adding
$2^{n+1}$ term to the right side, you add $2^{n+1}-1$.  }

\bigskip
\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 computer programs is countable.  }

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

\solution{We construct a bijection from the set $B'$ of infinite length binary
strings to the power set of the natural numbers $P(\naturals)$.  Since
$P(\naturals)$ is uncountable, it will then follow that $B'$ 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 \in{B'}$ 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:B'\rightarrow{P(\naturals)}$ 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\in P(\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.  

}

\bigskip
\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 (because
the set of all finite length bit strings was infinite and countable),
hence we can think of decision functions as mapping natural numbers to
the range $\{0,1\}$, i.e. to single bits.

It is easy to see a 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
both injective and surjective, it is also 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)$, i.e. the set 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.

}

\bigskip
\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 spoon-feeding...
(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{\bf (15 points)}

\bparts

\ppart (10 points) Let $[0,1]$ be the closed unit line segment, i.e.,
$\set{r \in \reals \mid 0 \leq r \leq 1}$.  Show that there is a bijection
from $[0,1]$ to the whole real line, i.e., to $\reals$.

\solution{
Obviously, $f_1:[0,1]\rightarrow\reals$ s.t. $f(x)=x$ is an injection
between the two sets.  There are many ways to construct a surjection
$f_2:[0,1]\rightarrow\reals$, for example it can be a superposition
$f_2(x)=h(g(x))$ of two surjections $g:[0,1]\rightarrow[-1,1]$ and
$h:[-1,1]\rightarrow\reals$ defined as follows:
\begin{eqnarray*}
g:[0,1]\rightarrow[-1,1]
&&
g(x)=2x-1
\\
h:[-1,1]\rightarrow\reals
&&
h(x)=\left\{\begin{array}{lll}
	1/x-1 	& x>0 	& (\mbox{This maps interval $(0,1]$ to $[0,\infty)$})\\
	0   	& x=0	&\\
	1/x+1	& x<0	& (\mbox{This maps interval $[-1,0)$ to $(-\infty,0]$})
	\end{array}\right.
\end{eqnarray*}
If there is a surjection from $[0,1]$ to $\reals$ then, by an
elementary fact listed in Lemma 2.3 in Handout 38, there exists an
injection from $\reals$ to $[0,1]$.  Therefore, by the
Schroeder-Bernstein theorem (Tutorial 8, and section 5 in Handout 38),
there exists a {\em bijection} between $[0,1]$ and $\reals$.

{\bf Alternative Solution:}

Some students constructed a direct bijection between $[0,1]$ and
$\reals$ by superimposing two bijections: $f_1:[0,1]\rightarrow(0,1)$ and
$f_2:(0,1)\rightarrow\reals$:
\[
f_1(x)=\left\{\begin{array}{ll}
	\frac{1}{n+2}	& \mbox{If $x=\frac{1}{n}$ for some $n\in\naturals$}\\
	\frac{1}{2}   	& \mbox{If $x=0$}\\
	x		& \mbox{Otherwise}
	\end{array}\right.
\]
\[
f_2(x)=\tan \left(\pi x-\frac{\pi}{2}\right)
\]


}

\bigskip
\ppart (5 points) Conclude that there is a bijection between the unit line
segment and the whole plane, i.e., between $[0,1]$ and $\reals \times
\reals$. \hint See Handout 38: Notes on Cardinality.

\solution{
By Theorem 7.2 in Handout 38, there is a bijection between $\reals$
and $\reals^2=\reals\times\reals$.  By Part (a), there is a bijection
between $[0,1]$ and $\reals$.  Hence, by transitivity of bijective
relation between sets, there is a bijection between $[0,1]$ and
$\reals^2$.
}

\eparts  

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


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem {\bf (15 Points)}


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 than 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,
..., a^i_{k_i}\}$, where $|A'_i|=k_i$.  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\ldots)=(a^1_{b_1},a^2_{b_2},a^3_{b_3},\ldots)$.  Clearly,
$f$ is an injection, which ends the proof.  }

\eparts

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

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem {\bf (10 Points)}

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 a
set of $D$ of all integer digraphs.  Hence, if we show that $D$ is
countable, it will follow that $A$ is countable.

To show that the set of all integer digraphs 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 the
set of all integer digraphs is $\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 {\bf (10 Points)}

Denote by $\{0,1\}^n$ the set of all bit strings of length $n$.

\bparts

\ppart

How many functions are there with domain $\{0,1\}^m$ and range
$\{0,1\}^n$?

\solution{There are $2^m$ elements in the domain.  There are $2^n$ elements in
the range.  For every element in the domain, we thus have $2^n$
choices for what we can map it to.  Therefore, by the product rule,
there are $(2^n)^{2^m}$ possible functions with domain $\{0,1\}^m$ and
range $\{0,1\}^n$.}

\bigskip
\ppart

How many functions with domain and range $\{0,1\}^n$ are {\em not
bijections}?

\solution{There are $2^n$ elements in both the domain and range.  Hence there
are a total of $(2^n)^{2^n}$ functions.  Now, of these functions
we know that $(2^n)!$ are permutations.  Hence the remaining are not
permutations.  The total number of functions with domain and range 
$\{0,1\}^n$ that are not {\em permutations} is $(2^n)^{2^n} - (2^n)!.$}

\bigskip
\ppart

A value $x$ is called a {\em fixed point} of a function $f$ if
$f(x) = x$.  
How many functions from $\{0,1\}^n$ to $\{0,1\}^n$ have {\em no} 
fixed points?

\solution{We have $2^n$ elements in the domain, and each of them can be possibly 
mapped to $2^n - 1$ elements in the range (any element but itself).
Therefore, there are $(2^n-1)^{2^n}$ total functions with no fixed
points.}

\bigskip
\ppart 
How many functions from $\{0,1\}^n$ to $\{0,1\}^n$ have {\em at least one} 
fixed point?

\solution{There are $(2^n)^{2^n}$ functions total, and $(2^n-1)^{2^n}$
have no fixed points.  Therefore, the remaining $(2^n)^{2^n} -
(2^n-1)^{2^n}$ have at least one fixed point.}

\bigskip
\ppart
How many functions from $\{0,1\}^n$ to $\{0,1\}^n$ have {\em exactly one} 
fixed point?

\solution{Let's fix a particular point for our fixed point.  Now let's
consider where the remaining $2^n - 1$ points can be mapped.  Each one can
be mapped to any spot but itself -- thus it can be mapped to at most $2^n
- 1$ spots.  For each particular fixed point, there are $(2^n - 1)^{2^n -
1}$ functions.  Since there are $2^n$ possible choices for the particular
fixed point, the total number of functions with exactly one fixed point is
$2^n(2^n - 1)^{2^n - 1}$.}

\eparts

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

\problem{\bf (10 points)}

How many zeroes does the decimal representation of $100!$ end with?

\solution{
$100!$ ends in $k$ zeros where $k$ is the largest number s.t. $10^k$
divides $100!$.  Since $10 = 2\cdot 5$, we know that
$10^k=2^k\cdot5^k$, and so we are looking for the largest $k$ such
that $2^k\cdot5^k\, |\, 100!$.  Clearly, $2^k$ divides $100!$ for
larger $k$ than $5^k$ divides $100!$, since multiples of two are more
common in $100!$ than multiples of five.  So, we just need to
determine the largest $k$ such that $5^k$ divides $100!$, in other
words the number of multiples of $5$ contained in
$100!=1\cdot2\cdot3\cdot...\cdot100$.  Each multiple of $5$ less than
or equal to $100$ will contribute one to this $k$.  There are $20$
such multiples: $5, 10, 15, ..., 95, 100$.  Each multiple of $25$ will
contribute two to this $k$, since $25^n = 5^n\cdot5^n$.  There are
four of these: $25, 50, 75, 100$.  So, multiples of $25$ contribute a
total of $8$.  However, the set of multiples of $25$ is a subset of
the set of multiples of $5$, and so we have double counted some
elements, and we must substract one double-counted contribution to $k$
from each multiple of $25$, i.e. $4$.  This gives the total of
$20+8-4=24$ zeroes in $100!$.
}

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

\problem {\bf (10 Points)}

Using the principle of inclusion-exclusion, show that there are fewer than 
50,000 prime numbers less than or equal to 210,000.

\solution{
Since natural numbers are either composite or prime, we can instead
show that there are at least $210,000 - 50,000 = 160,000$ composite
numbers less than or equal to $210,000$.  Let's count composite
numbers by counting the multiples of $2, 3, 5$, and $7$:

\[\begin{array}{lll}
\mbox{multiples of }2: &210,000/2 &= 105,000\\
\mbox{multiples of }3: &210,000/3 &= 70,000\\
\mbox{multiples of }5: &210,000/5 &= 42,000\\
\mbox{multiples of }7: &210,000/7 &= 30,000\\
\hline
  &&+ 247,000
\end{array}\]

However, we have double counted the numbers which are multiples of two
of $\{2, 3, 5, 7\}$.  So, using inclusion/exclusion, we subtract these
back out:

\[\begin{array}{lll}
\mbox{multiples of }\{2,3\}: & 210,000/6 &=  35,000\\
\mbox{multiples of }\{2,5\}: & 210,000/10 &=  21,000\\
\mbox{multiples of }\{2,7\}: & 210,000/14 &=  15,000\\
\mbox{multiples of }\{3,5\}: & 210,000/15 &=  14,000\\
\mbox{multiples of }\{3,7\}: & 210,000/21 &=  10,000\\
\mbox{multiples of }\{5,7\}: & 210,000/35 &=  6,000\\
\hline
  &&- 101,000
\end{array}\]

Now, we must add back in the numbers which are multiples of three of
$\{2, 3, 5, 7\}$:

\[\begin{array}{lll}
\mbox{multiples of }\{2,3,5\}: & 210,000/30 &=  7,000\\
\mbox{multiples of }\{2,3,7\}: & 210,000/42 &=  5,000\\
\mbox{multiples of }\{2,5,7\}: & 210,000/70 &=  3,000\\
\mbox{multiples of }\{3,5,7\}: & 210,000/105 &= 2,000\\
\hline
 &&+  17,000
\end{array}\]

And subtract out the multiples of $2\cdot3\cdot5\cdot7 = 210$:

\[\begin{array}{lll}
\mbox{multiples of }\{2,3,5,7\}: & 210,000/210 &=  1,000\\
\hline
 &&-  1,000
\end{array}\]

Totaling, we get $247,000 - 101,000 + 17,000 - 1,000 = 162,000$, which
is more than $160,000$ that we needed to show that there are fewer
than $50,000$ prime numbers less than or equal to $210,000$.





}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\problem {\bf (10 Points)}
% STAS: change of exercise 23 from Rosen 4.3 to r-permutations

The English alphabet contains $21$ consonants and five vowels.
Suppose that all strings of six English alphabet characters with no
repetitions were English words.  How many such words contain:

\bparts

\ppart exactly $1$ vowel?
\ppart exactly $2$ vowels?
\ppart at least $1$ vowel?
\ppart at least $2$ vowels?

\eparts

\noindent
{\bf Solution:}
\begin{enumerate}
\item[{\bf (a):\ }]

$P(21,5)\cdot5\cdot6=(21\cdot20\cdot19\cdot18\cdot17)\cdot30=73,256,400$:
A choice of $5$ consonants with no repetition, a choice of a vowel,
and a choice of vowel's position.

\item[{\bf (b):\ }]
 
$P(21,4)\cdot(5\cdot4)\cdot(6\cdot5/2)=
(21\cdot20\cdot19\cdot18)\cdot20\cdot15=
43,092,000$: A choice of $5$ consonants with no repetition, a choice
of $2$ vowels, and a choice of the vowels' positions.

\item[{\bf (c):\ }]

$P(21+5,6)-P(21,6)=21\cdot6,033,120=126,695,520$: All words minus
words with no vowels.

\item[{\bf (d):\ }]

$P(21+5,6)-P(21,6)-P(21,5)\cdot5\cdot6=
126,695,520-73,256,400=53,439,120$: As above minus part (a).

\end{enumerate}




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

\end{problems}

\end{document}




