\documentclass[12pt, twoside]{article}
\usepackage{amsmath}
\usepackage{psfig}

\input{macros-course}
\newcommand{\cross}{\times}
\newcommand{\eqdef}{\mathbin{::=}}

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

\begin{document}

\tutprobn{14}{10/29/99}{October 27, 1999}


\begin{problems}

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

\begin{figure}[htbp]
\centerline{\psfig{figure=figures/tiling1.eps,height=1in}}
\caption{A Tiling.}
\label{fig:tiling}
\end{figure}


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.


\begin{figure}[htbp]
\centerline{\psfig{figure=figures/tiling2.eps,height=1.5in}}
\caption{Shapes for Tiling.}
\label{fig:tiling-shapes}
\end{figure}

\solution{

In a tiling of shape $\texttt{A}_{\texttt{n}}$, the upper right corner can
be covered by a vertical tile, leaving the shape $\texttt{B}_{\texttt{n}}$.
The other case is that the the upper right corner is covered by a
horizontal tile, in which case the lower right corner may be covered by a
vertical tile leaving shape $\texttt{C}_{\texttt{n}}$, or it may be covered
by a horizontal tile, in which case the middle right square must also be
covered by a horizontal tile leaving shape $\texttt{A}_{\texttt{n-1}}$.  So
\[
A_{n}  = B_{n} + C_n +  A_{n-1}.
\]

In a tiling of $\texttt{B}_{\texttt{n}}$, the lower right corner must be
covered by a horizontal tile, leaving the shape $\texttt{C}_{\texttt{n}}$,
so
\[
B_{n}  = C_n.
\]

Finally, in a tiling of $\texttt{C}_{\texttt{n}}$, the lower right corner
and middle right square may be covered by horizontal tiles, leaving the shape
$\texttt{B}_{\texttt{n-1}}$, or it may be covered by a vertical tile,
leaving $\texttt{A}_{\texttt{n-1}}$,
so
\[
C_{n}  =  B_{n-1} + A_{n-1}.
\]

}

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


\problem

\bparts

\ppart Prove that if a polynomial $p(x)$ has a root, $r$, of multiplicity
$\geq 2$, then $x-r$ divides the derivative, $dp/dx$, of $p$.

\solution{

We know 
\[
p(x) = (x-r)^2 q(x)
\]
for some polynomial $q$.  So
\[
dp/dx =  q(x) \frac{d(x-r)^2}{dx} + (x-r)^2 \frac{dq}{dx} = (x-r)[2q(x) +
(x-r)\frac{dq}{dx}].
\]

}

\ppart Prove that if a homogeneous linear recurrence of
degree 3, that is, of the form
\[
a_n = c_1 a_{n-1} + c_2 a_{n-2} + c_3 a_{n-3}
\]
has a characteristic polynomial with a root, $r$, of multiplicity 2, then
$a_n \eqdef nr^n$ is a solution to the recurrence.
\hint Let $p_n(x) \eqdef x^n - c_1 x^{n-1} - c_2 x^{n-2} - c_3
x^{n-3}$ and prove that $r$ is a root of $d p_n/dx$.

\solution{

Let $p(x)$ be the characteristic polynomial $x^3 - c_1 x^2 - c_2x - c_3$.
Then
\[
p_n(x) \eqdef x^n - c_1 x^{n-1} - c_2 x^{n-2} - c_3 x^{n-3} =  x^{n-3}p(x).
\]
Since $p_n$ is a multiple of $p$, the root $r$ is also a root of $p_n$ of
multiplicity 2.  Hence, $x-r$ is a factor of the derivative $d p_n/dx$, so
$r$ is a root of $d p_n/dx$.  Hence $r$ is also a root of of $(d p_n/dx)x$.  But
\begin{eqnarray*}
(d p_n/dx)x & =& (nx^{n-1} - c_1(n-1)x^{n-2} -c_2(n-2)x^{n-3} - c_3(n-3) x^{n-4})x\\
& = & nx^n - c_1 (n-1)x^{n-1} - c_2(n-2) x^{n-2}- c_3 (n-3)x^{n-3}.
\end{eqnarray*}
That is, for $x=r$
\[
0  =  nr^n - c_1 (n-1)r^{n-1} - c_2 (n-2)r^{n-2}- c_3 (n-3)r^{n-3},
\]
so 
\[
nr^n =  c_1 (n-1)r^{n-1} + c_2 (n-2)r^{n-2} + c_3 (n-3)r^{n-3},
\]
proving that $a_n \eqdef nr^n$ satisfies the recurrence.}

\eparts


\problem
\textbf{Life and Death.}
In ancient Mars, cannibalism was an essential way of life.  The Marons and
the Batons were two species that lived for several thousand years in close
contact.  Every year, first all the Marons sustained themselves by first
consuming Batons: two Marons ate one Baton between them.  Then they
reproduced: one-year-old Marons doubled in number while Marons that were
two or older tripled in number.  Then the surviving Batons consumed one
newborn Maron each, and then all the Batons reproduced to quadruple in
number.  This cycle repeated every year.  After 1 year there were two
1-year old Marons and two 1-year old Batons.  After 2 years there were two
1-year olds and two 2-year olds in each of the two species.  How many of
each will there be of each species at the end of $n$ years?  Try for an
exact closed form answer rather than just a $\Theta()$ bound.

\solution{

Let $g(n)$ be the number of Marons after $n$ years, and $f(n)$ the number
of Batons.

After $n-1$ years, we have $g(n-1)$ Marons and $f(n-1)$ Batons.  Then in
the $n^{th}$ year, from the rules of sustenance, the population of Batons
drops to $f(n-1) - (1/2)g(n-1)$, assuming the Maron population was even.
The number of 1-year old Marons is $g(n-1) - g(n-2)$, this time assuming
the population is nondecreasing, and their population doubles to $2(g(n-1)
-g(n-2))$.  Meanwhile the number of older Marons triples from $g(n-2)$ to
$3g(n-2)$.  Then it is the Batons turn.  The surviving Batons consume a
newborn Maron each.  So, assuming there are more newborn Marons than
surviving Batons, the population of Marons after $n$ years is
\begin{eqnarray}\label{gf}
g(n) & = & 2(g(n-1)-g(n-2)) + 3g(n-2) -(f(n-1)-\frac{1}{2}g(n-1))\\
     & = & \frac{5}{2}g(n-1) + g(n-2) - f(n-1).
\end{eqnarray}
The Batons then quadruple.  So the number of Batons after $n$ years is:
\begin{equation}
f(n) = 4(f(n-1) - \frac{1}{2}g(n-1))\label{fg}
\end{equation}

A methodical approach at this point is to solve equation~(\ref{fg}) for
$g(n-1)$ as a linear combination of $f(n)$ and $f(n-1)$, then substitute
for $g(n), g(n-1)$ and $g(n-2)$ in equation~(\ref{gf}) to obtain a
homogeneous linear recurrence of degree 3 for $f$.  Solve this for $f$ and
that solution then defines one for $g$.

On the other hand, we know that $f(1) = g(1) = 2$ and $f(2) = g(2) = 4$.
Substituting these values in the recurrences, we get $f(3) = g(3) = 8$ and
$f(4) = g(4) = 16$.  So instead, an inspired approach at this point is to
guess that $g(n) = f(n) = 2^n$.  We can verify this --- and the three
assumptions on which the validity of the recurrence rests --- by strong
{\em simultaneous} induction on the two populations.  That is, the
induction hypothesis requires properties of \emph{both} $f(n)$ and $g(n)$:
\begin{proof}

I.H. : $P(n): f(n) = g(n) = 2^n$.

Base:  $n=1$: $f(1) = g(1) = 2$, and $n=2$: $f(2) = g(2) = 4$. 

Ind. Step.: Assume $P(k)$ is true for $1 \leq n$.  To prove $P(n+1)$,
observe
\begin{eqnarray*}
f(n+1) & = & 4(f(n) - \frac{1}{2}g(n))\\
       & = & 4(2^n - 2^{n-1})\\
       & = & 4(2^{n-1}) = 2^{n+1}.\\
g(n+1) & = & \frac{5}{2}g(n)+g(n-1) - f(n)\\
       & = & \frac{5}{2}(2^{n}) + 2^{n-1} - 2^n\\
       & = & 2^{n+1}.
\end{eqnarray*}

\end{proof}


}

\iffalse
\problem The inhabitants of Xoros 19 are unsatisfied
with the performance of their Fritolator devices.  They have
constructed a factory to convert Fritolators into new, more deadly
craft.  Each day, the factory performs one of the following
conversions:

\begin{eqnarray*}
\text{1 Fritolator} & \rightarrow & \text{1 Pringlizer} \\
\text{2 Fritolators} & \rightarrow & \text{1 Tostitomatic} \\
\text{2 Fritolators} & \rightarrow & \text{1 Santitotron}
\end{eqnarray*}

Grzzwk, the ruler of Xoros 19, plans to use the factory to convert his
entire fleet of $n$ Fritolators.  However, he must decide the sequence
of ships that the factory will produce.  Such a sequence is called a
{\em conversion schedule}.  For example, there are 5 possible
conversion schedules for a fleet of $n = 3$ Fritolators:

\begin{enumerate}
\item Pringlizer, Pringlizer, Pringlizer

\item Pringlizer, Tostitomatic

\item Pringlizer, Santitotron

\item Tostitomatic, Pringlizer

\item Santitotron, Pringlizer

\end{enumerate}

\bigskip

\begin{problemparts}

\problempart Let $x_n$ be the number of possible conversion
schedules for a fleet of $n$ Fritolators.  Express $x_n$ with a
recurrence relation and sufficient base cases.

\solution{
If $n = 0$, then there is a single conversion schedule; namely,
produce nothing.  If $n = 1$, then there is still only one conversion
schedule; the factory must produce a Pringlizer.  If $n \geq 2$, then
every conversion schedule is one of the following:

\begin{enumerate}
\item A Pringlizer followed by a conversion schedule for $n-1$ Fritolators.
\item A Tostitomatic followed by a conversion schedule for $n-2$ Fritolators.
\item A Santitotron followed by a conversion schedule for $n-2$ Fritolators.
\end{enumerate}

Thus, for a fleet of $n \geq 2$ Fritolators, there are $x_{n-1} + 2
x_{n-2}$ conversion schedules.  In summary:

\begin{eqnarray*}
x_0 & = & 1 \\
x_1 & = & 1 \\
x_n & = & x_{n-1} + 2 x_{n-2} \quad \text{(for $n \geq 2$)}
\end{eqnarray*}
}

\problempart Find a closed-form expression for $x_n$, the
number of conversion schedules for a fleet of $n$ Fritolators.

\solution{ The characteristic equation is $r^2 - r - 2 = 0$.  The
roots of this equation are $r = 2$ and $r = -1$.  The general form of
the solution is therefore

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

Substituting the base cases into this general form gives two linear
equations:

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

The solution to this system of equations is $A = \frac{2}{3}$ and $B =
\frac{1}{3}$.  Plugging these constants back into the general form of
the solution gives the exact solution:

\begin{eqnarray*}
x_n	& = &	\frac{2}{3} \cdot 2^n + \frac{1}{3} \cdot (-1)^n
\end{eqnarray*}
}
\end{problemparts}


\fi


\end{problems}

\end{document}

