\documentclass[11pt,twoside]{article}    
\usepackage{latex-macros/course}% !! use the macros 

%\backwardscompatibility        % !! use for backwards compatibility
%\showsolutions                 % !! use to force solutions & skip query
%\hidesolutions                 % !! use to force no solutions & skip query

\begin{document} 
\inclassproblems{3, Wed.}                    % !! start the paper


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

\begin{problem}
An {\em autocity} is a city with a road to some other town.

\begin{claim}
You can drive between every pair of autocities in our world.
\end{claim}

\begin{proof}
The proof is by induction $n$, the number of autocities in the world.
Let $P(n)$ be the proposition that in all possible worlds with $n$
autocities, you can drive between every pair of autocities.

Since a world with $n = 1$ autocities can not exist, we begin by
proving $P(2)$.  In this case, only one configuration is possible, and
the claim clearly holds:

\bigskip
\centerline{\resizebox{!}{0.75in}{\includegraphics{2-autocities}}}
\bigskip

Next, we show that $P(n)$ implies $P(n + 1)$ for all $n \geq 2$.  As
usual, we assume that $P(n)$ is true and show that $P(n + 1)$
logically follows.  By the assumption $P(n)$, you can drive between
every pair of autocities in a world with $n$ autocities.  Now we add
one more autocity (call it ``city $A$'') to form a world with $n + 1$
autocities:

\bigskip
\centerline{\resizebox{!}{1.5in}{\includegraphics{n-autocities}}}
\bigskip

All that remains is to prove that you can drive from city $A$ to any
other city.  Since $A$ is an autocity, you can drive from $A$ to at
least one of the other $n$ autocities (call that one ``city $B$'').
Then, from city $B$, you can drive to any of the others, by our
assumption $P(n)$.  This shows that $P(n + 1)$ is true.

By induction, $P(n)$ is true for all $n \geq 2$.  Thus, in particular,
you can drive between any pair of autocities in our world.
\end{proof}

Either underline and explain the first error in the proof or else take
a road trip from here to Honolulu and send us all back a postcard.

\solution{The first error is the statement, ``This shows that $P(n + 1)$
is true.''  We showed that in every world with $n + 1$ autocities
\emph{which can be constructed by adding one autocity to a world with $n$
autocities}, you can drive between any two autocities.  However, not all
worlds with $n + 1$ autocities can be constructed in this way.  Here is an
example:

\bigskip
\centerline{\resizebox{!}{0.75in}{\includegraphics{4-autocities}}}
\bigskip

Therefore, we have not shown that $P(n)$ implies $P(n + 1)$ and the
induction argument is broken.

Instead of starting with $n$ autocities and \emph{adding} one, a proper
way to organize the proof would be to start by considering $n+1$
autocities and \emph{remove} one to obtain a set of $n$ to which the
induction hypothesis will hopefully apply.  In this case, removing an auto
city may break the ``autocityness'' of one of the remaining cities, so the
induction hypothesis in general won't apply -- which is, of course,
inevitable because the claim to be proved is false.

This blunder of assuming an arbitrary configuration of $n+1$ objects can
be built up from a good configuration of $n$ objects in some particular
way is known as ``buildup error.''
}

\end{problem}

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

\instatements{\newpage}

\begin{problem}
A {\em winning configuration} in the game of Mini-Tetris is a complete
tiling of a $2 \times n$ board using only the three shapes shown
below:

\bigskip
\centerline{\includegraphics[height=0.5in]{rec2-tetrispieces}}
\bigskip

For example, here are several possible winning configurations on a $2
\times 5$ board:

\bigskip
\centerline{\includegraphics[height=1.25in]{rec2-2x5wins}}
\bigskip

\begin{problemparts}

\problempart Let $T_n$ denote the number of different winning
configurations on a $2 \times n$ board.  Determine the values of
$T_1$, $T_2$, and $T_3$.

\solution[\vspace{3in}]{
$T_1 = 1$, $T_2 = 3$, and $T_3 = 5$.
}

\newpage

\problempart Express $T_n$ in terms of $T_{n-1}$ and $T_{n-2}$.

\solution[\vspace{3in}]{Every winning configuration on a $2 \times n$
board is of one of the following three types:

\bigskip
\centerline{\includegraphics[height=2in]{rec2-types}}
\bigskip

\noindent There are $T_{n-1}$ winning configurations of the first
type, and there are $T_{n-2}$ winning configurations of the second and
third types.  Overall, the number of winning configurations on a $2
\times n$ board is:

\begin{eqnarray*}
T_n & = & T_{n-1} + 2 T_{n-2}
\end{eqnarray*}
}

\problempart Prove that the number of winning configurations on a $2
\times n$ Mini-Tetris board ($n \geq 1$) is:

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

\solution{The proof is by strong induction on $n$, with the induction
hypothesis $T_n = (2^{n+1}+(-1)^n) / 3$.  The hypothesis is true for
$n = 1$ and $n = 2$, since we determined above that $T_1 = 1 =
(2^{1+1}+(-1)^1)/3$ and $T_2 = 3 = (2^{2+1}+(-1)^2)/3$.

Now suppose $n \geq 2$ and assume that the hypothesis holds for all $k
< n$.  Starting from the equation derived in the preceding problem
part, we have:

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

\noindent We use the induction hypothesis twice in the second step,
and then simplify in the third and fourth steps.  This completes the
inductive step.  By strong induction, the hypothesis holds for all $n
\geq 1$.}

\end{problemparts}

\end{problem}

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

\instatements{\newpage}

\begin{problem}
Three pirates are considering an attack on the {\em Pi\~{n}ata}, a
Spanish galleon laden with $n \geq 20$ pieces of gold.  Redbeard
insists that his share of the treasure be a multiple of 5 gold pieces,
Bluebeard insists that his share be a multiple of 7 gold pieces, and
Blackbeard demands a multiple of 9 gold pieces.  Furthermore, no
pirate can tolerate treasure going to waste; if that is unavoidable,
the pirates will surely have a fatal quarrel.

For example, if there were 12 gold pieces aboard, then Redbeard could
take 5, Bluebeard 7, and Blackbeard 0.  However, if there were 13 gold
pieces aboard, then the pirates would kill each other.

Can the pirates safely attack the {\em Pi\~{n}ata}?  Use strong
induction to prove that your answer is correct.

\solution{The pirates can safely attack the Pi\~{n}ata.  The proof is
by strong induction on $n$, the number of gold pieces aboard.

Let $P(n)$ be the proposition that $n$ is of the form $5x + 7y + 9z$,
where $x$, $y$, and $z$ are integers.  First, we show that $P(n)$
holds for all $n$ between 20 and 24.

\begin{eqnarray*}
20 & = & 5 \cdot 4 + 7 \cdot 0 + 9 \cdot 0 \\
21 & = & 5 \cdot 1 + 7 \cdot 1 + 9 \cdot 1 \\
22 & = & 5 \cdot 3 + 7 \cdot 1 + 9 \cdot 0 \\
23 & = & 5 \cdot 0 + 7 \cdot 2 + 9 \cdot 1 \\
24 & = & 5 \cdot 2 + 7 \cdot 2 + 9 \cdot 0
\end{eqnarray*}

Now we must show that $P(n)$ is true assuming that $P(20), \ldots, P(n
- 1)$ are all true, where $n \geq 25$.  Then, in particular, we know
that $P(n - 5)$ is true; that is, there is a way of dividing up $n -
5$ gold pieces among the three pirates with none going to waste.  We
can divide $n$ gold pieces in the same way, giving the 5 extras to
Redbeard.  This shows that $P(n)$ is true as well.  Therefore, $P(n)$
is true for all $n \geq 20$ by strong induction.}

\end{problem}

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

\end{document}
