\documentclass[10pt,envcountsect]{beamer}

\mode<presentation> {
  \usetheme{Warsaw}
}


\usepackage{ambeamer}



\begin{document}

\title{Episode 14 -- Problems about polyominoes}
\subtitle{European section -- Season 2}
\author{}
\date{}

\begin{frame}
  \titlepage
\end{frame}


\begin{frame}{Rep-tiles}

\large

{\bf A polyomino is a \emph{rep-tile} if a larger version of itself can
be tiled with only copies of the initial polyomino.

Find four non-trivial polyominoes rep-tiles.}\pause

\bigskip

The easiest way is to find polyominoes that can be used to make a square. Then we just have to reproduce this square as in the initial polymino.

\end{frame}

\begin{frame}{The L-triomino}

\begin{center}
\includegraphics[scale=0.5]{images/Ltriominorep.eps}
\end{center}

\end{frame}

\begin{frame}{The L-tetromino}

\begin{center}
\includegraphics[scale=0.75,angle=270]{images/Ltetrominorep.eps}
\end{center}

\end{frame}

\begin{frame}{The T-tetromino}

\begin{center}
\includegraphics[scale=0.7]{images/Ttetrominorep.eps}
\end{center}

\end{frame}
\begin{frame}{The P-pentomino}

\begin{center}
\includegraphics[scale=0.3,angle=270]{images/Ppentominorep.eps}
\end{center}

\end{frame}


\begin{frame}{Tiling a rectangle with pentominoes}

\large

{\bf Find a rectangle tileable with the 12 pentominoes used exactly once.}\pause

One possibilty is the $6\times10$ rectangle pictured below. Other possibilities are $5\times 12$, $4\times 15$ or the $3\times 20$ that is the answer to another problem.
\begin{center}
\includegraphics[scale=0.75]{images/6x10rectangle.eps}
\end{center}


\end{frame}

\begin{frame}{Tiling a rectangle with the tetrominoes}

\large

{\bf Prove that it's impossible to tile a rectangle with the 5 tetrominoes used exactly once.}\pause

\bigskip

Any tileable rectangle should have an area of $5\times 4=20$. Color the squares of any rectangle of this area black and white, as on a chessboard. Obviously, there is the same number of black squares and white squares. 

\end{frame}

\begin{frame}{Tiling a rectangle with the tetrominoes}

\large 

Now color the squares of the 5 tetrominoes in the same way :

\begin{center}
\includegraphics[scale=0.75]{images/tetrominoescolor.eps}
\end{center}

Because of the T-tetromino, the number of black squares and the number of white squares will always be different. So it's impossible to tile a rectangle with the tetrominoes.

\end{frame}

\begin{frame}{Tiling a special rectangle with pentominoes}

\large

{\bf Tile a $3\times20$ rectangle with the 12 pentominoes used exactly once.%p.8
}\pause

\bigskip

There are only two solutions, one of them is pictured below. For the other solution, leave the four polyominoes on the left and the polyomino on the right and rotate the whole middle part.

\begin{center}
\includegraphics[scale=0.5]{images/3x20rectangle.eps}
\end{center}


\end{frame}

\begin{frame}{Three congruent groups of pentominoes}

\large


{\bf Divide the twelve pentominoes into three groups of four each. Find one 20-square region that \emph{each} of the three groups will cover.%p.13
}\pause

\bigskip

One solution is pictured below. There may be other solutions.
\begin{center}
\includegraphics[scale=0.4]{images/3congruentgroups.eps}
\end{center}


\end{frame}

\begin{frame}{Minimal region for the twelve pentominoes}

\large


{\bf Find a minimal region made of squares on which each of the 12 pentominoes can fit. %p.14
}\pause

\bigskip

Here are two possible answers. Each of the 12 pentominoes fits in any of these regions.
\begin{center}
\includegraphics[scale=0.8]{images/minimalregions.eps}
\end{center}


\end{frame}

\begin{frame}{A tromino or a tetromino on a chessboard}

\large


{\bf We've seen that you can tile a chessboard with dominoes. 

Can you do it with the I-tromino, or with the L-tromino~?}\pause

\bigskip

A tromino is made of three squares. So any region tileable with a tromino must have an area that is a mutiple of 3. It's not the case for a chessboard, as the area is $8\times 8=64=3\times 21+1$. So a chessboard is not tileable with trominoes (I or L). A further question is : what about a chessboard with one square removed ?

\end{frame}

\begin{frame}{A tromino or a tetromino on a chessboard}

\large

{\bf Which tetrominoes can be used to tile a complete chessboard ? %p.6
}\pause

\bigskip

The I, L, O and T tetrominoes tile a $4\times 4$ square, to they also tile a chessboard.
\begin{center}
\includegraphics[scale=0.5]{images/tetrotilechess.eps}
\end{center}

\end{frame}

\begin{frame}{Triplication of pentominoes}

\large

{\bf Pick a pentomino, then use nine of the other pentominoes to construct a scale model, three times as wide and three times as high as the given piece.%p.8
}\pause

\bigskip

Below are show the triplications of the V pentomino and the X pentomino. Other triplications are possible.
\begin{center}
\includegraphics[scale=0.4]{images/triplication.eps}
\end{center}

\end{frame}

\begin{frame}{Pentominoes on an amputated chessboard}

\large

{\bf Cover a chessboard with the four corners missing with the 12 pentominoes used exactly once.%p.7
}\pause

\bigskip

Here is one solution. Other positions of the four missing squares are possible, including the next one, where the four missing squares make the square tetromino.
\begin{center}
\includegraphics[scale=0.5]{images/pentoonchess.eps}
\end{center}

\end{frame}

\begin{frame}{Pentominoes and a tetromino on a chessboard}

\large

{\bf Cover a chessboard with the twelve pentominoes and the square tetromino.%p.7
}\pause

A simple trick is to combine the square tetromino with the V pentomino to make a $3\times 3$ square. Then all we have to do is tile the remaining portion of the chessboard with the 11 other pentominoes. There are many ways to do so, below is one example.
\begin{center}
\includegraphics[scale=0.5]{images/pento+tetroonchess.eps}
\end{center}

\end{frame}

\begin{frame}{Three 3$\times$7 rectangles}

\large

{\bf Divide the twelve pentominoes into three groups of four each. To each group add a monomino and form a $3\times 7$ rectangle.%p.14
}\pause

Here is the only solution. The proof that no other solution is possible starts from the only possibility for the U and X pentominoes.

\begin{center}
\includegraphics[scale=0.5]{images/3x7rectangles.eps}
\end{center}


\end{frame}

\begin{frame}{Tetrominoes and a pentomino on a square board}

\large

{\bf Cover a  5$\times$5 board with the five tetrominoes and one pentomino.%p.17
}\pause

\bigskip

Below are shown two possibilities. There may be more.
\begin{center}
\includegraphics[scale=0.7]{images/5x5square.eps}
\end{center}

\end{frame}


\end{document}
