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

\begin{document}
\pset{8}{March 30, 1999}{Tuesday, April 6}

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

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

}

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

\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 are more decision functions
than computer programs.  Hence there must be some decision function which
cannot be computed by a 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$.

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

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

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

\solution{
%  This statement is ``iff''-- need both directions.  EL

We show that if an infinite number of sets $A_i$ have more than
one element, then the product is uncountable.  Let $B_1, B_2, \ldots$
denote the sets among the $A_i's$ that have more than one element.  That
is each, $B_i$ uniquely corresponds to some set $A_j$ that has more than
one element.  Now, if we can show that $B_1 \times B_2 \times \cdots $ is
uncountable, then this implies that $A_1 \times A_2 \times \cdots$ is
uncountable because (REVISE THIS USING PROJECTION
FUNCTION LIKE $F$ IN PREVIOUS SOLUTION:)
 all we did to get from the $A_i$'s to the $B_i$'s was
to remove all the $A_j$'s with one element, and one element sets don't add
to the number of elements in the product.  
 
REVISE THE FOLLOWING SOLUTION TO USE SURJECTION FROM PROD OF $B_i$'S TO
INFINITE BIT-STRINGS B CHOOSING SOME ELEMENT $B_i\in B_i$ FOR EACH $i$ AND
MAPPING ELEMENT, $P$, OF THE PRODUCT OF $B_i$'S TO THE BIT STRING WHOSE
$i$TH ELEMENT IS 1 IFF THE $i$TH COMPONENT, $P_i$ OF $P$ EQUALS $B_i$.

Let's consider the case that each $B_i$ has exactly two elements.  
Denote by $\beta^i_1, \beta^i_0$ the two elements in the set $B_i$.  We 
will give
a bijection from the set of infinite length binary string to the product
$B_1  \times B_2 \times \cdots $.  Since the set of infinite length binary
strings is uncountable, we will have shown uncountability of the infinite
product of the $B_i's$.  Now, let $b_1 b_2 b_3 \ldots $ be an infinite 
length binary string.  We must associate this string with an element of
the infinite cross product of the $B_i$'s.  We associate with 
$b_1 b_2 b_3 \ldots $ the element 
$(\beta^1_{b_1}, \beta^2_{b_2}, \beta^3_{b_3}, \ldots )$.  
This gives us a bijection.

Now, the only remaining case is that some of the $B_i$'s might have 
more than two elements.  However, if all the $B_i's$ have at least
two elements, then the resulting product will have at least as many
elements as the product when each $B_i$ had exactly two elements.  Therefore
we have that the product of the $B_i$'s are uncountable in this case
as well.}

\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 a set of finite digraphs no two of
which are isomorphic, then there is a bijection from $A$ to a set of
integer digraphs.  Hence, if we show that the set of all integer
digraphs is countable, it will follow that $A$ is countable.

To show that the set of all integer digraphs is countable, let $D_n$
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$ 0-1-valued entries in the adjacency matrix, 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 (from Lecture 13 Notes) that the union of
a countable number of finite sets 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$.}

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

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

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

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

\ignore{ % STAS: math is ugly, what's the point?
\ppart 
How many functions from $\{0,1\}^n$ to $\{0,1\}^n$ have {\em at least two} 
fixed points?
\solution{Now, there are $(2^n)^{2^n}-(2^n-1)^{(2^n)}$ with at least one
fixed point.  Of these functions, $2^n(2^n - 1)^{2^n - 1}$ have
exactly one fixed point.  Therefore, the remaining
\[(2^n)^{2^n}-(2^n-1)^{(2^n)} - 2^n(2^n - 1)^{2^n - 1} \]
have at least two fixed points.}
} %END IGNORE

\eparts

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

\problem{\bf (10 points)}

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


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

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

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

\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

\solution{

\bparts

\ppart 
$P(21,5)*5*6$: a choice of $5$ consonants with no repetition, a choice
of a vowel, and a choice of vowel's position.
\ppart 
$P(21,4)*(5*4)*(6*5/2)$: a choice of $5$ consonants with no
repetition, a choice of 2 vowels, and a choice of vowels' positions.
\ppart at least $1$ vowel?
$P(21+5,6)-P(21,6)$: all words minus words with no vowels.
\ppart at least $2$ vowels?
$P(21+5,6)-P(21,6)-P(21,5)*5*6$: as above minus part (a).

\eparts

}


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

\end{problems}

\end{document}




