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

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

\newcommand{\problm}{\problem \rm}
\renewcommand{\ppart}{\problempart \rm}
\newcommand{\pf}{\begin{proof}\sf}
\newcommand{\soln}{\sf}
\newcommand{\thm}{\begin{theorem}\ \ }
\newcommand{\mystrut}{\rule{0pt}{14pt}}

\begin{document}

\psol{5}{October 14, 1994}

\bigskip

\begin{problems}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problm 
Recall that the composition $(g\circ f)(x)$ of two functions is equal
to $g(f(x))$ for all~$x$.
\begin{problemparts}
\problempart
Show that if $f:A\to B$ and  $g:B\to C$ are both surjections, 
then $(g\circ f): A\to C$ is a surjection also.
%%%	SOLN	%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\pf 
Let $c\in C$.  Since $g$ is a surjection, there exists $b\in B$ such
that $g(b)=c$.  Also, $f$ is a surjection, so there exists $a\in A$ such
that $f(a)=b$.  Thus, $(g\circ f) (a) = g(f(a)) = g(b) =c$.
Therefore, $(g\circ f)$ is a surjection.
\end{proof}

\problempart
Show that if $f:A\to B$ and  $g:B\to C$ are both bijections, 
then $(g\circ f): A\to C$ is a bijection also.
%%%	SOLN	%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\pf 
Since $f$ and $g$ are bijections, they must be surjections.
From (a), we know that $(g\circ f)$ is a surjection.  Thus, it remains
for us to prove $(g\circ f)$ is an injection.

Suppose we have $(g\circ f) (a_1) = (g\circ f) (a_2)$.
Then, $g(f(a_1))=g(f(a_2))$.  Since $g$ is an injection,
it must be that $f(a_1)=f(a_2)$.  The function $f$ is also an injection,
so $a_1=a_2$.  Therefore, $(g\circ f)$ is an injection.  Thus, it is also
a bijection.
\end{proof}
\end{problemparts}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%	Tom's #2
\problm Let $f^{-1}$ be the inverse of a function~$f$.  Show that
$f^{-1}$ is unique.  Demonstrate that $f^{-1}$ also has an inverse.
%%%	SOLN	%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\pf
By contradiction.  Let $f:A\to B$.
Assume for contradiction that $f$ has two distinct inverses, $g_1$ and $g_2$, 
so there exists a $b\in B$ such that $g_1(b)\neq g_2(b)$.
Note that $f(g_1(b))=b$ and $f(g_2(b))=b$ by definition of inverse.  
But then $f$ is not an injection and hence cannot have an inverse,
contradicting the fact that it does.
Therefore, the inverse is unique.

The function $f$ is the inverse of $f^{-1}$.
Because $f^{-1}$ is the inverse of $f$, we already know by our definition
of inverse
that $f^{-1}(f(a))=a$ for all $a\in A$, and $f(f^{-1}(b))=b$ for all $b\in B$.
Thus, $f$ is the inverse of $f^{-1}$ also.
\end{proof}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%	Tom's #3
\problm Let $f:A\to B$ and $g:B\to A$ be functions such that for all
$a\in A$, $(g\circ f)(a)=a$.  Construct such an $f$, $g$, $A$, and $B$
such that $g$ is {\em not\/} the inverse of~$f$.  Is it necessary that
$f$ be injective?  surjective?  Explain your answers.

%%%	SOLN	%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\soln
We only need that $|A|<|B|$ and that $g$ inverts $f$ on the image of~$A$.
Thus, $f$ is not surjective; if it were, it would be a bijection
(since it must be an injection) and $g$ would be its inverse.
The fact that $(g\circ f)(a)=a$ implies that $f$ is injective:
if $f(a_1)=f(a_2)$ then $g(f(a_1))=g(f(a_2))$, and so $a_1=a_2$.

For example, let $f:\naturals \to \naturals$ such that $f(x)=2x$, and let
$g:\naturals \to \naturals$ such that $g(x)= \lfloor \frac{x}{2} \rfloor$
(recall that $\lfloor x \rfloor$ is the {\em floor} function).
Now for all $a\in A$, we have $(g\circ f)(a)= g(f(a))=g(2a)=a$.
But $f(g(1))=f(0)=0$, so $g$ is {\em not\/} the inverse of~$f$.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problm 
A \defi{clique} is a graph with edges between all pairs of vertices.
An \defi{independent set} is a graph with no edges.

%%%	SOLN	%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\thm
For any pair of positive integers $(k,\ell)$, 
there exists an $n$ such that every graph on $n$ nodes 
contains either a clique on $k$ nodes or an independent set on $\ell$ nodes. 
\end{theorem}
\pf
Let $m=k+\ell$ and prove by induction on $m$.
Let the inductive hypothesis $P(m)$ be that the the theorem holds for 
all positive integers $(k,\ell)$ such that $m=k+\ell$.

{\bf\sf Base Case:}  For $m=2$, it must be that $k=\ell=1$.
Take $n=1$.  There is only one graph possible on one node (it has no edges).
A single node is trivially both a clique and an independent set, so $n=1$
satisfies the theorem.

{\bf\sf Induction Step:}  Assuming $P(m)$, we will show $P(m+1)$.
Let $(k,\ell)$ be a pair of nonnegative integers such that
$k+\ell = m+1$.  We need to consider three cases.
\begin{enumerate}
\item\
$k=1$.  Then take $n=1$.  There is only one graph possible on one node
and it is trivially a clique.
\item\ 
$\ell=1$.  Then take $n=1$. There is only one graph possible on one node
and it is trivially an independent set.
\item\
$k>1$ and $\ell>1$.  
Consider the nonnegative pairs $(k-1,\ell)$ and $(k,\ell-1)$.  
Both of these pairs sum to $m$.  
By the inductive hypothesis, there exists an $n_1$ such that any graph of size
$n_1$ has either a $(k-1)$-clique or an $\ell$-independent set.
Similarly, there exists an $n_2$ for the pair $(k,\ell-1)$.  
Take $n=n_1+n_2+1$.  We will show that any graph on $n$ nodes has either a 
$k$-clique or an $\ell$-independent set.

Take any graph on $n$ nodes and consider a node~$v$.
Either $v$ has $n_1$ neighbors or there are $n_2$ nodes not adjacent to~$v$.

\begin{itemize}
\item\
If $v$ has $n_1$ neighbors, then by the inductive hypothesis, 
the subgraph on those nodes has either an $\ell$-independent set or
a $(k-1)$-clique.  A $(k-1)$-clique together with $v$ forms a $k$-clique.
So either way, we satisfy~$P(m+1)$.
\item \
Similar.
If there are $n_2$ nodes not adjacent to $v$, then by the inductive hypothesis,
the subgraph on these nodes either has a $k$-clique or 
an $(\ell-1)$-independent set which together with $v$ forms an 
$\ell$-independent set.
Either way, we satisfy~$P(m+1)$.
\end{itemize}
\end{enumerate}
This completes the inductive step.\\
By induction, the theorem is true.
\end{proof}

\bigskip\bigskip
\soln
The minimum value of $n$ is called the Ramsey number of $(k,\ell)$,
denoted $r(k,\ell)$.  Ramsey numbers are very difficult to calculate precisely.
In fact, the exact value of $r(5,5)$ is still not known!
We know only that $43\leq r(5,5)\leq 55$.\footnote{N. Alon and 
J. Spencer.  {\em The Probabilistic Method}.
John Wiley \& Sons, Inc., 1992.  pp. 241--242.}


\newpage
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%	Tom's #6
\problm 
Let $[n]$ denote the set $\{1,2,\ldots,n\}.$
Show that any subset of $[2n]$ with $n+1$ elements
contains two numbers that sum to $2n+1$.  
Show that any subset of $[4n]$ with $3n+1$ elements
contains four numbers that sum to $8n+2$.  
State and prove a general theorem along these lines.

%%%	SOLN	%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\soln
We will prove the following theorem.  The first two statements are 
special cases when $k=1$ and $k=2$.  (Notice that our theorem actually
gives a better bound for $k=2$:  $2n+2$ rather than $3n+1$.)
\thm
For any integer $k\geq 1$, any subset of $[2kn]$ with $kn+k$ elements
contains $2k$ numbers that sum to $2k^2n+k$.
\end{theorem}
\pf
Consider the following tabular listing of the numbers 1 to $2kn$ in a
snake-like order.
\[
\begin{array}{c c c c c c c}
1 & 2 & 3 & \cdots & kn-2 & kn-1 & kn \\
2kn & 2kn-1 & 2kn-2 & \cdots & kn+3 & kn+2 & kn+1
\end{array}
\]
There are $kn$ columns in this table. 
Any set of $kn+k$ numbers from $[2kn]$ must choose both numbers
from at least $k$ columns.
(Formally, this follows by repeated applications of the 
pigeonhole principle:  we must have two numbers that appear in the same
column, leaving $kn-1$ other columns and $kn+k-2$ other numbers. 
We can repeat this argument on the remaining columns and numbers 
as long as the numbers outnumber the columns.  Since the difference
between the numbers and the columns decreases by one at each step,
we can repeat for $k$ steps.)

Each column sums to $2kn+1$, so the sum over $k$ pairs each appearing
pairwise in the same columns is~$k(2kn+1)$.
\end{proof}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%	Tom's #7
\problm 
Prove that it is impossible to number the squares of a chessboard 
with the numbers 1 to 64 so that the numbers of every two adjacent squares
differ by 8 or less.  (``Adjacent'' includes diagonally adjacent.)

\pf
For any numbering, the square numbered 1 and the square numbered 64 
are at most 7 adjacent-square-hops away.  There must be two adjacent
squares along the way whose difference is at least $(64-1)/7 = 9$.
\end{proof}

\remove{

  Consider the squares numbered 1 and 64.
  Since the maximum distance between squares is seven, 
  we can move from the square numbered 1 to the square
   numbered 64 in seven moves.
  Suppose we start at the square number 1.  With each move, 
  we can increase the numbering by eight.  So, after seven moves,
  the maximum number on a square is $7\cdot 8+1 = 56<64$. Contradiction.
  Therefore, it is impossible to number the squares.
  \end{proof}
}

\newpage
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%	Tom's #8
\problem
Show that the set of all subsets of $\naturals$ is not countable.\\
%%%	SOLN	%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\soln
It is impossible to list the subsets of $\naturals$ as
$S_0,S_1,S_2,\ldots$ where every subset of $\nats$
appears as $S_i$ for some $i\in \nats$.
For any such listing you give me, 
I can construct an $S^*\subseteq\nats$ to differ from each $S_i$ by putting 
$i\in S$ iff $i\not\in S_i$.
Thus your list does not contain $S^*$: for all $i\in\nats$, $S^* \neq S_i$
because the two sets differ in their inclusion of~$i$.
This shows that any such listing must be incomplete.
\remove{
  Assume ${\cal P}(\naturals)$ is countable.
  Thus, there exists a bijection $f:\naturals\to {\cal P}(\naturals)$,
  or a listing $S_0, S_1, S_2, \ldots$ of all $S_i\subseteq \nats$ 
  where $S_i=f(i)$.
  Now construct $S^*$ to differ from each $S_i$ by putting 
  $i\in S$ iff $i\not\in S_i$: $S=\{n\in \naturals \mid n \notin f(n)\}$.  
  Now $S^*$ is an element of ${\cal P}(\naturals)$, 
  but$S^*$does not appear in the list: for all $i\in\nats$, $S^* \neq S_i=f(i)$
  because the two sets differ in their inclusion of~$i$.
  This contradicts the assumption that $f$ is a bijection, or that 
  ${\cal P}(\nats)$ is countable.
  Therefore, ${\cal P}(\naturals)$ is not countable.
}

\bigskip \rm
Show that the set of all finite subsets of $\naturals$ {\em is\/} countable.
%%%	SOLN	%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\soln
Construct a listing of the finite subsets as follows.
Begin the list with $\emptyset, \{ 0 \}$.
Now for each set $S$ on the list so far, add to the list $S \cup \{1\}$:
the list is now $\emptyset, \{ 0 \}, \{ 1 \}, \{ 0,1 \}$.
Now for each set $S$ on the list so far, add to the list $S \cup \{2\}$:
we add $\{2\}, \{0,2\}, \{1,2\}, \{0,1,2\}$ to the list.
Then for each set $S$ on the list so far, add to the list $S \cup \{3\}$,
and so on.  In stage $i$, we add to the list $S\cup\{i\}$ for every $S$ on the
list so far; the resulting list includes all subsets of $\{0,1,\ldots,i\}$.
Since any finite subset of $\nats$ has a greatest element $k$, it will appear
on our list at some point during stage~$k$.


\remove{
  {\bf Method 1:}
  \pf
  Recall from lecture that the prime numbers form a countable, infinite
  set.  Let $p:\naturals \to PRIMES$ be a bijection that takes
  $i\in\naturals$ to the $i$th prime number.
  Let $S$ denote the set of all finite subsets of $\naturals$.
  In addition, let $T=\{n\in\naturals | n \mbox{ is a product
  of distinct primes}\}$.
  We will show a bijection between $S$ and $T$.  For $s\in S$, define
  \[
  \displaystyle f(s)=\prod_{x\in s} p(x).
  \]
  Now, $f$ is a mapping from $S$ to $T$, since $s$ is finite.  Also,
  $f(s)$ is well-defined and a member of $T$.
  Because prime factorization is unique, $f$ is a injection.  Since
  $S$ contains all finite subsets of $\naturals$, $f$ is a surjection,
  and thus, a bijection.

  Since $T$ is an infinite subset of $\naturals$, we can draw a
  bijection $g:\naturals \to T$.  We can list the elements of $T$ in
  increasing order, and let $g(i)$ will be the $i$th element in the list.
  Thus, $(f^{-1}\circ g):\naturals \to S$ is a bijection by problem 5-1.
  Therefore, $S$ is countable.
  \end{proof}

  {\bf Method 2:}
}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%	Tom's #10
\problm 

%Let $S_n$ denote the set of all decimal strings of length
%$n$, and let $S=\displaystyle\bigcup_{n\in \nats} S_n$.  What is wrong
%with the following diagonalization argument that $S$ is not countable?
%\begin{quotation}
%If $S$ is countable, then we can write $S=\{s_1, s_2, s_3, \ldots\}$.
%Then, we can construct a decimal string $s^*$ by letting the $i$th
%digit of $s^*$ differ from the $i$th digit of $s_i$, for
%all~$i\in\nats$.  By construction, $s^*\not\in S$, which is a
%contradiction.  Hence, $S$ is not countable.
%\end{quotation}

%Prove that $S$ is in fact countable.

%%%	SOLN	%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\soln
In the diagonalization argument, we make the $i$th digit of $s^*$ differ
from the $i$th digit of $s_i$.  However, $s_i$ is a decimal
string of finite length, so it may not have an $i$th digit!
% Intiutively, if we list the elements in a table and examine the diagonal
% entries, the width of the table could be less than the height.
% Thus, the diagonal would not cut across all elements in the table.

In fact, we will show $S$ is countable.
$S_i$ is a finite set, since there are a finite number
of decimal strings of length $i$.  Therefore, we could
construct a mapping $f:\naturals\to S$ by listing the elements
of $S_0$, followed by $S_1$, followed by $S_2$, etc.
Since each $S_i$ is finite, we will eventually list every element in $S$.  
Therefore, we have our bijection, and $S$ is countable.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%	Tom's #11
\problm 
Determine whether each of the following statements about the asymptotic growth
of functions is true or false.  As usual, ``$\lg n$'' denotes $\log_2 n$.

\begin{tabular}{rllp{4in}}
{\bf (a)} & \mystrut
$\lg^5 n = o(n^{1/5})$ &
%%%	SOLN	%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\sf True.  & \sf Remember that for any $\epsilon,k>0$, 
$\frac{\lg^kn}{n^\epsilon} \longrightarrow 0$ as $n\rightarrow\infty$. 
\\
{\bf (b)} & \mystrut
$n^2 \sim 2^{\lg^2 n}$ &
%%%	SOLN	%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\sf False. & \sf $2^{\lg^2 n}=(2^{\lg n})^{\lg n}=n^{\lg n} = \omega(n^2)$.
\\
{\bf (c)} & \mystrut
$\lg n = \Theta (\log_{10} n)$ &
%%%	SOLN	%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\sf True.  &  \sf They are related by a constant: 
$\lg n = \left({1\over \log_{10} 2}\right) \log_{10} n$.
\\
{\bf (d)} & \mystrut
$2^{\lg n} = \Theta (2^{\log_{10} n})$ &
%%%	SOLN	%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\sf False.  &  \sf $2^{\lg n}=n$ while $2^{\log_{10} n}=2^{\lg n \log_{10} 2} 
= n^{0.301\ldots} = O(n^{.302})$. 
\\
{\bf (e)} & \mystrut
$(n^2+3n+1)^3\sim n^6$ &
%%%	SOLN	%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\soln
\sf True. & $(n^2+3n+1)^3 = n^6 +O(n^5)$.
\\
{\bf (f)} & \mystrut
$(\sqrt{n} +1)^3/(n^2+1) = o(1)$ &
%%%	SOLN	%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\sf True. &  \sf $(\sqrt{n} +1)^3 =\Theta(n^{3/2})$ and
$\Theta(n^{3/2})/(n^2+1) = o(1)$
\\
{\bf (g)} & \mystrut
$ e^{1/n} = \Theta(1) $ & 
%%%	SOLN	%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\sf True. &  \sf Clearly $1<e^{1/n}<e$ for $n>1$. 
\\
{\bf (h)} & \mystrut
$  n^3(\lg \lg n)^2 = o(n^3 \lg n) $ &
%%%	SOLN	%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\sf True. &  \sf Let $x=\lg n$.  Since $\lg^2 x = o(x)$, it follows

that $(\lg \lg n)^2 = o(\lg n)$.
\\
{\bf (i)} & \mystrut
$  \sqrt{1+\lg n } = \Omega(\lg \lg n)$ &
%%%	SOLN	%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\sf True.  &  \sf Again, let $x=\lg n$. Then, $\sqrt{1+x}=\Theta({x^{1/2}})$.

Recall $x^{1/2}=\Omega(\lg x)$. 
\\
{\bf (j)} & \mystrut
$ \sin(n) = \Omega(1) $ & 
%%%	SOLN	%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\sf False. &  \sf There are arbitrarily large $n$ such that $\sin (n) = 0$, and

so it cannot be that $\exists n_0,c>0 \; \forall n>n_0 \; |\sin (n)| > c$.
%	For any $c>0$ and $n_o$, it cannot be possible
%	that for all $n>n_o$ ,$|\sin(n)|>c$, since $\sin$ will
%	always cycle back to zero. 
\end{tabular}

\end{problems}

\end{document}
