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

%\newcommand{\solution}[1]{}
\newcommand{\solution}[1]{\textbf{Solution}: \bigskip #1}

\begin{document}

\tutn{7}{3/19/99}{March 19, 1999}

\iffalse
\section*{TEACHING INSTRUCTIONS}
Cover all of section 1, and \S2.1.  Also do \S3.1, but skip the proof of
Lemma~\ref{incomp} if you can't be completely finished in $< 1$ hour.
Everything else is optional.  If you do finish earlier, you can present
some of it, or skip it and get to the Team problems sooner.
\fi

\section{Linear Recurrence Equations}
A \emph{degree $d$ linear recurrence equation} is
\[f(n) = g(n) + \sum_{i=1}^d a_if(n-i)\]
for positive integer $d$ and constants $a_i \in \reals$ for $1 \leq i \leq
d$.  The recurrence is \emph{homogeneous} if $g$ is absent, that is, $g(n)
\equiv 0$.  The \emph{characteristic polynomial} of the recurrence is
\[c(x)::= x^d- \sum_{i=1}^{d} a_ix^{d-i}.\]

\subsection{Distinct Roots}
We saw in lecture that if the characteristic polynomial has $d$ distinct
roots $\alpha_1,\dots, \alpha_d$, then the solutions to the homogeneous
recurrence are the linear combinations of ${\alpha_i}^n$.

\subsection{Repeated Roots}
If the characteristic polynomial of a linear recurrence has a repeated root,
then the solution is slightly more complicated.  The main tool is the
following theorem, which we will not prove.

\begin{theorem}\label{rroot}
If $r$ is a root of the characteristic equation of a recurrence with
multiplicity $m$, then all of $r^n, n r^n, n^2 r^n, \ldots n^{m-1} r^n$
are solutions to the homogeneous recurrence.
\end{theorem}

\textbf{Reminder}: The \emph{multiplicity} of a root $r$ of a polynomial
$p(x)$ is the largest positive integer $m$ such that $(x-r)^m$ divides
$p(x)$.

For example, if the characteristic equation of a recurrence has root
$r_1$ with multiplicity 2, root $r_2$ with multiplicity 1, and root
$r_3$ with multiplicity 3, then the solution to the recurrence has the
form:

\[
f(n) = c_1 r_1^n + c_2 n r_1^n +
       c_3 r_2^n +
       c_4 r_3^n + c_5 n r_3^n + c_6 n^2 r_3^n
\]

As before, the constants depend on the boundary conditions.  Each
boundary condition generates a linear equation, and the constants are
computed by solving the resulting system of linear equations.  In this
respect, solving linear recurrences is very similar to solving linear
differential equations.

\iffalse
\subsection{Repeated root example}
Let's work an example.  Suppose that there is a type of plant that lives
forever, but only reproduces during the first year of life.  How fast will
the plant population grow?  (Notice that this is just the reverse of the
graduate student job problem where faculty ``reproduce'' in every year
except the first.)

Let $f(n)$ be the number of plants in year $n$.  As boundary
conditions, define $f(0) = 0$ and $f(1) = 1$.  The plant population in
year $n$ is equal to the population from the year before plus the
number of new plants.  The population from the year before is
$f(n-1)$.  The number of new plants this year is equal to the number
of new plants last year or $f(n-1) - f(n-2)$.  We can now form a
recurrence equation for the plant population:

\begin{eqnarray*}
f(n) & = & f(n-1) + (f(n-1) - f(n-2)) \\
     & = & 2 f(n-1) - f(n-2) \\
f(n) - 2 f(n-1) + f(n-2) & = & 0
\end{eqnarray*}

The characteristic equation is $\alpha^2 - 2 \alpha + 1 = 0$, which
has the single root $\alpha = 1$ with multiplicity 2.  Therefore, the
solution to the recurrence has the form:

\begin{eqnarray*}
f(n) & = & c_1 (1)^n + c_2 n (1)^n \\
     & = & c_1 + c_2 n
\end{eqnarray*}

The boundary conditions, $f(0) = 0$ and $f(1) = 1$, generate the
following linear equations:

\begin{eqnarray*}
0 & = & c_1 + c_2 (0) \\
1 & = & c_1 + c_2 (1)
\end{eqnarray*}

The solution to the linear system is $c_1 = 0$ and $c_2 = 1$.
Therefore, the solution to the recurrence is:

\begin{eqnarray*}
f(n) & = & c_1 + c_2 n \\
     & = & 0 + (1) n \\
     & = & n
\end{eqnarray*}

The answer turns out to be very simple!  In year $n$, there are
exactly $n$ plants.  Of course, we probably could have solved this
problem more easily with Guess and Verify, but for many other
examples, guessing is not so easy.
\fi

\subsection{An Inhomogeneous Example}
Let
\[f(n) = 4 f(n-1) - 4 f(n-2) + n\]
and, as a boundary condition, let $f(0) = 4$ and $f(1) = 7$.

\subsubsection*{Step 1:  Solve the Homogeneous Recurrence}

The homogeneous recurrence is $f(n) - 4 f(n-1) + 4 f(n-2) = 0$.  The
characteristic equation is $\alpha^2 - 4 \alpha + 4$.  The only root
is $\alpha = 2$ with multiplicity 2.  Therefore, the homogeneous
solution is $c_1 2^n + c_2 n 2^n$.

\subsubsection*{Step 2:  Find a Particular Solution}
We know we can find all solutions by combining a single solution of the
inhomogeneous recurrence with all solutions of the associated homogeneous
recurrence.

So we need a single solution to the recurrence $f(n) = 4 f(n-1) - 4 f(n-2)
+ n$.  Let's guess a solution of the form $a n + b$ and substitute into
the recurrence:

\begin{eqnarray*}
f(n) & = & 4 f(n-1) - 4 f(n-2) + n \\
a n + b & = & 4 (a (n-1) + b) - 4 (a (n-2) + b) + n \\
        & = & 4 a n - 4 a + 4 b - 4 a n + 8 a - 4 b + n \\
        & = & 4 a + n \\
& \Rightarrow & a = 1, b = 4a = 4
\end{eqnarray*}

This gives the particular solution $f(n) = n + 4$.

\subsubsection*{Step 3:  Add Solutions and Find Constants}

Adding the homogeneous solution and the particular solution gives the
general solution:

\[
f(n) = c_1 2^n + c_2 n 2^n + n + 4
\]

The values of the constants are obtained from the boundary conditions,
$f(0) = 4$ and $f(1) = 7$.

\begin{eqnarray*}
4 & = & c_1 2^0 + 0 c_2 2^0 + 0 + 4 \\
  & = & c_1 + 4 \\
c_1 & = & 0 \\
7 & = & c_1 2^1 + 1 c_2 2^1 + 1 + 4 \\
  & = & 2 c_1 + 2 c_2  + 5 \\
c_2 & = & 1
\end{eqnarray*}

The solution to the recurrence is $f(n) = n 2^n + n + 4$.

Lecture 12 Notes gives some suggestions of how to guess the form of
solution to an inhomogeneous linear recurrence.  Rosen, \S5.2, Theorem 6
also describes the general forms of the solutions to many common examples
of inhomogeneous recurrences.

\section{Pigeonholing}

\subsection{Pigeonhole Principle Example: Weighing Balls}

In the first tutorial you worked out how to use three weighings on a
balance scale to solve the following problem: there are twelve balls of
which eleven have the same weight and one has a different weight.
Identify the different-weight ball, and determine whether it is heavier or
lighter than the rest.

The problem is solvable using a strategy algorithm represented by a
ternary tree.  Each internal node in the tree represents a weighing such
as, ``put balls 1, 3 on one side and 2, 4 on the other side''.  Each leaf
node represents a result such as, ``the 3rd ball is heavier than the
rest''.  A run of the algorithm corresponds to a path from the root to a
leaf.  At each internal node, we perform the weighing associated with the
node.  Based on the result -- ``leaning left'', ``leaning right'' or
``balanced'' we descend to one of the three children.  When we reach a
leaf, we output the indicated result.

\newpage
\begin{verbatim}
        (labels of balls in left pan, labels of balls in right pan)
 
                         ({1,2,3,4},{5,6,7,8})
                                   /|\
                                 L  B  R
                               /    |     \
                             /      |        \
                          /         |           \
                       /            |              \
                  (...,...) ({1,2,3},{9.10.11}) (...,...)
                     /|\           /|\             /|\
                    L B R         L B R           L B R
                   /  |  \       /  |  \         /  |  \  
                  .       .         .   .       .   .   .
                  .       .         .           .       .
                  .                 .                   .
leaves:          3H                 7L                 11L


``3H'' means ball 3 is heavy, ``7L'' means ball 7 is light, etc.
\end{verbatim}

Could we handle more balls than twelve, still with three weighings?
Pigeonholing gives an easy proof that we \textbf{cannot} handle 14 balls.

\begin{claim}
The weighing problem with 14 balls cannot be solved with 3 weighings.
\end{claim}

\begin{proof}
The pigeons are the possible situations.  Since any one of 14 balls could
be the different weight one, and it could be either heavier or lighter
than the rest, there are 28 pigeons.  The holes are the 27 leaves of the
depth-3 tree.  Since there are more pigeons than holes, the Pigeonhole
Principle implies that some hole must have two pigeons.  That is, some
leaf is not associated with a unique situation.  Therefore, for every
three-weighing strategy, there is some pair of situations that the
strategy cannot distinguish.  In at least one of these situations, the
strategy must give the wrong answer.
\end{proof}

What about 13 balls?  Now there are only 26 pigeons and a three-weighing
strategy tree has 27 leaves, so at this point, we cannot rule out the
possibility of handling 13 balls.

\subsection{Two Weighing Problems}

Suppose that we have $n$ balls.  All weigh the same except for one
that is heavier.  We have a funny balance scale that reports only
whether two weights are equal or unequal, not which one is heavier.
How many weighings are necessary to find the heavy ball?

This puzzle is like previous weighing problems in that we can
represent any strategy with a tree.  In this case, since the scale
only reports two results at each stage, the tree is binary.  If we use
$W$ weighings, then the tree has depth $W$ and $2^W$ leaves.  There
are $n$ possible outcomes, since any one of the $n$ balls could be the
heavy one.  If the number of outcomes $n$ is greater than the number
of leaves $2^W$, then by the Pigeonhole Principle, some leaf is
associated with two or more outcomes.  This means that the strategy
can not distinguish these two situations, and so sometimes produces an
incorrect answer.  Therefore, we must have $2^W \geq n$, and so we
need at least $W \geq \lceil \log_2 n \rceil$ weighings to always find
the heavy ball.  (This is only a lower bound; we have not given a
strategy that actually works with this number of weighings!)

Now suppose the setup is the same, but instead of finding the heavy
ball, our task is to find one of the normal-weight balls.  There are
still $n$ possible outcomes, the strategy tree is still binary, so
it appears we still need about $\log n$ weighings.

But what about this strategy?  We weigh two balls.  If they are
equal, we pick one.  If they are unequal, we pick a ball that we have
not yet weighed.  With this strategy, we can find a normal-weight ball
in just 1 weighing!  The preceding argument must contain a flaw!

The problem with the argument is that a strategy need not distinguish
all $n$ possible situations to be correct.  For example, if we know
that the heavy ball is among the first $n/2$ balls, then we can just
pick any of the other $n/2$ to get a normal-weight ball.  Unlike the
previous weighing problems, we don't have to know precisely which ball
is heavy in order to give a correct answer!


\subsection{Checkers}

Suppose we place $n+1$ checkers on different squares of an $n \times n$
checkerboard.  We claim that some length occurs more than once as the
distance between different checkered squares.  (The same square may be
involved in both cases, namely, when the distance from $A$ to $B$ is the
same as the distance from $A$ to $C$ for three different squares $A,B,C$.

The distance between checkers at distinct positions $(x_1,y_1)$ and
$(x_2,y_2)$ is uniquely determined by the set
$\set{\abs{x_1 - x_2}, \abs{y_1 - y_2}}$.  The values of these differences
can be $0,\dots,n-1$ except that both can't be zero since the positions
are different.  These are the holes.

We claim there are $n(n+1)/2 - 1$ holes.  Each hole is a set of one or two
integers between 0 and $n-1$, except for $\set{0}$ which corresponds to
the distance zero between a point and itself.  There are $n(n-1)$ possible
distinct \emph{ordered} pairs of numbers $0,\dots,n-1$, and half that many
if we ignore their order.  There are an additional $n-1$ sets of size one
excluding $\set{0}$, so the total is $n(n-1)/2 + n - 1 = n(n+1)/2 -1$.

Each set of two checkers is a pigeon.  There are $(n+1)n$ ordered pairs of
checkers, and hence half that many pigeons.  A pigeon gets assigned to a
hole which is the difference of the $x$ and $y$ coordinates of the checker
positions.  Since there is one more pigeon than hole, there must be two
pigeons in the same hole.  That means the $x$ and $y$ coordinate
differences, and hence the distance, between the two pigeons is the same.

\section{Strong Pigeonholing}

The {\em Strong Pigeonhole Principle}.  If $n$ pigeons are placed in $r$
holes, then there is a hole with at least $\ceil{n/r}$ pigeons in it.

\begin{proof}
By contradiction.  Assume that there is a way of placing the pigeons in
the holes so that each hole has at most $\ceil{n/r}-1$ pigeons.  Then
since there are $r$ holes, the total number of pigeons is at most
$r(\ceil{n/r}-1) < r(n/r) = n$, contradicting the fact that there
are $n$ pigeons.
\end{proof}

\subsection{Chains and Antichains}
We proved in an earlier recitation:
\begin{theorem}
If $t$ is the length of the longest chain in a poset $(A, \preceq)$
then $A$ can be partitioned into $t$ antichains.
\end{theorem}

Review: {\bf chain}: all elements comparable (total order); {\bf
antichain}: all elements incomparable.

We can use this along with Pigeonholing to prove a famous result about
posets:

\begin{theorem}\label{anti}
(Dilworth\footnote{Theorem~\ref{anti} is a corollary of a more powerful
result known as Dilworth's Theorem.}) If $t$ is the length of the longest
chain in a poset with $n$ elements, then the poset has an antichain of
size $\geq n/t$.
\end{theorem}

\begin{proof}
By previous result, the $n$ elements can be partitioned into
$t$ antichains.  The pigeons are the $n$ elements.  The holes are the $t$
antichains.  By Strong Pigeonholing, there must be $\geq n/t$
pigeons in some hole.
\end{proof}

Here's an an amusing application of Theorem~\ref{anti} (this was used as a
Team Problem in a past term):

\textbf{Claim}: In any sequence of $n$ different numbers, there is either
an increasing subsequence of length $\ceil{\sqrt{n}}$ or a decreasing
subsequence of that length.

For example
\[ 6 4 7 9 1 2 5 3 8\]
has the decreasing sequence
\[6 4 1\]
and the increasing sequence
\[1 2 3 8.\]
That is, it has ``long'' subsequences of both kinds.

\begin{proof}
Define a DAG whose vertices are the numbers in the sequence.  For the
ordering, define $(a, b)$ to be an edge iff [$a < b$ and $a$ comes before
$b$ in the sequence].  A chain obviously corresponds to an increasing
subsequence, but what does an antichain correspond to?

\begin{lemma}\label{incomp}
If the set $\set{a_1,a_2,\dots,a_t}$ is an antichain in the DAG, and $a_1
> a_2 > \cdots > a_t$, then $a_1,a_2,\dots,a_t$ forms a decreasing
subsequence.
\end{lemma}
\begin{proof}
By contradiction.  If $a_i$ did not precede $a_{i+1}$ in the sequence, for
some $i$ between 1 and $t$, then $a_{i+1}$ must precede $a_{i}$.  But
$a_{i+1} < a_i$, so by definition of the DAG, there is an edge $(a_{i+1},
a_i)$, contradicting the fact that $a_i$ and $a_{i+1}$ are part of an
antichain and hence are incomparable.
\end{proof}

So if we take any antichain in the DAG and list it in decreasing numerical
order, we obtain an decreasing subsequence.

From Theorem~\ref{anti} with $t = \sqrt{n}$, there is a chain or an
antichain of size $\ceil{\sqrt{n}}$.  If we have a chain, then it is an
increasing subsequence of length $\ceil{\sqrt{n}}$; otherwise we have an
antichain of this length which yields decreasing subsequence of this
length by Lemma~\ref{incomp}.
\end{proof}


\subsection{Chessboard numbering}
Consider the following problem: we are to number the squares of a
chessboard from 1 to 64.  Is it possible to do this so that the difference
between the numbers of any pair of adjacent squares (horizontally,
vertically or diagonally) is no more than 8 ?

The answer is NO.  Consider the square numbered 1 and the square numbered
64. We know that no matter where they are placed, there is a path of
length at most 7 between them (i.e., in at most 7 hops to adjacent
squares, we can go from the 1-square to the 64-square).  To go from 1 to
64, there is a difference of 63 to be covered in 7 hops.  Let us think of
this difference as 63 pigeons and they have to each be placed in one of 7
holes.  The holes represent which hop the step is taken in.  Now by the
strong PP there must be a hole with at least 63/7 = 9 pigeons.  This means
that there must be a hop which covers a difference of 9 or greater.  That
is there are a pair of adjacent squares that differ by at least 9.


\section{Team Problems}

\begin{problems}

\problem Prove that the different-weight ball problem with 13 balls cannot
be solved with 3 weighings.  \hint Unlike the 14 ball case, it doesn't
fall in one step to the Pigeon Hole Principle.  But proper appeals to the
Pigeonhole Principle can greatly simplify the the case analysis.

\solution{Let $n$ be the number of balls placed in each pan of the balance
scale on the first weighing.  Since there are 13 balls, $n$ could be 1, 2,
3, 4, 5, or 6.  We can actually reduce these 6 cases to just two.

In the first case, suppose that $n \leq 4$.  This means that at least 5
balls are not used in the first weighing.  As a result, there are at least
10 situations in which the scale will be balanced on the first weighing:
the odd ball could be any of the unweighed balls, and it could be either
heavy or light.  By the Pigeonhole Principle, we can not distinguish
between these 10 or more cases with only two additional weighings.

In the second case, suppose that $n \geq 5$.  Now there are $2n \geq
10$ situations in which the right pan is heavier: $n$ when the odd
ball is heavy and in the right pan and $n$ more when the odd ball is
light and in the left pan.  Again, by the Pigeonhole Principle, we can
not distinguish these 10 or more cases with only two weighings.}

\problem
In how many ways can a $3 \times 2n$ grid of squares be tiled with $1
\times 2$ dominos?  For example, here is one possible tiling of a $3 \times 8$
grid.

\bigskip
\centerline{\resizebox{!}{1.0in}{\includegraphics{tiling1.eps}}}
\bigskip

We can solve this problem using linear recurrence equations.

\begin{problemparts}

\problempart
First, let's compute the number of tilings for $n = 1$ and $n = 2$
as base cases.  How many ways are there to tile a $3 \times 2$ grid
and a $3 \times 4$ grid?

\solution{There are 3 ways to tile a $3 \times 2$ grid, and there are 11 ways
to tile a $3 \times 4$ grid.}

\problempart Define $A_n$, $B_n$, and $C_n$ to be the number of ways to tile
the following shapes with $1 \times 2$ dominos.  Formulate a set of
three linear recurrences relating these variables.

\bigskip
\centerline{\resizebox{!}{1.5in}{\includegraphics{tiling2.eps}}}
\bigskip

\solution{
\begin{eqnarray*}
A_{n} & = & A_{n-1} + 2 B_{n} \\
B_{n} & = & C_n \\
C_{n} & = & A_{n-1} + B_{n-1}
\end{eqnarray*}
}

\problempart Make substitutions to express $A_n$ as a function of $A_{n-1}$ and
$A_{n-2}$.  This gives a linear recurrence for $A_n$, the number of
ways to tile a $3 \times 2n$ grid with $1 \times 2$ dominos.

\solution{
Since $B_n = C_n$, we can eliminate either variable from the system.

\begin{eqnarray*}
A_{n} & = & A_{n-1} + 2 B_n \\
B_{n} & = & A_{n-1} + B_{n-1}
\end{eqnarray*}

Solving for $B_n$ in the first recurrence gives

\begin{eqnarray*}
B_{n} & = & \frac{A_n - A_{n-1}}{2}.
\end{eqnarray*}

Substituting this formula for $B_n$ into the the second recurrence
simplifies the system to one variable.

\begin{eqnarray*}
\frac{A_n - A_{n-1}}{2} & = & A_{n-1} + \frac{A_{n-1} - A_{n-2}}{2} \\
A_n & = & 4 A_{n-1} - A_{n-2}
\end{eqnarray*}
}

\problempart Use the base cases from part (a) and the linear recurrence from
part (c) to compute the number of ways to tile a $3 \times 2n$ grid
with $1 \times 2$ dominos.

\solution{
The characteristic equation is $r^2 - 4r + 1 = 0$, which has roots at
$r = 2 + \sqrt{3}$ and $r = 2 - \sqrt{3}$.  Therefore, the general
form of the solution is

\begin{eqnarray*}
A_n	& = &	X \cdot \left(2 + \sqrt{3}\right)^n +
		Y \cdot \left(2 - \sqrt{3}\right)^n.
\end{eqnarray*}

Substituting the base cases, $A_1 = 3$ and $A_2 = 11$, gives the
following system of equations:

\begin{eqnarray*}
3	& = &	X \cdot \left(2 + \sqrt{3}\right) +
		Y \cdot \left(2 - \sqrt{3}\right) \\
11	& = &	X \cdot \left(2 + \sqrt{3}\right)^2 +
		Y \cdot \left(2 - \sqrt{3}\right)^2 \\
\end{eqnarray*}

Solving this system of equations gives:

\begin{eqnarray*}
X 	& = &	\frac{3 + \sqrt{3}}{6} \\
Y 	& = &	\frac{3 - \sqrt{3}}{6}
\end{eqnarray*}

Therefore, the number of way to tile a $3 \times 2n$ grid using $1
\times 2$ dominos is

\begin{eqnarray*}
\frac{3 + \sqrt{3}}{6} \cdot \left(2 + \sqrt{3}\right)^n +
\frac{3 - \sqrt{3}}{6} \cdot \left(2 - \sqrt{3}\right)^n.
\end{eqnarray*}
}

\end{problemparts}

\iffalse
\problem
Prove Theorem~\ref{rroot} for linear homogeneous recurrences of degree 3
whose characteristic polynomial has a root of multiplicity 2.  \hint:
Remember, a polynomial $p(x)$ has a root, $r$, of multiplicity $\geq 2$
iff $x-r$ divides $dp/dx$.

\solution{Let $c(x)$ be the characteristic polynomial
$x^3 - a_1 x^2 - a_2x - a_3$.  Let
\[
c_n(x) ::= x^{n-3}c(x)= x^n - a_1 x^{n-1} - a_2 x^{n-2} - a_3 x^{n-3}.
\]
Since $c_n$ is a multiple of $c$, the root $r$ is also a root of $c_n$ of
multiplicity 2.  Hence, $x-r$ is a factor of the derivative
$d\, c_n/dx$, so $r$ is a root of $d\, c_n/dx$ and hence of  $x(dc_n/dx)$.
But
\begin{eqnarray*}
x(dc_n/dx) & =& x(nx^{n-1} - a_1(n-1)x^{n-2} -a_2(n-2)x^{n-3} - a_3(n-3)
 x^{n-4})\\
& = & nx^n - (n-1)a_1 x^{n-1} - (n-2)a_2 x^{n-2}- (n-3)a_3 x^{n-3}.
\end{eqnarray*}
That is,
\[nr^n - (n-1)a_1 r^{n-1} - (n-2)a_2 r^{n-2}- (n-3)a_3 r^{n-3} = 0\]
proving that $nr^n$ satisfies the recurrence.}
\fi

\end{problems}
\end{document}

