\documentclass[12pt]{article}
\usepackage[Mickael]{ammaths}

\begin{document}

\en
\module{Tiling with trominos}{3}{17}{2 periods}
\nocouleur

\prereq{Polyominos (done in year II).}

\object{\begin{itemize}
        \item First introduction to the concept of proof by induction.
	\end{itemize}}

\mater{\begin{itemize}
	\item Lesson with the proofs for $n=5$ and $n=2^k$.
	\item Eight chessboards.
	\item Eight times (21 trominoes plus one black monomino).
	\item Beamer.
	\end{itemize}}

\modpart{First examples}{55 mins}

\begin{quote}
Is it possible to tile a deficient $n$-board with trominoes ?
\end{quote}

The problem is exposed and students, working in groups, try to solve it for the following values of $n$, in the exact order given below.

\begin{enumerate}
\item $n=2$ ;
\item $n=3$ ;
\item $n=3k$ ;
\item $n=4$ ;
\item $n=5$ ;
\item $n=7$ ;
\item $n=8$ ;
\item $n=16$.
\end{enumerate}

\modpart{The $n=5$ case}{20 mins}

The case $n=5$ is studied thoroughly, and the proof is given.

\modpart{The $n=2^k$ case}{35 mins}

The case $n=2^k$ is studied thoroughly, and the proof is given.

\pagebreak

\moddocdis{Tiling with trominos}{3}{17}{Lesson}

The tromino puzzle is a famous problem in recreational mathematics, that was notably studied by Solomon R. Golomb. 

\bigskip

\defi{Trominoe}{A \emph{tromino} is a shape made up of three $1\times 1$ squares assembled
as shown below :
\begin{center}
\begin{pspicture}(0,0)(2,2)
	\pspolygon[linewidth=1.5pt,fillstyle=solid,fillcolor=lightgray](0,0)(0,2)(2,2)(2,1)(1,1)(1,0)
	\psline[linewidth=1.5pt](0,1)(1,1)(1,2)
\end{pspicture}
\end{center}}

\defi{Deficient $n$-board}{A \emph{deficient $n$-board} is a square board made of $n$ times $n$ unit squares with one
square removed.}

The problem is easily stated as follows.

\begin{quote}
\bf Is it possible to tile a deficient $n$-board with trominoes ?
\end{quote}

\prop{Mutiples of $3$}{A deficient $n$-board is not tileable with trominoes if $n$ is a multiple of $3$. In all other
situations, the tiling may be possible.}

\proo{First, note that, as the tromino is made of three unit squares, a deficient board is not tileable with trominoes if its number of unit squares is not divisible by $3$. Consider the division with remainder of $n$ by $3$. The remainder is either $0$, $1$ or $2$, which means that $n$ is equal to $3k$, $3k+1$ or $3k+2$. 
\begin{itemize}
\item If $n=3k$, then $n^2=9k^2$ is a multiple of $3$. So $n^2-1$ is not a multiple of 3 and the deficient $3k$-board is not tileable with trominoes.
\item If $n=3k+1$, then $n^2=9k^2+6k+1$. So $n^2-1=9k^2+6k=3(3k^2+2k)$ is a multiple of 3 and the deficient $(3k+1)$-board may be tileable with trominoes.
\item If $n=3k+2$, then $n^2=9k^2+12k+4$. So $n^2-1=9k^2+12k+3=3(3k^2+4k+1)$ is a multiple of 3 and the deficient $(3k+2)$-board may be tileable with trominoes.
\end{itemize}
This condition is necesary but not sufficient : we don't know yet if for $n=3k+1$ and $n=3k+2$ an actual tiling exists.
}

For the next proposition, we consider the $5$-board and we define in the obvious way the coordinates of each unit square, starting with $(1,1)$ on the bottom left corner. The proof of this result is taken from an article by J. Marshall Ash and Solomon R. Golomb.

\pagebreak

\prop{The deficient $5$-board}{If the square $(i,j)$ is removed from the $5$-board where either $i$ or $j$ is even, then
the resulting shape is not tileable with trominoes. It's easy to check by trial and error that all other deficient
$5$-boards are tileable.}

\proo{Form a kind of checkerboard design by marking each of the nine squares
$${(1, 1), (1, 3), (1, 5), (3, 1), (3, 3), (3, 5), (5, 1), (5, 3), (5, 5)}$$
and assume that one of the 16 unmarked squares has been removed from the board. Then a proposed tiling of the deficient board must contain one tromino for each of the 9 marked squares, so that tiling must have area at least $9\times 3 = 27$, which is absurd since the deficient board is 24. Thus all 16 of the unmarked squares are bad.
}

A famous category of tileable boards is studied in the next theorem, first proved by Solomon R. Golomb in his 1965
book about {\sl Polyominoes}.

\bigskip

\theo{Deficient $2^k$-boards}{Any deficient $2^k$-board with $k\in\N^\star$ is tileable with trominoes.}

\proo{This proof is a famous example of proof by induction. We will first prove that it's true or $k=1$ and then that if
it's true for one value $k$, it's also true for $k+1$.\\
First, it's obvious that the deficient $2$-board is tileable with trominoes, as it is a tromino.\\
Now, suppose that the deficient $2^k$-board is tileable with trominoes, and consider the deficient $2^{k+1}$-board. This board can be cut into four quadrants, each one a $2^k$-board. The missing square has to be in one of the four quadrant. So from our induction hypothesis, that quadrant is tileable with trominoes. We are left with three quadrants to tile. We can then place one tromino at the center of the $2^{k+1}$-board so that each of its three squares is in a different quadrant.
\begin{center}
\psset{unit=0.3cm}
\begin{pspicture}(-12,-12)(12,12)
\pspolygon(-12,-12)(-12,12)(12,12)(12,-12)
\psline(-12,0)(12,0)
\psline(0,-12)(0,12)
\pspolygon[fillstyle=solid,fillcolor=black](5,7)(5,8)(6,8)(6,7)
\pspolygon[fillstyle=solid,fillcolor=lightgray](0,0)(0,1)(-1,1)(-1,-1)(1,-1)(1,0)
\psline(-1,0)(0,0)(0,-1)
\psline{<->}(13,-12)(13,12)
\uput[r](13,0){$2^{k+1}$}
\psline{<->}(-13,0)(-13,12)
\uput[l](-13,6.5){$2^k$}
\end{pspicture}
\end{center}


We must now tile three deficient $2^k$-boards, which we know is possible from our induction hypothesis. So the deficient
$2^{k+1}$-board is tileable with trominoes. As the property is true for $k=1$, it's also true for $k=2$, $k=3$, and so
on for all natural values of $k$.}





\pagebreak

\moddoc{Chessboard}

\begin{center}
\psset{unit=2cm}
\begin{pspicture}(0,0)(8,8)
\multido{\n=0+1}{9}{
\psline[linewidth=1.5pt](0,\n)(8,\n)
}
\multido{\d=0+1}{9}{
\psline[linewidth=1.5pt](\d,0)(\d,8)
}

\multido{\n=0+2}{4}{
	\multido{\d=0+2}{4}{
	\rput(\n,\d){
	\pspolygon[linewidth=1.5pt,fillstyle=solid,fillcolor=gray](0,0)(0,1)(1,1)(1,0)
	}}
}

\multido{\n=1+2}{4}{
	\multido{\d=1+2}{4}{
	\rput(\n,\d){
	\pspolygon[linewidth=1.5pt,fillstyle=solid,fillcolor=gray](0,0)(0,1)(1,1)(1,0)
	}}
}

\end{pspicture}
\end{center}

\pagebreak

\moddoc{Trominoes}


\psset{unit=2cm}
\begin{pspicture}(0,-1)(8,10)
\multido{\n=0+2}{4}{
	\multido{\d=0+2}{5}{
	\rput(\n,\d){
	\pspolygon[linewidth=1.5pt,fillstyle=solid,fillcolor=lightgray](0,0)(0,2)(2,2)(2,1)(1,1)(1,0)
	\psline[linewidth=1.5pt](0,1)(1,1)(1,2)}
	}
}
\pspolygon[linewidth=1.5pt,fillstyle=solid,fillcolor=lightgray](0,0)(1,0)(1,1)(2,1)(2,-1)(0,-1)
	\psline[linewidth=1.5pt](1,-1)(1,0)(2,0)
\pspolygon[linewidth=1.5pt,fillstyle=solid,fillcolor=black](2,-1)(3,-1)(3,0)(2,0)
\end{pspicture}


\end{document}
