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

%	\addtolength{\topmargin}{-.35in}
%	\setlength{\textheight}{9in}

\begin{document}

\pset{4}{March 2, 1995}{In recitation, March 10}

\bigskip


\begin{problems}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem

Prove that any countable cover of an uncountable set contains an
uncountable set. (Recall that a {\em cover} of $X$ is a collection of 
sets whose union is $X$).

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem

Let $A$ and $B$ be finite sets.  How many functions are there from $A$ to
$B$?  That is, what is the cardinality of $\{f \mid f : A \rightarrow B\}$?

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem

A certain hotel has $90$ rooms and $100$ guests.  
We wish to give keys to the guests so that any subset of $90$ guests
collectively hold keys to all of the rooms.  
(Different rooms require different keys.)
What is the smallest number of keys that we have to distribute?
Prove your answer.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem

Recall that the composition $g \circ f$ of two functions $f$ and $g$ 
is defined by $(g \circ f)(x) =g(f(x))$.
\bparts
\ppart 
Show that if $f: A \rightarrow B$ and $g : B \rightarrow C$ are both
surjections, then $(g \circ f) : A \rightarrow C$ is also a surjection.
\ppart 
Show that if $f : A \rightarrow B$ and $g : B \rightarrow C$ are both
bijections, then $(g \circ f) : A \rightarrow C$ is also a bijection.
\ppart 
If $g\circ f$ is a bijection, what can you conclude about $f$ and $g$?
\eparts

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%\problem

%Recall that a full binary tree is one in which every node is either a leaf
%or has two children.  Define the internal path length of a full binary tree
%to be the sum, taken over all of the internal nodes of the tree, of the
%depth of each node (the root has depth 0).  Similarly the external path
%length is the sum of the depths of all of the leaves of the tree.  Consider
%a full binary tree with $n$ nodes, internal path length $i$, and external
%path length $e$.  Prove that $e = i + 2n$.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem

For any rooted binary tree, let $d(x)$ denote the depth of node $x$ 
in the tree.  (The depth of the root is~0.)
%	Associate with each leaf $x$ of a rooted binary tree a ``weight'' 
%	$w(x) = 2^{-d(x)}$ where $d(x)$ is the depth of $x$.  
Prove that 
\[
\sum_{\mbox{\scriptsize leaves }x} 2^{-d(x)} \leq 1
\]
 where the sum is over all {\em leaves} in the tree.  

\end{problems}

\end{document}
