\documentstyle[12pt,twoside,amstex]{article}
\input{macros-course}

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

{\bf Reading assignment}: Rosen sections 4.1-4.3, 5.5-5.6, pages and
76-78, and Fall 97 lecture notes 14-15.

%% topics to cover:
%% Infinite Sets
%% Countable vs. Uncountable sets.
%% Sum/Product rules
%% Permutations
%% Inclusion/Exclusion.

\begin{problems}

\problem {\bf (20 Points)}
\bparts
\ppart 

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

\ppart 

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

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

\ppart 
A function is a decision function if it maps finite length 
bit strings into the range $\{0,1\}$.       
Let $F$ be the set consisting of {\em all possible} decision functions. 
Show that the set $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 are decision functions that are not
computable.  That is, no computer program can compute it.  
(Hint: compare your answer from the second part to the the
answer you just got from the previous part)

\eparts

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

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

We would like to show that there is a bijection from the unit line $[0,1]$ 
to the unit sphere (all points that have distance exactly one from the 
origin in three dimensional space).  We know that we can do this by giving
two injections.

\bparts

\ppart (5 points) 
Show that there is an injection from the unit line to the unit sphere.

\ppart (10 points) 
Show that there is an injection from the unit sphere to the unit line.

\ppart (Extra Credit) Give a bijection from the unit
line to the unit sphere.

\eparts  

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


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

Recall from lecture that if $A_1, \ldots, A_k$ is a collection of
{\em finite} sets, then the product $A_1 \times A_2 \times \cdots
\times A_k$ is finite, and hence countable.  What happens if 
you consider a countably infinite collection of finite sets.  That
is suppose $A_1, A_2, \ldots$ is an infinite collection of sets,
each of which is finite but non-empty.  What happens when you take 
the infinite product $A_1 \times A_2 \times \cdots $?  Is it countable? 
uncountable?  Please justify your answer.  
    

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

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

Show that the set of all directed acyclic graphs is countable. 


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



\problem {\bf (15 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$?

\ppart

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

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

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

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

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

\eparts

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

\problem{\bf (15 points)}

Compute the number of  0's at the end of $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.

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

\end{problems}

\end{document}




