\documentclass[11pt, twoside]{article}

\usepackage{graphics}
\usepackage{psfig}

\input{macros-course}

%\newcommand{\nand}{|}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Printing the page layout parameters

\printlayout

\askaboutsolutions

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

\ifshowsolutions
  \newcommand{\reading}[1]{}
%
  \newcommand{\handoutlabel}{sol6}
  \newcommand{\handouttitle}{Problem Set 6 Solutions}
  \newcommand{\handoutdate}{March 30, 2000}
  \newcommand{\collaboration}{}
  \newcommand{\titlebar}{\handout{\handoutlabel}{\handouttitle}{\handoutdate}}
%
\else 
  \newcommand{\reading}[1]{%
%    \mbox{}\\ %
    \hrule\mbox{} \\ %\bigskip %
    #1%
%    \mbox{} \\ %\bigskip %
    \hrule %
    %\vfill\mbox{}\newpage%
    }
%
  \newcommand{\handoutlabel}{ps6}
  \newcommand{\handouttitle}{Problem Set 6}
  \newcommand{\handoutdate}{March 14, 2000}
  \newcommand{\duedate}{March 28, 2000}
  \newcommand{\collaboration}{\collaborationnote}
  \newcommand{\titlebar}{%
    \handout{\handoutlabel}{\handouttitle}{\handoutdate}
    \centerline{{\bf Due  Date: \duedate.}}
    \vspace*{\baselineskip}}
%
\fi

\renewcommand{\solution}[1]{%
  \ifshowsolutions %
  \textbf{Solution.} \par %
  #1
  \mbox{} \\
  \mbox{}\hrulefill\hspace*{1ex}\ignorespaces%
  \raisebox{-0.25\baselineskip}{$\square$}%
  \hspace*{1ex}\ignorespaces\hrulefill%
  \nopagebreak%
  \fi}


%\newcommand{\solutionname}{Solution}
%\renewenvironment{solution}[1][\solutionname]{%
%  \par
%  \normalfont
%  \topsep6\p@\@plus6\p@ \trivlist
%  \item[\hskip\labelsep\bfseries
%    #1\@addpunct{.}]~~\ignorespaces
%}{%
%\mbox{} \\
%\mbox{}\hrulefill\hspace*{1ex}\ignorespaces%
%\raisebox{-0.25\baselineskip}{$\square$}%
%\hspace*{1ex}\ignorespaces\hrulefill%
%\nopagebreak%
%}

%\renewcommand{\solution}[1]{%
%  %\begin{solution}
%    #1
%  %\end{solution}
%  }

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

\begin{document}

\titlebar

\reading{%
  \vspace{-2\baselineskip}
  \begin{description}\itemsep 0\baselineskip
  \item[Self-study:] \mbox{} \\
    Rosen, Section 1.8, on the growth of functions. \\
    Self-study problems: 3,7,9,11,13,15,17,19,23,31
    
  \item[Reading:] \mbox{} \\[-\baselineskip]
    \vspace*{-0.5\baselineskip}
    \begin{description}\itemsep 0\baselineskip
    \item[Rosen:] Sections 5.1, 5.2, 5.3, 4.1, 4.2
    \item[6.042 Fall 97 Lecture notes (available from course webpage):] %
      Lectures 9--12
    \end{description}
  \end{description}
  }

\section*{Problems:}

\begin{problems}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem %
Determine the flaw in the following reasoning and explain your answer.

\[
\left( \sum_{j=1}^n a_j \right) \left( \sum_{k=1}^n 1/a_k \right) =
\sum_{j=1}^n \sum_{k=1}^n a_j/a_k =
\sum_{k=1}^n \sum_{k=1}^n a_k/a_k =
\sum_{k=1}^n \sum_{k=1}^n 1 =
\sum_{k=1}^n n = n^2
\]

\solution{%
  not done yet!
  }

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem 
% problem 2, problem set 6, fall 1996

Find a closed-form expression for the summation
$\displaystyle\sum_{i=1}^n{i^2x^i}$.% and prove your answer is correct.

\solution{%
  %\begin{solution}
    We first come up with a formula for ${\displaystyle \sum_{i=1}^n
      i^2x^i}$ and then prove it using induction. From class notes we
    know that:
    
    \[{\displaystyle \sum_{i=1}^n ix^i} = \frac{x - (n+1)x^{n+1} + nx^{n+2}}{(1-x)^2}.\] 

    Differentiating (with respect to $x$) the above expression and
    multiplying with $x$ we find that

    \[{\displaystyle \sum_{i=1}^n i^2x^i} = \frac{x+x^2-(n+1)^2x^{n+1}+(2n^2+2n-1)x^{n+2}-n^2x^{n+3}}{(1-x)^3}\]

    We prove that the above closed-form expression for the summation
    is correct by induction on the upper bound $n$ of the summation.
    In particular, let $P(n)$ be the predicate that:

    \[{\displaystyle \sum_{i=1}^n i^2x^i} = \frac{x+x^2-(n+1)^2x^{n+1}+(2n^2+2n-1)x^{n+2}-n^2x^{n+3}}{(1-x)^3}.\]

    Base Case. $P(1)$ is true since

    \[{\displaystyle \sum_{i=1}^1 i^2x^i} = x = \frac{x+x^2-4x^2+3x^3-x^4}{(1-x)^3}.\]

    Inductive Step. Assume $P(n)$ is true. Then
    \begin{eqnarray*}
      {\displaystyle \sum_{i=1}^n i^2x^i} + (n+1)^2x^{n+1} & = & \\
      {\displaystyle \sum_{i=1}^{n+1} i^2x^i} & = & \frac{x+x^2-(n+1)^2x^{n+1}+(2n^2+2n-1)x^{n+2}-n^2x^{n+3}}{(1-x)^3} + (n+1)^2x^{n+1} \\
      & = & \frac{x+x^2-(n+2)^2x^{n+2}+(2(n+1)^2+2(n+1)-1)x^{n+3}-(n+1)^2x^{n+4}}{(1-x)^3}
    \end{eqnarray*}

    Thus $P(n+1)$ is true. Hence, $P(n)$ is true for all $n$.
  %\end{solution}
  }

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem
% problem 3, problem set 6, fall 1996
% similar to CLR 3.2-1

Show that $\sum_{k=1}^{\infty}{1/k^{3/2}}$ is bounded above by a constant.

\solution{%
  %\begin{solution}
    We use the integral method for bounding the infinite sum. Since
    $f(k)=\frac{1}{k^{3/2}}$ is monotonically decreasing for $k>1$, we
    have:
    \begin{eqnarray*}
      \sum_{k=1}^\infty{1/{k^{3/2}}} &=& 1 + \sum_{k=2}^\infty{1/{k^{3/2}}} \\
      &\leq& 1+ \int_1^\infty{\frac{1}{x^{3/2}}}dx\\
      &=& 1 + \left [{\frac{-2}{\sqrt{x}}}\right ]_1^\infty\\
      &=& 1 + (0 + 2)\\
      &=& 3
    \end{eqnarray*}
    Hence, $\sum_{k=1}^\infty{1/{k^{3/2}}} \leq 3$.
  %\end{solution}
}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem

In this problem, we will prove that the ``average'' number of divisors
of a number of size about $n$ is ``about'' $\ln n$.  More formally,
let $t(n)$ be the number of divisors of the number $n$, and let
\[
T(n) = \frac{1}{n} \sum_{j=1}^n t(j)
\]
be the average number of divisors of all numbers less than or equal to
$n$.  Show that $T(n) \sim \ln n$.  

{\bf Hint:} Let the function $f(i,j)=1$ if $i$ is a divisor of $j$,
and $0$ otherwise.  What do the row and column sums of $f(i,j)$ mean?

\solution{%
  not done yet!
  }

\clearpage
\problem \textbf{Asymptotic notation}
% problem 1, problem set 7, fall 1999

For each pair of functions $(f(n), g(n))$ in the table below, indicate
whether the statement at the top of the column is true (e.g., whether
$f(n) = O(g(n))$).  Assume $k\geq 1$, $\epsilon > 0$, and $c > 1$ are
constants. Your answer should be in the form of a table with ``yes''
or ``no'' in each box.

\vspace*{-0.5\baselineskip}

\begin{equation*}
  \begin{array}{|cc|*{3}{c|}}
    \hline
    f(n) & g(n) & f(n) = O(g(n)) & g(n) = O(f(n)) & f(n) =
    \Theta(g(n)) \\\hline\hline
    \log^k n & n^\epsilon &&&\\\hline
    n^k & c^n &&&\\\hline
    \sqrt{n} & n^{\sin n} &&&\\\hline
    2^n & 2^{n/2} &&&\\\hline
    \log(n!) & \log(n^n) &&&\\\hline
  \end{array}
\end{equation*}

\solution{
  \newcommand\y{\text{yes}}
  \newcommand\n{\text{no}}
%
  \begin{equation*}
    \begin{array}{|cc|*{3}{c|}}
      \hline
      f(n) & g(n) & f(n) = O(g(n)) & g(n) = O(f(n)) & f(n) =
      \Theta(g(n)) \\\hline\hline
      \log^k n & n^\epsilon & \y & \n & \n \\\hline
      n^k & c^n & \y & \n & \n \\\hline
      \sqrt{n} & n^{\sin n} & \n & \n & \n\\\hline
      2^n & 2^{n/2} & \n & \y & \n \\\hline
      \log(n!) & \log(n^n) & \y & \y & \y \\\hline
    \end{array}
  \end{equation*}
  
  Following are some hints on deriving the table above:\\
  (a) See notes on $O$-notation. (to appear)\\
  (b) Polynomial growth versus exponential growth. (See Theorem 3.6,
  Lecture 9, Fall97.)\\
  (c) When $n$ is a multiple of $\pi$, $n^{\sin n}=1$, so no
  constant times 1 will bound $\sqrt n$ as $n$ ranges over
  multiples of $\pi$. When $n$ is of the form $2k'\pi + \pi/2$,
  for some integer $k'$, then $n^{\sin n}=n$ and $\frac{n}{\sqrt n} =
  \sqrt n$ grows without bound as $k'$ increases.\\
  (d) $\frac{2^n}{2^{n/2}}=2^{n/2}$ grows without bound as $n$
  grows -- it is not bounded by a constant.\\
  (e) See Rosen \S 1.8 Ex. 61,62\\
  }

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

\problem \textbf{Recurrences}
% problem 4, problem set 6, spring 1999

\noindent
Consider a set of record items, each carrying some data and a key and
the following definition of a \emph{majority key}.

\begin{definition*}
The {\em majority key} of a set of $n$ records is a key that occurs
more than $n/2$ times.
\end{definition*}

For example, $2$ is the majority key in a set of 3 records which are
tagged, consecutively, by keys $1$, $2$, and $2$.  On the other hand,
in the set of 4 records tagged by keys $1$, $2$, $3$, and $3$, there
is no majority key.

Consider the following algorithm for finding the majority key of a set of
records: If there is an even number of records, we pair adjacent items up
(first with second, third with fourth, etc.) and compare their keys.  If
they have the same key, we keep one of them, otherwise we throw them both
away.  We run this algorithm recursively on the resulting set.  If there
is an odd number of items in our set, we find the majority key of the set
containing all but the last item.  If there was no majority key than we
check if the key of the last record is the majority key by explicitly
counting how many times this key appears in the whole set.  We continue in
this fashion until we either get one record, in which case we check if its
key is in fact the majority key --- again by counting how many times this
key appears in the original set --- or we end up with no items, in which
case we conclude that there was no majority key.

\begin{problemparts}

\vspace{-\baselineskip}
\problempart %
Prove that if there is a majority key in the initial set of records
then this algorithm terminates with a record item carrying that key.
(Hint: Find an invariant that is preserved at every stage.  Consider
the even and odd cases separately.)

\solution{%
%\begin{solution}
Case 1: Even number of elements $= 2k$.  Element t occurs at least
$2k+1$ times.  After we pair the elements into k pairs, suppose
l pairs have two different elements and $k-l$ pairs have two
same elements.  Of the l different pairs, there is at most 1 t in
each pair, therefore at most l t's are taken away.  Hence, the same
elements have at least $k-l+1$ t's out of $2k-2l$ elements.  So, t is
a majority element now and it still will be after dividing the number
of elements by 2.

Case 2: Odd number of elements $=2k+1$.  If the last element is not t,
then t occurs $k+1$ times in the first $2k$, i.e. t is a majority
element of the first $2k$ and we can see case 1.

If the last element is t, than t may not be a majority element of the
first $2k$, but the first $2k$ can have no other majority element so
the algorithm will return either t or no majority, and in the latter
case we discover t is the majority element in the checking phase.
%\end{solution}
}

\vspace{-\baselineskip}
\problempart %
Write down a recurrence for worst-case time this algorithm takes.  For
this part assume that the size of the working set at every stage is
even.

\solution{%
%\begin{solution}
  A recurrence for the worst-case time for this algorithm is
  $T(n)=T(n/2)+n/2$.
%\end{solution}
}

\vspace{-\baselineskip}
\problempart %
Solve the recurrence you wrote down in part (b) to obtain an
asymptotic time bound (theta) for worst-case running time.  (We are
interested in the {\em order} of growth, not the exact constant.)

\solution{%
  %\begin{solution}
    The asymptotic time bound for the worst-case running time is
    $T(n)=T(n/2)+n/2=T(n/4)+n/4+n/2=...= \theta (n)$.
  %\end{solution}
  }

\vspace{-\baselineskip}
\problempart %
Argue that this time bound also holds without the assumption that the
working set at each stage is even.

\solution{%
%\begin{solution}
  If the set is odd, then $T(n)=T(n/2)+n/2+n=T(n/2)+3/2n$ which comes
  down to $T(n)=3n=\theta(n)$.
%\end{solution}
}

\end{problemparts}

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

\clearpage 
\problem \textbf{Linear Recurrences}

Find closed-form solutions to the following linear recurrences.

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

\solution{%
%\begin{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*}
%\end{solution}
}

\vspace{-\baselineskip}
\problempart $x_{n} = 5 x_{n-1} - 8 x_{n-2} + 4 x_{n-3} \quad (x_0 =
1, x_1 = 2, x_2 = 3)$

\solution{%
%\begin{solution}
  The characteristic equation is $r^3 - 5 r^2 + 8 r - 4 = 0$.  Solving
  a cubic equation can be messy process, but in this case the roots
  are easy to find:

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

The general form of the solution is therefore

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

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

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

The solution to this linear system is $A = 2$, $B = -\frac{1}{2}$, and
$C = -1$.  The complete solution to the recurrence is therefore

\begin{eqnarray*}
  x_n & = & 2^{n+1} - n 2^{n-1} - 1.
\end{eqnarray*}
%\end{solution}
}

\vspace{-\baselineskip}
\problempart (Fibonacci Plus) %
$x_{n} = x_{n-1} + x_{n-2} + 1 \quad (x_0 = 0, x_1 = 1)$

\solution{%
%\begin{solution}
  First, we find the general solution to the homogeneous recurrence.
  The characteristic equation is $r^2 - r - 1 = 0$.  The roots of this
  equation are:

\begin{eqnarray*}
  r_1 & = & \frac{1 + \sqrt{5}}{2} \\ r_2 & = & \frac{1 - \sqrt{5}}{2}
\end{eqnarray*}

Therefore, the solution to the homogeneous recurrence is of the form

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

Next, we need a particular solution to the inhomogeneous recurrence.
Since the inhomogeneous term is constant, we guess a linear solution.

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

This equation holds if we set $a = 0$ and $b = -1$.  Therefore, the
inhomogeneous recurrence has the simple particular solution $x_n = -1$.
The complete solution to the recurrence is the homogeneous solution
plus the particular solution:

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

All that remains is to find the constants $A$ and $B$.  Substituting
the initial conditions gives a system of linear equations.

\begin{eqnarray*}
  0 & = & A + B - 1 \\ 1 & = & A \left( \frac{1 + \sqrt{5}}{2} \right)
  + B \left( \frac{1 - \sqrt{5}}{2} \right) - 1
\end{eqnarray*}

The solution to this linear system is:

\begin{eqnarray*}
  A & = & \frac{5 + 3 \sqrt{5}}{10} \\ B & = & \frac{5 - 3
    \sqrt{5}}{10}
\end{eqnarray*}

Therefore, the complete solution to the recurrence is

\begin{eqnarray*}
  x_n & = & \left( \frac{5 + 3 \sqrt{5}}{10} \right) \cdot \left(
  \frac{1 + \sqrt{5}}{2} \right)^n + \left( \frac{5 - 3 \sqrt{5}}{10}
\right) \cdot B \left( \frac{1 - \sqrt{5}}{2} \right)^n - 1.
\end{eqnarray*}
%\end{solution}
}

\end{problemparts}

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

\problem \textbf{Injections, Surjections, and Bijections}
%[[[Source:  first two parts are standard, second two are from
%Velleman, p. 231, Ex. 6]]]

Let $f$ be a function from $A$ to $B$, and $g$ a function from $B$ to
$C$.  The composition $g \circ f$ is defined by:
$g \circ f (x) = g(f(x))$.

%[[[Check that my notation is consistent with what's been used in the
%class, in Rosen, etc.]]]

Determine whether each of the following statements is true or false.
If it's true, prove it.  If it's false, give a counterexample.

\begin{problemparts}

\vspace{-\baselineskip}
\problempart
If $f$ and $g$ are both injective then $g \circ f$ is injective.

\vspace{-\baselineskip}
\problempart
If $f$ and $g$ are both surjective then $g \circ f$ is surjective.

\vspace{-\baselineskip}
\problempart
If $f$ is surjective and $g \circ f$ is injective then $g$ is injective.

\vspace{-\baselineskip}
\problempart
If $g$ is injective and $g \circ f$ is surjective then $f$ is surjective.

\end{problemparts}

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

\problem \textbf{Counting Using Functions}

Determine the cardinality of the following: 
\begin{problemparts}
\vspace{-\baselineskip}
\problempart %
The number of binary relations on a set $A$ of $n$ elements.

\solution{%
  [[[I get $2^{(n^2)}$, using bijection with Boolean matrices.]]]
  }

\vspace{-\baselineskip}
\problempart %
The number of different digraphs without self-loops for a set $V$ of
$n$ vertices.

\solution{%
  [[[I get $2^{(n^2 - n)}$, thinking of Boolean matrices without the
  diagonal elements.]]]
}

\vspace{-\baselineskip}
\problempart %
The number of functions from $A$ to $B$, where $|A| = n$ and $|B| =
m$.

\solution{%
  }
\end{problemparts}

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

%\clearpage
\problem \textbf{Pigeonhole Principle}

\begin{problemparts}

\vspace{-\baselineskip}
\problempart
% problem 5, problem set 7, fall 1998

%[[[This one comes from Fall 98, pset 7, problem 5.  It might be nice
%to change the numbers.  Solutions are given there too.]]]

%Prove that among every set of $52$ integers, there exists a pair with
%sum or difference divisible by 100.

Prove that among every set of $18$ integers, there exists a pair with
sum or difference divisible by $32$.

\solution{%
  The solution must be adjusted from $52$ and $100$ to $18$ and $32$,
  respectively.

  We assign each of the 52 numbers to one of 51 bins, which are
  defined as follows.

  First, we define 49 ``ordinary'' bins.  Let bin 1 contain numbers
  congruent to 1 or 99 modulo 100.  Let bin 2 contain numbers
  congruent to 2 to 98 modulo 100.  Continuing in this vein, let bin
  49 contain numbers congruent to 49 or 51 modulo 100.  Now we define
  two ``special'' bins.  Let bin 0 contain numbers congruent to 0
  modulo 100, and let bin 50 contain numbers congruent to 50 modulo
  100.

  By the Pigeonhole Principle, at least two numbers are assigned to
  the same bin.  If two numbers are assigned to an ordinary bin and
  are congruent modulo 100, then their difference is divisible by 100.
  If two numbers are assigned to an ordinary bin and are not congruent
  modulo 100, then their sum is divisible by 100.  If two numbers are
  assigned to a special bin, then both their sum and their difference
  is divisible by 100.  
  }

\vspace{-\baselineskip}
\problempart
% problem 6a, problem set 7, fall 1998

One of the 6.042 TAs has decided to conduct his next tutorial in the
following manner: he will arrange his $m$ students in alphabetical
order and hand out tutorial problems to each of the students such that
each student ends up with one or more problems.  The TA claims that
using such an arrangement, there is always a group of (one or more)
students that are consecutive in the alphabetical order and
collectively receive a number of problems that is a multiple of $m$.

As an example, consider a 6.042 tutorial with $m = 10$ students in
which the students are arranged in alphabetical order and each of
which receives $1, 2, 4, 8, 16, 16, 8, 4, 2, 1$ problems.  Then, since
the fourth, fifth, and sixth students have collectively received $40$
problems, the TA's claim holds.

Prove this claim for all $m$.

%The same pset, problem 6a.
%It's a very cute problem.
%But change not only the numbers but also the story.
%Or just make it about a sequence of $m$ consecutive positive natural
%numbers.

%Maybe say there are 120 students in the class.
%Arrange them in alphabetical order.
%Everyone owns one or more books. 
%Claim that there is some group of (one or more) students that are
%consecutive in alphabetical order, and whose total number of books is
%a multiple of 120.

\solution{%
  Let $P_i$ be the total number of problems given out to the first $i$
  students.  There are two cases.  In the first case, suppose that at
  least one of $P_1, P_2, \ldots, P_m$ is congruent to 0 modulo $m$.
  In particular, suppose that $P_j$ is congruent to 0 modulo $m$.
  This implies that the number of problems received by the first $j$
  pigs is a multiple of $m$, and so the claim holds.  In the second
  case, suppose that none of $P_1, P_2, \ldots, P_m$ is congruent to 0
  modulo $m$.  Then each of the $m$ terms $P_1, P_2, \ldots, P_m$ is
  congruent to one of the $m-1$ values $1, 2, \ldots, m-1$ modulo $m$.
  By the Pigeonhole Principle, there are at least two terms $P_j$ and
  $P_k$ that are congruent to the same value modulo $m$.  Thus
  students $j+1, j+2, \ldots, k$ received a total of $P_k - P_j$
  problems, which is a multiple of $m$.%
  }
\end{problemparts}

\end{problems}

\end{document}

\endinput

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem

Riemann's Zeta Function $\zeta(k)$ is defined to be the infinite summation:
\[
1+\frac1{2^k}+\frac1{3^k} \cdots = \sum_{j \ge 1} \frac1{j^k}
\]
Prove that 
\[
\sum_{k \ge 2} (\zeta(k)-1) = 1
\]

\textbf{Hint:} You may use (without proof) problem 2 from problem set~5.

\solution{%
  not done yet!
  }

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

\problem \textbf{Weighings}

Suppose you have a collection of 40 balls, of which you know that 39
have normal weight and one is abnormal~---~either heavy or light, but
you don't know which.

\begin{problemparts}
\vspace{-\baselineskip}
\problempart

Using a tree, describe a procedure, using weighings on a balance
scale, for determining both which ball is
the abnormal one, and whether it is heavy or light.
Your procedure should use the smallest number of weighings
possible.

\solution{%
  [[[I think 5 must work--- check me.  Does this turn out to be too
  complicated/detailed? ]]]
}

\vspace{-\baselineskip}
\problempart
Prove that no algorithm can be guaranteed to determine the answer in
fewer weighings.

\solution{%
  [[[I think that 4 is impossible; the method is as near the end of my
  lecture notes for lecture 13.]]]%
  }

\end{problemparts}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem \textbf{False Proofs}

Determine why each of the following are false proofs.

\begin{problemparts}

\vspace{-\baselineskip}
\problempart

\[
\left( \sum_{j=1}^n a_j \right) \left( \sum_{k=1}^n 1/a_k \right) =
\sum_{j=1}^n \sum_{k=1}^n a_j/a_k =
\sum_{k=1}^n \sum_{k=1}^n a_k/a_k =
\sum_{k=1}^n \sum_{k=1}^n 1 =
\sum_{k=1}^n n = n^2
\]

\solution{%
  not done yet!
  }

\vspace{-\baselineskip}
\problempart



\end{problemparts}


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

\problem \textbf{Asymptotic notation}
% problem 4, problem set 5, fall 1997

Given that $f(x) = O(g(x))$, prove or disprove the following:

\bparts
\ppart
$2^{f(x)} = O(2^{g(x)})$

\solution{%
  The above does not hold. Let $f(x) = 2x$ and $g(x) = x$. Then $f(x)
  = O(g(x))$. Now $2^{f(x)} = 2^{2x} = 4^x$, and $2^{g(x)} = 2^x$, and
  $4^x\neq O(2^x)$. Indeed, $\frac{4^x}{2^x} = 2^x$, so the ratio
  grows without bound as $x$ grows~---~it is not bounded by a constant. %
  }

\ppart 
$f(x)^2 = O(g(x)^2)$

\solution{%
  The above does hold.  Since $f(x) = O(g(x))$, $\exists x_0,c$ such
  that $\forall x \geq x_0, |f(x)| \leq cg(x)$.  So, $\forall x \geq
  x_0, f(x)^2 \leq c^2g(x)^2$.  Therefore, there exist $x_0' = x_0$
  and $c' = c^2$ such that $\forall x \geq x_0', f(x)^2 \leq
  c'g(x)^2$.  So $f(x)^2 =
  O(g(x)^2)$. %
  }

\eparts

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

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

\solution{%
%\begin{solution}
  First, we find the general solution to the homogeneous 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 homogeneous 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 inhomogeneous 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 homogeneous 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{solution}
}

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

\problem \textbf{Injections, Surjections, and Bijections}
% problem 5, problem set 6, spring 1998

For each of the following functions, $f: \reals \rightarrow \reals$,
determine whether it is an injection, surjection, or bijection and
give the inverse if it exists.

\begin{problemparts}

\vspace{-\baselineskip}
\problempart $f(x) = \sin (x)$

\solution{%
%\begin{solution}
  $f(x) = \sin (x)$ is not an injection because it maps $0$ and $\pi$
  to $0$.  It is not a surjection because it maps $\reals$ onto
  $[-1,1]$.  Therefore it is not a bijection and does not have an
  inverse.
%\end{solution}
}

\vspace{-\baselineskip}
\problempart $f(x) = \frac{x+2}{x^2 + 4}$

\solution{%
%\begin{solution}
  $f(x) = {{x+2}\over{x^2 + 4}}$ is not an injection because it maps
  $0$ and $2$ to ${1}\over{2}$.  It is not a surjection because $1$
  has no pre-image.  $x^2 + 4 = x+2$ has no real solutions.  Therefore
  it is not a bijection and does not have an
  inverse.
%\end{solution}
}

\vspace{-\baselineskip}
\problempart

\begin{equation}
f(x) =
\begin{cases}
  {\ln x} & \text{if } x > 0,\\ %
  0 & \text{if } x = 0,\\ %
  {e^x} & \text{if } x < 0 %
\end{cases}
\end{equation}

\solution{%
%\begin{solution}  
  This function is not an injection because $ln {{1}\over{2}}$ and
  $e^{{1}\over{2}}$ both map to ${1}\over{2}$.  It is a surjection
  because for any $x \in \reals$, a pre-image of $x$ is $e^x$ for $x
  \neq 0$, and $0$ for $x=0$.
%\end{solution}
}

\vspace{-\baselineskip}
\problempart

$f(x) = x^3 + 2$

\solution{%
%\begin{solution}
  $f(x) = x^3 + 2$ is an injection because $x \neq y \rightarrow x^3
  \neq y^3 \rightarrow x^3 + 2 \neq y^3 + 2$.  The function is a
  surjection because for every $x \in \reals$ $\exists\; y =
  (x-2)^{{1}\over{3}}$.  Therefore $f$ is a bijection.  It's inverse
  is $(x-2)^{{1}\over{3}}$.
%\end{solution}
}

\end{problemparts}

