\documentstyle[11pt,epic,eepic]{article}

\begin{document}

6.042J/18.062J: Mathematics for Computer Science

\begin{center}
\Large\bf Tutorial 1

\large Solution to problem 1 
\end{center}


The first problem of Tutorial 1 admitted several solutions.  Here we
present one of the particularly interesting ones.  First of all, we
recall the problem.

\vskip 1cm
{\em 
\noindent {\bf Problem T}

Every $2^k$ by $2^k$ chessboard with the
upper-right central square removed 
can be tiled with $L$ shaped tiles.
}
\vskip 1cm

We want to solve problem $T$ by induction on $n$.
In order to prove the desired property,
we will use a ``trick'' that sometimes greatly simplifies
proofs by induction.
The trick is to prove a stronger assertion than that
required by the problem.
In this case, we prove that any $2^n\times 2^n$ 
chessboard with one 
square removed can be tiled, regardless of where
the hole is positioned.

\begin{description}
 \item[BASE CASE] for $n=0$ we have a $1\times 1$ chessboard
   whose unique square has been removed.
   The property holds vacuously since there is nothing to tile.

 \item[INDUCTIVE STEP]
   Assume we can tile any $2^n\times 2^n$ board with 
   one square removed.
   We want to tile a board of size $2^{n+1}\times 2^{n+1}$.
   Divide the board into four quadrants, each of wich is 
   of size $2^n\times 2^n$.
   One of these chessboards contains the hole and can be 
   tiled by inductive hypothesis.
   Now temporarily remove the square from each of 
   the three other 
   $2^n\times 2^n$ chessboards
   that has the center of the original 
   $2^{n+1}\times 2^{n+1}$ chessboard as one of its corners.

\begin{center}
\setlength{\unitlength}{0.5cm}
\begin{picture}(8,8)
\thicklines
\put(0,0){\line(0,1){8}}
\put(8,0){\line(0,1){8}}
\put(0,0){\line(1,0){8}}
\put(0,8){\line(1,0){8}}

\put(0,4){\line(1,0){4}}
\put(4,0){\line(0,1){4}}
\put(3,4){\line(0,1){1}}
\put(3,5){\line(1,0){2}}
\put(5,5){\line(0,-1){2}}
\put(5,3){\line(-1,0){1}}
\put(4,5){\line(0,1){3}}
\put(5,4){\line(1,0){3}}

\put(1,1){\line(0,1){1}}
\put(2,1){\line(0,1){1}}
\put(1,1){\line(1,0){1}}
\put(1,2){\line(1,0){1}}

\end{picture}
\end{center}

   The resulting $2^n\times 2^n$ chessboards with one 
   square removed can be tiled by inductive hypothesis.
   Furthermore the three squares that were temporarily removed 
   can be covered with one tile.
   Hence the entire $2^{n+1}\times 2^{n+1}$ board can be tiled
   with L-shaped pieces.
\end{description}

\end{document}
