\input{latex-macros/handout-preamble.tex}
\inhandout{
\decideaboutsolutions
\usesimpleproblems
}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Problem starts here
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


\begin{problem}
\PTAGfilename{CP0301_courtyard_tiling}
\PTAGhistory{S09_cp4t}
\PTAGkeywords{induction}
\bparts

\ppart Prove by induction that a $2^n \times 2^n$ courtyard with a $1
\times 1$ statue of Bill in {\em any position} can be covered with
$L$-shaped tiles.

\solution{Let $P(n)$ be the proposition that for every location of Bill in
a $2^n \times 2^n$ courtyard, there exists a tiling of the remainder.

\textbf{Base case:} $P(0)$ is true because Bill fills the whole courtyard.

\textbf{Inductive step:} Assume that $P(n)$ is true for some
$n \geq 0$; that is, for every location of Bill in a $2^n \times 2^n$
courtyard, there exists a tiling of the remainder.  Divide the
$2^{n+1} \times 2^{n+1}$ courtyard into four quadrants, each $2^n
\times 2^n$.  One quadrant contains Bill (\textbf{B} in the diagram
below).  Place a temporary Bill (\textbf{X} in the diagram) in each of
the three central squares lying outside this quadrant:

\begin{center}
\begin{picture}(148,148)(-20,-20)
\thinlines
\put(0,0){\line(1,0){128}}
\put(0,0){\line(0,1){128}}
\put(128,128){\line(-1,0){128}}
\put(128,128){\line(0,-1){128}}
\put(64,0){\line(0,1){128}}
\put(0,64){\line(1,0){128}}
\put(56,72){\makebox(0,0){\textbf{X}}}
\put(56,56){\makebox(0,0){\textbf{X}}}
\put(72,56){\makebox(0,0){\textbf{X}}}
\put(48,80){\line(1,0){16}}
\put(48,48){\line(1,0){32}}
\put(80,48){\line(0,1){16}}
\put(48,48){\line(0,1){32}}
\put(96,96){\framebox(16,16){\textbf{B}}}
\put(32,-10){\makebox(0,0){$2^n$}}
\put(96,-10){\makebox(0,0){$2^n$}}
\put(-10,32){\makebox(0,0){$2^n$}}
\put(-10,96){\makebox(0,0){$2^n$}}
\end{picture}
\end{center}

Now we can tile each of the four quadrants by the induction assumption.
Replacing the three temporary Bills with a single L-shaped tile completes
the job.  This proves that $P(n)$ implies $P(n+1)$ for all $n \geq 0$.
The theorem follows as a special case.

This proof has two nice properties.  First, not only does the argument
guarantee that a tiling exists, but also it gives a recursive procedure
for finding such a tiling.  Second, we have a stronger result: if Bill
wanted a statue on the edge of the courtyard, away from the pigeons, we
could accommodate him!}

\ppart {\em (Discussion Question)} In part~(a) we saw that it can be
easier to prove a stronger theorem.  Does this surprise you?  How would
you explain this phenomenon?

\solution{It might seem that it ought to be harder to prove a more general
theorem than a less general one, but sometimes not.  For example, the more
general result might actually be easier because it involves fewer
assumptions, and this can help in avoiding the complications of unnecessary
hypotheses.

But for an induction proof in particular, using a more general induction
hypothesis means we can make a stronger \emph{assumption} in the induction
step (namely, we can assume a stronger $P(n)$), which can make it easier
to prove the conclusion of the induction step (namely, $P(n+1)$).}

\eparts

\end{problem}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Problem ends here
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\input{latex-macros/handout-postamble.tex}
