\documentclass[12pt,twoside]{article}
\usepackage{amsmath}
\usepackage{graphics}
\input{macros-course}

\begin{document}
%\pset{7}{March 16, 1999}{Tuesday, March 30}
\psol{7}{April 2, 1999}

%\newcommand{\solution}[1]{}
\newcommand{\solution}[1]{\bigskip #1}

%\reading{Sections 1.6, 4.2, 5.1, and 5.2 in Rosen; also refer to the notes
%for Lectures 11 and 12 and to Tutorial 7.}

\begin{problems}

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

\problem {\bf (25 points) } Solve the following linear recurrences.

\begin{problemparts}

\problempart {\bf (5 points)}
\begin{eqnarray*}
T_0 & = & 0 \\ T_1 & = & 1 \\ T_n & = & 2 T_{n-1} + 3 T_{n-2} \quad
\quad \text{(for $n \geq 2$)}
\end{eqnarray*}

\solution{The characteristic equation is $r^2 - 2 r - 3 = 0$, which
has roots $r = -1$ and $r = 3$.  Therefore, the general form of the
solution is $T_n = A \cdot (-1)^n + B \cdot 3^n$.  Substituting the
base cases into this general form gives a system of equations:

\begin{eqnarray*}
0	& = &	A + B \\
1	& = &	-A + 3B
\end{eqnarray*}

The solution to this system is $A = -\frac{1}{4}$ and $B =
\frac{1}{4}$.  Therefore, the complete solution to the recurrence is

\begin{eqnarray*}
T_n & = & -\frac{1}{4} \cdot (-1)^n + \frac{1}{4} \cdot 3^n
\end{eqnarray*}
}

\problempart {\bf (10 points)}
\begin{eqnarray*}
T_0 & = & 0 \\
T_1 & = & 1 \\
T_n & = & 2 T_{n-1} + 3 T_{n-2} + n \quad \quad \text{(for $n \geq 2$)}
\end{eqnarray*}

\solution{The characteristic equation is the same as before.
Therefore, the general form of the homogeneous solution is still $T_n
= A \cdot (-1)^n + B \cdot 3^n$.  Let's first look for a particular
solution of the form $an + b$.

\begin{eqnarray*}
an+b	& = &	2(a(n-1)+b) + 3(a(n-2)+b) + n \\
	& = &	2an - 2a + 2b + 3an - 6a + 3b + n \\
\end{eqnarray*}

Equating linear terms gives $a = - \frac{1}{4}$ and equating constant
terms gives $b = - \frac{1}{2}$.  This suggests the particular
solution $- \frac{1}{4} n - \frac{1}{2}$, which we can verify by
substituting back into the recurrence.  The general form of the
complete solution is therefore $T_n = A \cdot (-1)^n + B \cdot 3^n -
\frac{1}{4} n - \frac{1}{2}$.  Substituting the base cases into this
general form gives a system of equations:

\begin{eqnarray*}
0	& = &	A + B - \frac{1}{2} \\
1	& = &	-A + 3B - \frac{3}{4}
\end{eqnarray*}

The solution to this system is $A = - \frac{1}{16}$ and $B =
\frac{9}{16}$.  Therefore, the complete solution to the recurrence is

\begin{eqnarray*}
T_n = - \frac{1}{16} \cdot (-1)^n + \frac{9}{16} \cdot 3^n - \frac{1}{4} n - \frac{1}{2}
\end{eqnarray*}
}

\problempart {\bf (10 points)}
\begin{eqnarray*}
T_0 & = & 0 \\
T_1 & = & 1 \\
T_2 & = & 2 \\
T_n & = & 2 T_{n-1} + 4 T_{n-2} - 8 T_{n-3} \quad \quad \text{(for $n \geq 3$)}
\end{eqnarray*}

\solution{The characteristic equation is $r^3 - 2 r^2 - 4 r + 8 = 0$,
which has a root at $r = -2$ and a double root at $r = 2$.  Therefore,
the general form of the solution is

\begin{eqnarray*}
T_n & = & A \cdot (-2)^n + B \cdot 2^n + C \cdot n 2^n.
\end{eqnarray*}

Substituting the base cases into this general form gives the following
system of equations.

\begin{eqnarray*}
0	& = &	A + B \\
1	& = &	-2A + 2B + 2C \\
2	& = &	4A + 4B + 8C
\end{eqnarray*}

The solution to this system of equation is $A = - \frac{1}{8}$, $B =
\frac{1}{8}$, and $C = \frac{1}{4}$.  Therefore, the complete solution
to the recurrence is

\begin{eqnarray*}
T_n & = & - \frac{1}{8} \cdot (-2)^n + \frac{1}{8} \cdot 2^n + \frac{1}{4} \cdot n 2^n.
\end{eqnarray*}
}

\end{problemparts}

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

\problem {\bf (10 points) } Suppose that the catch of lobsters each
year is the average of the catch for the last two years.  The catch in
year 0 was 1000 pounds and the catch in year 1 was 2500 pounds.

\begin{problemparts}
\problempart Express the catch of lobsters in year $n$ using
a recurrence relation and sufficient base cases.

\solution{
\begin{eqnarray*}
L_0 & = & 1000 \\
L_1 & = & 2500 \\
L_n & = & \frac{L_{n-1} + L_{n-2}}{2} \quad \quad (n \geq 2)
\end{eqnarray*}
}

\problempart Solve the recurrence to determine the catch in year $n$.

\solution{The characteristic equation is $2 r^2 - r - 1 = 0$.  This
equation has roots $r = 1$ and $r = - \frac{1}{2}$.  Thus, the
solution has the form

\begin{eqnarray*}
L_n	& = &	A \cdot 1^n + B \cdot \left(- \frac{1}{2} \right)^n.
\end{eqnarray*}

Substituting the base cases gives a system of linear equations:

\begin{eqnarray*}
1000	& = &	A + B \\
2500	& = &	A - \frac{1}{2} B
\end{eqnarray*}

Solving these equations gives $A = 2000$ and $B = -1000$.  Thus the
complete solutions is

\begin{eqnarray*}
L_n & = & 2000 - 1000 \cdot \left(- \frac{1}{2} \right)^n.
\end{eqnarray*}
}

\problempart What constant will the annual lobster catch approach in
the distant future?

\solution{
\begin{eqnarray*}
\lim_{n \rightarrow \infty} 2000 - 1000 \cdot \left(- \frac{1}{2} \right)^n
	& = &	2000 \text{ pounds per year}
\end{eqnarray*}
}

\end{problemparts}

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

\problem {\bf (15 points)} Below is a list of properties that a group
of people might possess.  For each property, either give the minimum
number of people that must be in a group to ensure that the property
holds, or else indicate that the property need not hold even for
arbitrarily large groups of people.  Assume that every year has
exactly 365 days; ignore leap years.  No proofs are required.

\begin{problemparts}
\problempart At least 2 people were born on the same day of the year.

\solution{This property holds for every group of 366 or more people.}

\problempart At least 2 people were born on January 1.

\solution{This property need not hold, even for arbitrarily large
groups of people.}

\problempart At least 3 people were born on the same day of the week.

\solution{
This property holds for every group of 15 or more people.
}

\problempart At least 4 people were born in the same month.

\solution{
This property holds for every group of 37 or more people.
}

\problempart At least 2 people were born exactly one week apart.

\solution{This property need not hold.  For example, everyone might be
born on the same day of the year.
}

\problempart At least 9 people were born on a weekend or at least 11
people were born during the week.

\solution{This property holds for every group of at least $(9-1) +
(11-1) + 1 = 19$ or more people.}

\problempart At least 2 people were born on the same day of the year or else
2 people were born exactly one week apart.

\solution{There are two interpretations of this question, which differ
on whether, say, people born on Dec 1 and Jan 6 were born a week
apart.  If such ``wraparound'' is considered, then the answer is 183
people.  If ``wraparound'' is ignored, then the answer is 184 people.
}

\end{problemparts}

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

\problem {\bf (10 points) } Let $D$ be the diamond-shaped region of the
real plane consisting of all points $(x, y)$ such that $|x| + |y| \leq
1$.
Prove that among every set of 5 points in $D$, there must exist two
distinct points that are at most unit distance apart.  \hint  Consider
the diagram below.

\bigskip
\centerline{\resizebox{2.0in}{!}{\includegraphics{diamond.eps}}}
\bigskip

\solution{The diagram for the preceding problem part shows that the
set $D$ can be partitioned into four smaller diamonds.  By the
pigeonhole principle, at least two of the five points must be
contained in the same small diamond.  These two points are distance at
most one apart.

(Note that boundary points can be assigned to smaller diamonds
arbitrarily.)
}

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

\problem {\bf (15 points) } Let $G$ be a simple, undirected graph with
a total of 100 vertices, all with even degree.  Prove that there
exists a set of three vertices, all with the same degree.

\solution{There are two cases.  First, suppose that there is a vertex
with degree 98.  Then there is at most one vertex with degree 0.  The
remaining 98 vertices must have degrees in the range $2, 4, \ldots,
96$, which includes 48 possibilities.  Therefore, by the pigeonhole
principle, there are at least three vertices with the same degree.

On the other hand, suppose that there is no vertex with degree 98.
Then all 100 vertices must have degrees in the range $0, 2, \ldots,
96$, which includes 49 possibilities.  Again, by the pigeonhole
principle, there must be at least three vertices with the same degree.
}

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

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

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\end{problems} \end{document}
