\documentclass[10pt,envcountsect]{beamer}

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

\usepackage{ambeamer}
\usepackage{etex}
\usetikz


\begin{document}

\title{Episode 13 -- Polyominoes}
\subtitle{European section -- Season 2}
\author{}
\date{}

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


\begin{frame}{Polyomino, a general definition}

\defi{Polyomino}{A \emph{polyomino} is a polyform with the square as its base form. It is a connected shape formed as
the union of one or more identical squares in distinct locations on
the plane, such that every square can be connected to every other
square through a sequence of shared edges (i.e., shapes connected
only through shared corners of squares are not permitted).
}

\begin{center}
\begin{tabular}{cc}
\begin{pspicture}(0,0)(5,3)
\rput(0,0){\pspolygon[fillstyle=solid,fillcolor=gray](0,0)(1,0)(1,1)(0,1)}
\rput(1,0){\pspolygon[fillstyle=solid,fillcolor=gray](0,0)(1,0)(1,1)(0,1)}
\rput(2,0){\pspolygon[fillstyle=solid,fillcolor=gray](0,0)(1,0)(1,1)(0,1)}
\rput(2,1){\pspolygon[fillstyle=solid,fillcolor=gray](0,0)(1,0)(1,1)(0,1)}
\rput(3,1){\pspolygon[fillstyle=solid,fillcolor=gray](0,0)(1,0)(1,1)(0,1)}
\rput(3,2){\pspolygon[fillstyle=solid,fillcolor=gray](0,0)(1,0)(1,1)(0,1)}
\rput(4,2){\pspolygon[fillstyle=solid,fillcolor=gray](0,0)(1,0)(1,1)(0,1)}
\end{pspicture} &
\begin{pspicture}(0,0)(4,3)
\rput(0,0){\pspolygon[fillstyle=solid,fillcolor=gray](0,0)(1,0)(1,1)(0,1)}
\rput(1,0){\pspolygon[fillstyle=solid,fillcolor=gray](0,0)(1,0)(1,1)(0,1)}
\rput(2,0){\pspolygon[fillstyle=solid,fillcolor=gray](0,0)(1,0)(1,1)(0,1)}
\rput(2,1){\pspolygon[fillstyle=solid,fillcolor=gray](0,0)(1,0)(1,1)(0,1)}
\rput(3,1){\pspolygon[fillstyle=solid,fillcolor=gray](0,0)(1,0)(1,1)(0,1)}
\rput(3,2){\pspolygon[fillstyle=solid,fillcolor=gray](0,0)(1,0)(1,1)(0,1)}
\rput(1,2){\pspolygon[fillstyle=solid,fillcolor=gray](0,0)(1,0)(1,1)(0,1)}
\end{pspicture} \\
This is a polyomino. &  
This is not a polyomino.\\
\end{tabular}
\end{center}


\end{frame}

\begin{frame}{The various types of polyominoes}

\large

\defi{Small polyominos}{
A \emph{monomino} is made of just one square, \emph{domino}
is made of two, a \emph{triomino} of three and so on for
\emph{tetrominoes}, \emph{pentominoes}, \emph{hexominoes},
etc.}

In this lesson, we will work on \emph{free} polyominoes, that are
considered different from each other as long as none is a
translation, rotation, or reflection of another.



\end{frame}

\begin{frame}{The various types of polyominoes}

\large

\begin{block}{Problem 1}
    It's easy to see that there is only one free monomino and one free domino. Enumerate and draw all the triominoes, tetrominoes and pentominoes.
    \end{block}

\end{frame}

\begin{frame}{The 2 free triominoes}
\begin{center}
\includegraphics[scale=3]{images/trominoi.eps}
\includegraphics[scale=3]{images/trominov.eps}
\end{center}
\end{frame}

\begin{frame}{The 5 free tetrominoes}
\begin{center}
\includegraphics[scale=0.75]{images/Tetrominoes.eps}
\end{center}
\end{frame}

\begin{frame}{The 12 free pentominoes}
\begin{center}
\includegraphics[scale=0.65]{images/Pentominoes.eps}
\end{center}
\end{frame}


\begin{frame}{Order}

\large

\defi{Order of a polyomino}{
The \emph{order} of a polyomino is the number of copies of itself
you need to build a rectangle.}\pause

    \begin{block}{Problem 2}
    The monomino, the domino and the I-triomino are clearly of
    order $1$.\\ 
    Find out the orders of all the others triominoes, tetrominoes
    and pentominoes.
    \end{block}\pause

    \begin{block}{Problem 3}
    Can you think of a polymino of order $3$ ?
    \end{block}

\end{frame}

\begin{frame}{Some obvious orders}

\large

\begin{itemize}
\item The I-tetromino has order 1.
\item The O-tetromino has order 1.
\item The L-tetromino has order 2.
\item The S-tetromino has an infinite order.
\item The P-pentomino has order 2.
\item The L-pentomino has order 2.
\end{itemize}
\end{frame}


\begin{frame}{The T-tetromino has order 4.}
\begin{center}
\includegraphics[scale=1.3]{images/T-tetromino-order4.eps}
\end{center}
\end{frame}

\begin{frame}{What is the order of the Y-pentomino ?}
\begin{center}
\includegraphics[scale=1.5]{images/Y-pentomino.eps} 
\end{center}
\end{frame}

\begin{frame}{The Y-pentomino has order 10.}
\begin{center}
\includegraphics[scale=1.3]{images/Y-pentomino-order10.eps} 
\end{center}
\end{frame}

\begin{frame}{What about the others ?}
\Large

All the other pentominoes have an infinite order.
\end{frame}


\begin{frame}{What is the order of the G-hexomino ?}
\begin{center}
\includegraphics[scale=1.5]{images/G-hexomino.eps} 
\end{center}
\end{frame}


% \begin{frame}{The G-hexomino has order 18.}
% \begin{center}
% \includegraphics[scale=1]{images/G6-12x9.eps} 
% \end{center}
% \end{frame}

\begin{frame}{What is the order of the Y-hexomino ?}
\begin{center}
\includegraphics[scale=1.5]{images/Y-hexomino.eps} 
\end{center}
\end{frame}

\begin{frame}{The Y-hexomino has order 92.}
\begin{center}
\includegraphics[scale=0.4]{images/Y6-24x23.eps} 
\end{center}
\end{frame}

\begin{frame}{No known polymino has order 3}
\begin{center}
\huge Did you find one ?
\end{center}
\end{frame}

\end{document}
