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

\begin{document}

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

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


\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{!}{1in}{\includegraphics{tiling1.eps}}}
\bigskip

We can solve this problem using linear recurrences.

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

\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

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

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

\end{problemparts}


\end{problems}

\end{document}

