\documentclass[10pt,envcountsect]{beamer}

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

\usepackage[english]{babel}
\usepackage[latin1]{inputenc}
\usepackage{times}
\usepackage[T1]{fontenc}
\usepackage{pstricks}
\usepackage{multicol}



\begin{document}

\title{Episode 19 -- How to cut a square grid ?}
\subtitle{European section -- Season 3}
\date{}

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


\begin{frame}{The problem}

\begin{center}

\psset{unit=0.8cm}
\begin{pspicture}(-1,-1)(8.5,5.5)
\psgrid[subgriddiv=0,gridlabels=0](0,0)(8,5)
\psline{<->}(0,-0.5)(8,-0.5)
\psline{<->}(-0.5,0)(-0.5,5)
\uput[d](4,-0.5){$n+1$}
\uput[l](-0.5,2.5){$m+1$}
\end{pspicture}

\pause

\bigskip

\large What is the best way to cut a rectangular grid ?

\end{center}


\end{frame}

\begin{frame}{Problem \#1}

\begin{center}
\LARGE How should you cut the grid so that the total \emph{length} cut is minimal ?
\end{center}


\end{frame}

\begin{frame}{Problem \#1}

\begin{center}
\psset{unit=0.8cm}
\begin{pspicture}(-1,-1)(8.5,5.5)
\psgrid[subgriddiv=0,gridlabels=0](0,0)(8,5)
\psline{<->}(0,-0.5)(8,-0.5)
\psline{<->}(-0.5,0)(-0.5,5)
\uput[d](4,-0.5){$n+1$}
\uput[l](-0.5,2.5){$m+1$}
\end{pspicture}

\pause

\bigskip

\large {\bf Solution :} \pause The total cut length is always $2mn+m+n$.

\end{center}

\end{frame}

\begin{frame}{Problem \#2}

\begin{center}
\LARGE How should you cut the grid so that the \emph{number of cuts} is minimal ?
\end{center}

\end{frame}

\begin{frame}{Problem \#2}

\begin{center}
\psset{unit=0.8cm}
\begin{pspicture}(-1,-1)(8.5,5.5)
\psgrid[subgriddiv=0,gridlabels=0](0,0)(8,5)
\psline{<->}(0,-0.5)(8,-0.5)
\psline{<->}(-0.5,0)(-0.5,5)
\uput[d](4,-0.5){$n+1$}
\uput[l](-0.5,2.5){$m+1$}
\end{pspicture}

\pause

\bigskip

\large {\bf Solution :} \pause The total number of cuts is always $mn+m+n$.

\end{center}

\end{frame}


\begin{frame}{Problem \#3}

\begin{center}
\LARGE How should you cut the grid so that the \emph{time} needed to cut it is minimal ?
\end{center}

\end{frame}

\begin{frame}{Problem \#3}

\begin{center}
\psset{unit=0.7cm}
\begin{pspicture}(-1,-1)(8.5,5.5)
\psgrid[subgriddiv=0,gridlabels=0](0,0)(8,5)
\psline{<->}(0,-0.5)(8,-0.5)
\psline{<->}(-0.5,0)(-0.5,5)
\uput[d](4,-0.5){$n+1$}
\uput[l](-0.5,2.5){$m+1$}
\end{pspicture}

\pause

\bigskip

\large {\bf Solution :} \pause The minimal cutting time is $mn+2m+n+1$.\pause\\
The solution is to start with a vertical grid\\ and cut into into strips.

\end{center}

\end{frame}


\end{document}
