\documentclass[11pt, twoside]{article}
\input{macros-course}
\usepackage{graphicx}
\renewcommand{\implies}{\longrightarrow}
\newcommand{\from}{:}
\newcommand{\ignore}[1]{}
\askaboutsolutions
\begin{document}
\pset{6}{March 20, 2001}{2:35pm in lecture, April 3, 2001}

\textbf{Be sure to indicate your TA's name clearly on the solutions
you turn in}.

\paragraph{Reading}
Velleman, \textit{How to Prove It}, Chapter 5.
Rosen, \textit{Discrete Mathematics and Its Applications},
Section 4.2 and Sections 5.1--5.3.


\paragraph{Policy on collaboration}
If you collaborated with someone on the problem sets, you should
mention their names on top of the problem set. If you did not
collaborate with anyone, you should explicitly say so. As a reminder,
the write-up of your solutions should be entirely your own.

\paragraph{Self-study}
Rosen, \emph{Discrete Mathematics and Its Applications}, Section 4.1.

The following exercises are \emph{optional;} do them if you think you
need the practice. The mini-quiz in tutorial on Friday will draw
(only) from these problems.

Exercises from Rosen (answers in the back of the book): Section 4.1:
1, 3; Section 5.1: 1, 3; Section 5.2: 1.
%Section 1.7:
%5, 8, 9.  Section 1.8: 7, 13, 14, 21
%??????


\medskip
\begin{problems} 

\problem \goals{closed-forms}
In this problem we will estimate the \emph{average} number of
divisors a ``typical'' number has.  More precisely, let $a(n)$ denote
the average number of divisors of the numbers from $1$ to $n$.
\begin{problemparts}
\ppart\points{2} Let $f_{ij}=1$ if $i \mid j$, and 0 otherwise.  Explain why
\begin{displaymath}
  a(n) = \frac{1}{n} \sum_{j=1}^n \sum_{i=1}^n f_{ij}
\end{displaymath}

\solution{\textbf{Solution:} For a fixed~$j$, $\sum_{i=1}^n f_{ij}$ is
  the number of divisors of~$j$.}

\ppart\points{3} For a given~$i$, what is the value of $\sum_{j=1}^n f_{ij}$?

\solution{\textbf{Solution:} $\lfloor n/i \rfloor$.}

\ppart\points{5} Give a closed form estimate of $a(n)$ that is accurate to
within plus or minus 2 for any~$n$.

\solution{\textbf{Solution:} By the solution above,
  \begin{displaymath}
    a(n) =
    \frac{1}{n} \sum_{j=1}^n \sum_{i=1}^n f_{ij} =
    \frac{1}{n} \sum_{i=1}^n \sum_{j=1}^n f_{ij} =
    \sum_{i=1}^n \frac{\lfloor n/i \rfloor}{n}\,.
  \end{displaymath}
  Since
  \begin{displaymath}
    \frac{n-i}{i} \leq \biggl\lfloor\frac{n}{i}\biggr\rfloor \leq 
    \frac{n}{i}\,
  \end{displaymath}
  we obtain the bound
  \begin{displaymath}
    \sum_{i=1}^n \biggl(\frac{1}{i} - \frac{1}{n}\biggr) \leq
    a(n) \leq
    \sum_{i=1}^n \frac{1}{i}\,,
  \end{displaymath}
  or, equivalently, $H_n - 1 \leq a(n) \leq H_n$, where $H(n)$~denotes
  the $n$th harmonic number. From the lecture notes, we now the bound
  $\ln(n+1) \leq H_n \leq \ln n + 1$. Combining these bounds, we obtain
  \begin{displaymath}
    \ln(n+1) - 1 \leq a(n) \leq \ln n + 1.
  \end{displaymath}
}

\end{problemparts}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Pigeonhole Principle
% from Spring 99 pset 7
\problem \goals{counting}
\points{10} 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 31 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}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%Pigeonhole Principle
%from pset7 spring99
\problem \goals{proofs}
\points{10} 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{figures/ps6-diamond}}}
\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.)
}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%injective/surjective/bijective functions
%from pset7 fall 98  (Largely stolen from Fall 97)
\problem \goals{counting}
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\points{2.5} 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\points{2.5} 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\points{2.5} 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\points{2.5} 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}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%Linear homogenous recurrences
%from fall98 pset6
\problem \goals{closed-forms}
Find closed-form solutions to the following
linear recurrences.

\begin{problemparts}
\problempart\points{5} $x_{n} = 5 x_{n-1} - 6 x_{n-2} \quad (x_0 = 0, x_1 = 1)$

\solution{ The characteristic equation is $r^2 - 5 r + 6 = 0$.  The
roots can be found with the quadratic formula:

\begin{eqnarray*}
r_1 & = & 2 \\
r_2 & = & 3
\end{eqnarray*}

This implies a solution of the form

\begin{eqnarray*}
x_n & = & A 2^n + B 3^n.
\end{eqnarray*}

Substituting the initial conditions into this general form gives a
system of linear equations:

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

The solution to this system is $A = -1$ and $B = 1$.  Therefore, the
final solution to the recurrence is

\begin{eqnarray*}
x_n & = & 3^n - 2^n.
\end{eqnarray*}
}

\problempart\points{5} $x_{n} = 3x_{n-1} - 2 x_{n-2} + n \quad (x_0 = 0, x_1 = 1)$

\solution{
First, we find the general solution to the homogenous recurrence.  The
characteristic equation is $r^2 - 3r + 2 = 0$.  The roots of this
equation are $r_1 = 1$ and $r_2 = 2$.  Therefore, the general solution
to the homogenous recurrence is

\begin{eqnarray*}
x_n & = & A + B 2^n.
\end{eqnarray*}

Now we must find a particular solution to the recurrence, ignoring the
boundary conditions.  Since the inhomogenous term is linear, we guess
a solution that is quadratic:

\begin{eqnarray*}
an^2+bn+c       & = &   3(a(n-1)^2+b(n-1)+c) - 2(a(n-2)^2+b(n-2)+c) + n \\
                & = &   an^2+2an-5a+bn+b+c+n \\
0               & = &   2an - 5a + b + n
\end{eqnarray*}

This equation is solved by setting $a = -\frac{1}{2}$ and $b =
-\frac{5}{2}$.  Apparently, any value of $c$ gives a valid particular
solution; for simplicity, we choose $c = 0$.  Therefore, the
particular solution is:

\begin{eqnarray*}
x_n     & = &   -\frac{1}{2}n^2 - \frac{5}{2} n
\end{eqnarray*}

The complete solution to the recurrence is the homogenous solution
plus the particular solution:

\begin{eqnarray*}
x_n     & = &   A + B 2^n -\frac{1}{2}n^2 - \frac{5}{2} n
\end{eqnarray*}

Substituting the initial conditions gives a system of linear
equations:

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

The solution to this linear system is $A = -4$ and $B = 4$.
Therefore, the complete solution to the recurrence is

\begin{eqnarray*}
x_n     & = &   2^{n+2} -\frac{1}{2}n^2 - \frac{5}{2} n - 4.
\end{eqnarray*}
}

\end{problemparts}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%Recurrences
%from spring99 pset7
\problem \goals{closed-forms}
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\points{3} 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\points{5} 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\points{2} 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}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Multiple Linear Recurrences
% pset 7, #6
\problem \goals{closed-forms}
On a certain far away island, all men are either blond or
brown-haired. Studies show that each man has four sons. Every blond
father has exactly three blond sons, while every brown-haired man
has exactly two brown-haired sons.

\begin{problemparts}
\problempart\points{2} Let $a_n$ and $b_n$ denote the number of blond and
brown-haired men, respectively, in the $n$th generation. Write a
system of recurrences for $a_n$ and $b_n$.

\solution{
\begin{equation*}
\begin{split}
a_n &= 3 a_{n-1} + 2 b_{n-1},\\
b_n &= a_{n-1} + 2 b_{n-1}.
\end{split}
\end{equation*}
}

\problempart\points{3} For which values of $c\ne 0$ and $d$ will we have a
solution of the form $a_n = c^n$, $b_n = d c^n$?

\solution{ Assume $a_n = c^n$ and $b_n = d c^n$ for some $c\ne 0$
and $d$. Let's substitute this into the system of recurrences.
We will obtain the equations
\begin{align*}
c^n &= 3 c^{n-1} + 2 d c^{n-1},\\
d c^n &= c^{n-1} + 2 d c^{n-1}.
\end{align*}
Dividing out $c^{n-1}$ (which is allowed, since $c\ne 0$), we
obtain
\begin{equation}
\label{eq:de}
\begin{split}
c &= 3 + 2 d,\\
d c &= 1 + 2 d.
\end{split}
\end{equation}
Multiplying both sides of the first equation by $d$ and
subtracting the second equation, we obtain
\begin{equation*}
0 = 3 d + 2 d^2 - 1 - 2d = 2 d^2 + d - 1.
\end{equation*}
Solving the quadratic equation, we obtain $d \in \{-1,
\frac{1}{2}\}$. Substituting into~\eqref{eq:de}, we obtain the
solutions
\begin{alignat*}{2}
c &= 1, \quad &d &= -1;\\
c &= 4, \quad &d &= \frac{1}{2}.
\end{alignat*}
}


\problempart\points{3} Show that there exist values for $c_1$, $c_2$, $d_1$,
and $d_2$ such that
\begin{equation*}
\begin{split}
a_n &= x c_1^n + y c_2^n,\\
b_n &= x d_1 c_1^n + y d_2 c_2^n,
\end{split}
\end{equation*}
is a solution for all $x$ and $y$.

\solution{ Let $c_1 = 1$, $d_1 = -1$, $c_2 = 4$, $d_2 =
\frac{1}{2}$ (i.e., the two pairs of $c$ and $d$ that were
obtained in part~(a)).  From part~(a) we know that $a_n =
c_i^n$, $b_n = d_i c_i^n$ is a solution to the recurrences, for
each $i\in \{1, 2\}$. It is easy to verify that a constant
multiple of a solution is a solution, and that a sum of two
solutions is a solution.  }

%     \problempart Let $c_1$, $c_2$, $d_1$, and $d_2$ be the values you
%     obtained in part~(b). Show that every solution to the system of
%     recurrences~\eqref{eq:sys} can be written in the form
%     of~\eqref{eq:sol} for some $x$ and $y$.
%
%     \solution{Show that $x$ and $y$ can be found for any initial
%       conditions. Then use induction to show that two solutions with the
%       same initial conditions are equal everywhere.}


\problempart\points{2} Suppose in the first generation there were ten blond
and twenty brown-haired men on the island. How many of each
group will there be in the $n$th generation?

\solution{We have $a_1 = 10$, $b_1 = 20$. Let's find $x$ and $y$
such that a solution in the form of part~(d) would satisfy these
initial conditions. We have
\begin{align*}
10 &= x \cdot 1^1 + y \cdot 4^1,\\
20 &= x \cdot (-1) \cdot 1^1 + y \cdot \frac{1}{2} \cdot 4^1,
\end{align*}
which can be rewritten as
\begin{align*}
10 &= x + 4 y,\\
20 &= -x + 2 y.
\end{align*}
This gives $x = -10$ and $y = 5$.

Thus the solution is
\begin{align*}
a_n &= -10 + 5 \cdot 4^n,\\
b_n &= 10 + \frac{5}{2} \cdot 4^n.
\end{align*}
}
\end{problemparts}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% sur/in/bijection
% from fall98 pset7
\problem \goals{proofs, counting}
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\points{7} 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\points{3} 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{problems}
\end{document}
