\documentstyle[12pt,twoside]{article}

\newcommand{\problem}{%
  \paragraph{Problem}}
\newcommand(\solution}{%
  \paragraph{Solution}}

\begin{document}


\begin{problems}

%BEGIN Kavita's problems
% Fall 1998


%**************
%   PSET 7    *
%**************

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

%  Largely stolen from Fall 97.

\problem {\bf (10 points)} For each of the functions below, determine
whether the function is injective, whether it is surjective, and
whether it is bijective.  No proofs are required.

\begin{problemparts}
\problempart The function $f : \mathbb{R} \mapsto \mathbb{R}$ defined by
$f(x)=e^x$

\solution{ The function is injective because $e^x = e^y$ if and only
if $x = y$.  The function is not surjective, because $e^x$ never takes
on non-positive values.  The function is not bijective, because it is
not surjective.  }

\problempart The function $f : \mathbb{R} \mapsto \mathbb{R}^+$
defined by $f(x)=e^x$.  (Here $\mathbb{R}^+$ denotes the set of
positive real numbers.)

\solution{The function is injective as before, but is now also surjective
because for every $y \in \mathbb{R}^+$, there exists an $x$ (namely $x
= \ln y$) such that $y = e^x$.  Therefore, the function is bijective.}

\problempart The function $f : \mathbb{R} \mapsto \mathbb{R}$ defined
by $(x+1)/(x^2+1)$

\solution{ The function is not injective, because $f(0) = f(1) = 1$.
The function is not surjective, because the function never takes on
large positive or negative values.  The function is not bijective
because it is neither injective nor surjective.}

\problempart The function $f : \mathbb{R} \mapsto \mathbb{R}$ defined
by

\begin{eqnarray*}
f(x) & = & \left\{
\begin{array}{cl}
1/x & \text{for $x \neq 0$} \\
0 & \text{for $x = 0$.}
\end{array}
\right.
\end{eqnarray*}

\solution{ The function is injective, because $f(x) = f(y)$ if and
only if $x = y$.  The function is surjective, because for all $y \in
\mathbb{R}$, there exists an $x$ (namely $x = 1 / y$ or $x = 0$) such
that $f(x) = y$.  Therefore, the function is also bijective.}

\end{problemparts}


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

\problem {\bf (10 points)} Suppose that $f$ is a function of the form
$f: A \mapsto B$, and $g$ is a function of the form $g: B \mapsto C$.
The composed function $g \circ f$ has domain $A$, range $C$, and is
defined by $(g \circ f)(a) = g(f(a))$.

\begin{problemparts}

\problempart Prove that if the composition $g \circ f$ is a bijection,
then $f$ is an injection and $g$ is a surjection.

\solution{
\begin{proof}
Suppose that $g \circ f$ is a bijection.

Assume for the purpose of contradiction that $f$ is not an injection.
Then there exist elements $a_1, a_2 \in A$, such that $f(a_1) =
f(a_2)$.  This implies that $g(f(a_1)) = g(f(a_2))$.  Therefore, $g
\circ f$ is not an injection and thus not a bijection.  This is a
contradiction; therefore, $f$ must be an injection.

Now assume for the purpose of contradiction that $g$ is not a
surjection.  Then there exists an element $c \in C$ such that for all
$b \in B$, $g(b) \neq c$.  Therefore, for all $a \in A$, $g(f(a)) \neq
c$.  This implies that $g \circ f$ is not a surjection and thus not a
bijection.  This is again a contradiction; therefore, $g$ must be a
surjection.
\end{proof}
}

\problempart If $f$ is an injection and $g$ is a surjection, then is
$g \circ f$ necessarily a bijection?

\solution{
No.  For example, consider the following setup.

\begin{eqnarray*}
A & = & \{ 1 \} \\
B & = & \{ 1, 2 \} \\
C & = & \{ 1, 2 \} \\
\\
f(x) & = & x \\
g(x) & = & x
\end{eqnarray*}

In this case, $f$ is injective, $g$ is surjective, but $g \circ f$ is
not bijective.  }

\end{problemparts}

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

%END   Kavita's problems

%BEGIN Joe's problems
%END   Joe's problems

%BEGIN Ray's problems

%%%%%%%%  S99 ps5


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

\problem {\bf (20 points)} In analyzing algorithms, one often must
determine the asymptotic behavior of nasty functions like those
shown below.

\[
\begin{array}{ccc}
\iffalse \hspace{2cm} & n^{10} - n^{9} &\hspace{2cm} \fi
n! & (\ln n)^{300} & 2 n^{\ln \ln n}  \\
\iffalse  & \sum_{i=0}^n \sqrt{i}\fi
n^n & n (\ln n)^{4} & n^{1.01}/2 \\
7 n^2 + 3 & \sqrt{n}^{\sqrt{n}} & 4^n \\
\iffalse  & \frac{(2n)!}{n! \ n!}\fi
(n/e)^n & (7n^3 - 17n^2)/(n + 128) & (\ln n)^{\ln n}
\end{array}
\]

Arrange these functions in a list so that each is $\Theta$ or $O$ of
the next function in the list.  For each pair of consecutive functions
in your list, indicate whether the stonger $\Theta$ relationship holds
or only the weaker $O$ relationship.  No proofs are required.

\solution{
\begin{eqnarray*}
(\ln n)^{300}		& = & O\left(n (\ln n)^{4}\right) \\
n (\ln n)^{4}		& = & O\left(\frac{1}{2} n^{1.01}\right) \\
\frac{1}{2} n^{1.01}	& = & O\left(7 n^2 + 3\right) \\
7 n^2 + 3		& = & \Theta\left(\frac{7n^3 - 17n^2}
					{n + 128}\right) \\
\frac{8n^3 - 17n^2}
	{n + 128}	& = & O\left((\ln n)^{\ln n}\right) \\
(\ln n)^{\ln n}		& = & \Theta\left(2 n^{\ln \ln n}\right) \\
2 n^{\ln \ln n}		& = & O\left(\sqrt{n}^{\sqrt{n}}\right) \\
\sqrt{n}^{\sqrt{n}}	& = & O\left(4^n\right) \\
4^n			& = & O\left(\left(\frac{n}{e}\right)^n\right) \\
\left(\frac{n}{e}\right)^n
			& = & O\left(n!\right) \\
n!			& = & O\left(n^n\right)
\end{eqnarray*}
}




%%%%%%%%%%%%%%%%%%%%%% S99 ps7


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

\problem {\bf (10 points)} Let $A$, $B$, and $C$ be finite sets.  Let
$f$ be a function mapping $A$ to $B$, $g$ be a function mapping $B$ to
$C$, and $h$ be a function mapping $C$ to $A$.  No proofs are required
for this problem.

\begin{problemparts}

\problempart Suppose that $h(g(f(a))) = a$ for all $a$ in $A$.  Which
functions must be injective and which must be surjective?

\solution{The function $f$ must be injective, and the function $h$
must be surjective.}

\problempart Suppose also that $|A| = |C|$.  Now which functions must
be injective and which must be surjective?

\solution{The functions $f$ and $h$ must be injective, and the
functions $g$ and $h$ must be surjective.}

\problempart Suppose also that $f$ is invertible.  Now which functions
must be injective and which must be surjective?

\solution{All of the functions must be both injective and surjective.}

\end{problemparts}

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

\problem {\bf (15 points)} Recall that in the game Lights Out there is
an $m \times n$ grid of squares, each of which is lit or unlit.
Pressing a square switches the light on that square and on all squares
that share an edge with the one pressed.  The solution to this
(solitary) game is a subset of squares s.t. if initially all lights on
the grid are lit then pressing all squares in this subset will turn
all the lights on the grid off.

Note that pressing a sequence of squares has the same effect as
pressing the same squares in any other order.  Also, note that
pressing a square twice has the same effect as not pressing it at all.
Therefore, if a configuration of lights can be reached at all, then it
can be reached by pressing some set of squares in an arbitrary order.

In this problem we want you to think about the function $f_{m,n}$ that
maps each subset of the squares in an $m \times n$ grid to the subset
of lights that are switched if those squares are pressed.  For
example, let's look at the value of function $f_{2,3}$ on argument
$A$, a particular subset of squares in the $2\times{3}$ grid:
\[
A=
\begin{array}{|c|c|c|}
\hline
x&\hspace{1ex}&\hspace{1ex}\\ \hline
&x&\\ \hline
\end{array}
\]
Then $B=f_{2,3}(A)$ is the following subset of lights:
\[
B=f_{2,3}(A)=
\begin{array}{|c|c|c|}
\hline
x&\hspace{1ex}&\hspace{1ex}\\ \hline
&x&x\\ \hline
\end{array}
\]

Include a brief explanation with your answers to the following
questions:

\begin{problemparts}
\problempart First, consider the function $f_{3,3}$.  Recall that for
a $3 \times 3$ grid, every configuration of lights can be reached from
the initial state where all lights are on.  Is this function
injective?  Is it surjective?

\solution{The function is surjective, since every configuration of
lights can be achieved by pressing some set of squares.  The domain
has size $2^9$, since every square is either pressed or not pressed.
The range also has size $2^9$, since every square is lit or unlit.
Therefore, the function is also injective.}

\problempart Is the function $f_{2,3}$ injective?  Is it surjective?

\solution{Pressing the set of squares indicated below has the same
effect as pressing no squares at all.  Consequently, the function is
not injective.  Since the domain and range again have the same size
(now $2^6$), the function can not be surjective.

\[
\begin{array}{|c|c|c|}
\hline
x&\hspace{1ex}&x\\ \hline
x& &x\\ \hline
\end{array}
\]
}

\problempart A solution to the $5 \times 5$ version of Lights Out is
shown below; if the marked squares are pressed, then all lights are
switched.

\[
\begin{array}{|c|c|c|c|c|}
\hline
x& &x&x& \\ \hline
 &x&x&x& \\ \hline
x&x&x& & \\ \hline
x&x& &x&x\\ \hline
 & & &x&x\\ \hline
\end{array}
\]

Is the function $f_{5,5}$ injective?  Is it surjective?

\solution{Three more solutions can be obtained by rotation.
Therefore, the function is not injective.  Since the domain and range
are the same size (now $2^{25}$), the function is not surjective
either.}

\end{problemparts}


%%%%%%%%%%%%%%%%%%%%% S99 ps8

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

\problem {\bf (10 Points)}

In this problem, we will have to be careful about the technical
distinction between the \emph{range} and the \emph{codomain} of a
function.

If $D$ and $C$ are sets, the notation $f:D \to C$ indicates that $f$ is a
total function with \emph{domain} $D$ and \emph{codomain} $C$.  This means
that for every element, $d$, of the domain, $D$, there is a unique
element, denoted $f(d)$, in the codomain, $C$, that is determined by $f$.
The \emph{range of $f$} is the set of values actually taken by $f$, namely
\[
\mbox{range}(f) :: = \set{d \mid \exists c \in C :\ d = f(c)}.
\]
It follows that the range of a function is in general just a \emph{subset}
of its codomain, and equals the codomain precisely when the function is a
surjection.

Now let $\{0,1\}^n$ be the set of all bit strings of length $n$.

\bparts

\ppart

How many functions are there with domain $\{0,1\}^m$ and codomain
$\{0,1\}^n$?


\solution{There are $2^m$ elements in the domain.  There are $2^n$
elements in the codomain.  For every element in the domain, we thus have
$2^n$ choices for what we can map it to.  Therefore, by the product rule,
there are $(2^n)^{2^m}$ possible functions with domain $\{0,1\}^m$ and
codomain $\{0,1\}^n$.}

\ppart


How many functions with domain and codomain $\{0,1\}^n$ are {\em not
bijections}?

\solution{There are $2^n$ elements in both the domain and codomain.  Hence
there are a total of $(2^n)^{2^n}$ functions.  When the domain and
codomain coincide as in this case, the bijections are precisely the same
as permutations of the domain.  We know that there are $(2^n)!$ of these
permutations.  Hence the remaining are not bijections.  The total number
of functions with domain and codomain $\{0,1\}^n$ that are not bijections
is therefore $(2^n)^{2^n} - (2^n)!$.}

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

\solution{We have $2^n$ elements in the domain, and each of them can
possibly be mapped to $2^n - 1$ elements in the codomain---to any element
but itself.  Therefore, there are $(2^n-1)^{2^n}$ such functions with no
fixed points.}

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

\solution{There are $(2^n)^{2^n}$ functions, and $(2^n-1)^{2^n}$ have no
fixed points.  Therefore, the remaining $(2^n)^{2^n} - (2^n-1)^{2^n}$ have
at least one fixed point.}

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

\solution{Let's fix a particular point for our fixed point.  Now let's
consider where the remaining $2^n - 1$ points can be mapped.  Each one can
be mapped to any spot but itself---thus it can be mapped to exactly $2^n
- 1$ possible spots.  So there are $(2^n - 1)^{2^n - 1}$ functions with
exactly this particular fixed point and no other.  Now there are $2^n$
possible choices for the particular fixed point, so the total number of
functions with exactly one fixed point is $2^n(2^n - 1)^{2^n - 1}$.}

\eparts



%END   Ray's problems

%BEGIN Ivan's problems (spring '98)
%END   Ivan's problems

%BEGIN George's problems
%END   George's problems

%BEGIN Josh's problems
%END   Josh's problems

%BEGIN Tina's problems
%END   Tina's problems


\end{problems}

\end{document}



