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

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

\begin{document}

\pset{5}{October 6, 1994}{In recitation, October 14}

{\bf Reading:\ }  Chapter 2 from [CLR] (Handout~\ref{clrchap2}) and
[MR] Sections 0.3 and 0.4.

\bigskip\medskip

\begin{problems}

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

\end{problemparts}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%	Tom's #2
\problem Let $f^{-1}$ be the inverse of a function~$f$.  Show that
$f^{-1}$ is unique.  Demonstrate that $f^{-1}$ also has an inverse.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%	Tom's #4
%%	\problem Let $A$ be a finite set, and let $B$ be a set such that
%%	$|A|=|B|$.  Prove that there is a bijection from $A$ to~$B$.
%%
%%	Objection(CEL):  What is our definition of cardinality?
%%		In set theory, existence of bijection *is* the definition.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%	Tom's #3
\problem 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.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem 
A \defi{clique} is a graph with edges between all pairs of vertices.
An \defi{independent set} is a graph with no edges.
Recall from the last problem set ({\bf 4-8(b)}), that any graph on
6 nodes contains (as an induced subgraph) either a clique on 3 nodes 
or an independent set on 3 nodes, which can be proved by a case
analysis as follows.

Fix a node $v$ and consider two cases.  (1) If $v$ has at least 3
neighbors, then if any pair of those neighbors has an edge between
them, they form a clique with $v$.  If no pair has an edge between
them, then the neighbors form an independent set themselves.  (2) If
$v$ has fewer than 3 neighbors, then there are at least 3 nodes not
adjacent to $v$.  If any pair of them is not adjacent, they form an
independent set with $v$.  If each pair is adjacent, they form a
clique themselves.

Generalize this theorem by proving that for any pair of nonnegative
integers $(k,\ell)$, there exists an $n$ such that every graph on $n$
nodes contains (as an induced subgraph) either a clique on $k$ nodes
or an independent set on $\ell$ nodes.  (\hint Do this by
induction: prove that it is true for $(k,\ell)$ by assuming it is true for
$(k-1,\ell)$ and $(k,\ell-1)$.)
%%	Ramsey Theorem:
%%  	A good written problem would be to prove Ramsey's general theorem
%% 	that for any (k,l), there is some n s.t. any graph on n nodes has
%%	either a k-clique or an l-ind.set.
%%	Do this by induction--assume true for (k-1,l) and (k,l-1).

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%	Tom's #5	DONE IN CLASS (EFFECTIVELY)
%% \problem 
%% Prove that in any undirected graph there are two nodes with the same degree.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%	Tom's #6
\problem 
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.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%	Tom's #7
\problem 
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.)

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%	Tom's #8
\problem
%\begin{problemparts}
%\problempart
Show that the set of all subsets of $\naturals$ is not countable.\\
%\problempart
Show that the set of all finite subsets of $\naturals$ {\em is\/} countable.
%\end{problemparts}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%	Tom's #10
\problem 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.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%	Tom's #11
\problem 
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{problemparts}
\problempart
$\lg^5 n = o(n^{1/5})$
\problempart
$n^2 \sim 2^{\lg^2 n}$
\problempart
$\lg n = \Theta (\log_{10} n)$
\problempart
$2^{\lg n} = \Theta (2^{\log_{10} n})$
\problempart
$(n^2+3n+1)^3\sim n^6$
\problempart
$\displaystyle{(\sqrt{n} +1)^3\over(n^2+1)} = o(1)$
\problempart
$ e^{1/n} = \Theta(1) $
\problempart
$  n^3(\lg \lg n)^2 = o(n^3 \lg n) $
\problempart
$  \sqrt{1+\lg n } = \Omega(\lg \lg n)$
\problempart
$ \sin(n) = \Omega(1) $
\end{problemparts}


\end{problems}

\end{document}
