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

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

\begin{document}

\psol{4}{March 10, 1995}

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

\begin{proof}
To prove this it is enough to show that a countable union of countable sets
is countable.  Why?  If we have a countable cover of an uncountable set $X$
where each of the sets is countable, then the union of all of the sets in the
cover is countable.  But $X$ is uncountable, a contradiction.

To show that a countable union of countable sets is countable note that
any element in the union can be denoted by $a_{i,j}$, i.e.\ the $i$th
element of the $j$th set.  So we have an surjective function $f : \nat
\times \nat \rightarrow X$ by $f(i,j) = a_{i,j}$.  But we know that $\nat
\times \nat$ is countable so we have a surjection from a countable set to
$X$.  Thus $X$ is countable.  
\end{proof}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\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\}$?

\begin{proof}
It is $|B|^{|A|}$.  Why?  To totally specify the function it is enough to
give its value at each element of $A$.  There are $|B|$ choices for each
element of $A$ and so the total number of functions is $|B|^{|A|}$.

\end{proof}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\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.  
What is the smallest number of keys that we have to distribute?


We need 990 keys.

\begin{proof}
If we give all of the keys to each of $11$ guests, then
any subset of $90$ guests must contain one of these ``special'' guests who
can open all of the rooms.   We must now show that it can't be done with
fewer keys.  Let $g_i$ for $i=1,\ldots,90$ be the number of guests that have a
key to room $i$.  We know that $\sum g_i \leq 989$ and so some $g_k$ must be
less than $11$ (If not then the sum would be greater than 990).  In
other words fewer than $11$ guests have keys to this room.  So if we
pick all of the guests that don't have keys to this room then we have
at least 90 guests who can't open room $k$.  
\end{proof}

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

Let $c \in C$. Since $g$ is a surjection, there must exist $b \in B$ such
that $g(b) = c$.  Similarly there must exist $a \in A$ such that $f(a) = b$.
Thus $(g \circ f)(a) = c$ and $g \circ f$ is 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.

We already know that $g \circ f$ is a surjection.  To prove it is injective,
let $(g \circ f)(x) = (g \circ f)(y)$.  Then it must be that $f(x) = f(y)$
since $g$ is injective.  But since $f$ is also injective $x = y$.

\ppart 
If $g\circ f$ is a bijection, what can you conclude about $f$ and $g$?

$g$ must be surjective.  If not then there will be elements of $C$ that are
not $g(f(a))$ for any $a$.

$f$ must be injective.  If there exist $x$ and $y$ with $x \neq y$ such
that $f(x) = f(y)$ then $g(f(x)) = g(f(y))$.

$g$ isn't necessarily injective and $f$ isn't necessarily surjective.
Consider $f: \{1,2\} \rightarrow \{1,2,3\}$ where $f(x) = x$ and $g :
\{1,2,3\} \rightarrow \{1,2\}$ where $g(1) = g(3) = 1$ and $g(2) = 2$.  $g
\circ f$ is a bijection but $f$ isn't surjective and $g$ isn't injective.
\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.  

\begin{proof}
Let us prove this for a full binary tree (every node either has 0 or 2
children).  We will do this by induction on the maximum depth of the tree.

\begin{description}
\item[Base Case:] The maximum depth is $0$.  In this case we just have one
node of depth $0$ (which is a leaf) and so the left hand side if the sum is
$2^0 = 1$.
\item[Inductive Step:] Assume the inequality holds for all trees with
maximum depth less than $k$.  We are now given a full binary tree $T$ with
maximum depth $k$.  Remove
the root giving $2$ full binary trees $T_1$ and $T_2$.  The depth of every
node in $T_1$ and $T_2$ is one less than in $T$ and so we can apply the
inductive hypothesis and assume that:
\[ \sum_{\mbox{\scriptsize leaves in } T_1} 2^{-d(x)} \leq 1 \] and
\[ \sum_{\mbox{\scriptsize leaves in } T_2} 2^{-d(x)} \leq 1 \]

But the leaves in $T$ are just the union of the leaves in $T_1$ and $T_2$.
Note also that the depths of these leaves in $T$ are one more than the
depths in $T_1$.  Thus $2^{-(\mbox{\scriptsize depth in }T)} = 1/2 \times
2^{-(\mbox{\scriptsize depth in } T_1)}$.
Therefore we divide both expressions above by 2 to get
\[ \sum_{\mbox{\scriptsize leaves in } T} 2^{-d(x)} \leq 1/2 + 1/2 = 1 \]

\end{description}

\end{proof}

\end{problems}

\end{document}
