\documentclass[10pt,envcountsect]{beamer}

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

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

\newtheorem{proposition}[theorem]{Proposition}

\begin{document}

\title{Episode 02 -- Proving Pick's formula}
\subtitle{European section -- Season 3}
\date{}

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

\begin{frame}
\begin{proposition}
Pick's formula is additive :  if $P$ and $T$ are two polygons with one edge in common, and if Pick's formula holds for $P$ and $T$, it also holds for the polygon $PT$ obtained by adding $P$ and $T$. This is also true for more than two polygons.
\end{proposition}
\end{frame}

\begin{frame}
\begin{proof}
First, it's obvious from the definitions that $\mathscr{A}_{PT}=\mathscr{A}_{P}+\mathscr{A}_{T}$. Then, suppose that Pick's formula holds for the two polygons, and we use the same notations as in the previous session. Let's call $c$ the number of boundary points in common. Then $I_{PT}=I_P+I_T+(c-2)$ and $B_{PT}=B_P+B_T-2(c-2)-2.$
We can deduce that 
\begin{eqnarray*}
&& \frac12B_{PT}+I_{PT}-1\\
 &=& \frac12\left(B_P+B_T-2(c-2)-2\right)+I_P+I_T+(c-2)-1\\
				      &=& \frac12B_P+\frac12B_T-(c-2)-1+I_P+I_T+(c-2)-1\\
				      &=& \frac12B_P+I_P-1+\frac12B_T+I_T-1\\
				      &=& \mathscr{A}_{P}+\mathscr{A}_{T}\\
				      &=& \mathscr{A}_{PT}
\end{eqnarray*}
So the formula also holds for the polygon $PT$. It's easy to extand this result to more than two polygons.
\end{proof}
\end{frame}

\begin{frame}
\begin{lemma}
Pick's formula is true for the unit square and for any rectangle with sides parallel to the axes.
\end{lemma}\pause
\begin{proof}
For a unit square $S$, we have $\mathscr{A}_S=1$, $B_S=4$ and $I_S=0$. As $\frac12B_S+I_S-1=1$, the formula holds. Then, any rectangle with sides parallel to the axes is made of unit squares, so from Proposition 1, the formula also holds for these rectangles.
\end{proof}

\end{frame}

\begin{frame}
\begin{lemma}
Pick's formula holds for any right-angled triangle with its perpendicular sides parallel to the axes.
\end{lemma}

\pause

\begin{block}{Proof.}
Any such triangle $T$ is one half of a rectange $R$ with sides parallel to the axes, cut diagonally, and it's clear that $2\mathscr{A}_{T}=\mathscr{A}_{R}$. Let's call $n$ and $m$ the number of points on each side of the rectangle and $d$ the number of points on the diagonal. Then, a simple analysis gives
\begin{eqnarray*}
B_R=2(n+m-2) &\textrm{ and }& I_R=(n-2)(m-2) \\
B_T=n+m-1+d &\textrm{ and }& I_T=\frac{(n-2)(m-2)-d}{2}
\end{eqnarray*}
\end{block}

\end{frame}


\begin{frame}
\begin{proof}
Then we can compute on one hand
\begin{eqnarray*}
\frac12B_R+I_R-1 &=& n+m-2+(n-2)(m-2)-1 \\
			   &=& n+m-3+(n-2)(m-2) 
\end{eqnarray*}
and on the other hand
\begin{eqnarray*}
2(\frac12B_T+I_T-1) &=& B_T+2I_T-2 \\
			       &=& n+m-1+d+(n-2)(m-2)-d-2\\ 
			       &=& n+m-3+(n-2)(m-2)
\end{eqnarray*}
The two expressions are equal, and $\mathscr{A}_R=\frac12B_R+I_R-1$, so
$$2\mathscr{A}_{T}=\mathscr{A}_{R}=\frac12B_R+I_R-1=2(\frac12B_T+I_T-1)$$
so the formula is true for triangle $T$ : $\mathscr{A}_{T}=\frac12B_T+I_T-1$.
\end{proof}

\end{frame}

\begin{frame}
\begin{lemma}
Pick's formula holds for any lattice triangle.
\end{lemma}\pause

\begin{block}{Proof.}
This lemma is proved by a graphical argument : any lattice triangle can be turned into a rectangle by attaching at most three suitable right-angled triangles and one rectangle. 
\begin{center}
\newrgbcolor{qrqrqr}{0 0 0}
\psset{xunit=0.6cm,yunit=0.6cm,dotstyle=*,dotsize=2pt 0,linewidth=0.8pt,arrowsize=3pt 2,arrowinset=0.25}
\begin{pspicture*}(-1.32,-1.42)(8.5,5.38)
\pspolygon[linecolor=qrqrqr,fillcolor=lightgray,fillstyle=solid](1,3)(1,0)(5,0)
\pspolygon[linecolor=qrqrqr,fillcolor=lightgray,fillstyle=solid](1,4)(1,3)(6,4)
\pspolygon[linecolor=qrqrqr,fillcolor=lightgray,fillstyle=solid](6,4)(6,0)(5,0)
\psline[linecolor=qrqrqr](1,3)(5,0)
\psline[linecolor=qrqrqr](5,0)(6,4)
\psline[linecolor=qrqrqr](6,4)(1,3)
\psline[linecolor=qrqrqr](1,3)(1,0)
\psline[linecolor=qrqrqr](1,0)(5,0)
\psline[linecolor=qrqrqr](5,0)(1,3)
\psline[linecolor=qrqrqr](1,4)(1,3)
\psline[linecolor=qrqrqr](1,3)(6,4)
\psline[linecolor=qrqrqr](6,4)(1,4)
\psline[linecolor=qrqrqr](6,4)(6,0)
\psline[linecolor=qrqrqr](6,0)(5,0)
\psline[linecolor=qrqrqr](5,0)(6,4)
\psdots[linecolor=qrqrqr](-1,5)
\psdots[linecolor=qrqrqr](0,5)
\psdots[linecolor=qrqrqr](1,5)
\psdots[linecolor=qrqrqr](2,5)
\psdots[linecolor=qrqrqr](3,5)
\psdots[linecolor=qrqrqr](4,5)
\psdots[linecolor=qrqrqr](5,5)
\psdots[linecolor=qrqrqr](6,5)
\psdots[linecolor=qrqrqr](7,5)
\psdots[linecolor=qrqrqr](8,5)
\psdots[linecolor=qrqrqr](8,4)
\psdots[linecolor=qrqrqr](8,3)
\psdots[linecolor=qrqrqr](8,2)
\psdots[linecolor=qrqrqr](8,1)
\psdots[linecolor=qrqrqr](8,0)
\psdots[linecolor=qrqrqr](8,-1)
\psdots[linecolor=qrqrqr](7,-1)
\psdots[linecolor=qrqrqr](7,0)
\psdots[linecolor=qrqrqr](7,1)
\psdots[linecolor=qrqrqr](7,2)
\psdots[linecolor=qrqrqr](7,3)
\psdots[linecolor=qrqrqr](7,4)
\psdots[linecolor=qrqrqr](6,4)
\psdots[linecolor=qrqrqr](6,3)
\psdots[linecolor=qrqrqr](6,2)
\psdots[linecolor=qrqrqr](6,1)
\psdots[linecolor=qrqrqr](6,0)
\psdots[linecolor=qrqrqr](6,-1)
\psdots[linecolor=qrqrqr](5,-1)
\psdots[linecolor=qrqrqr](5,0)
\psdots[linecolor=qrqrqr](5,1)
\psdots[linecolor=qrqrqr](5,2)
\psdots[linecolor=qrqrqr](5,3)
\psdots[linecolor=qrqrqr](5,4)
\psdots[linecolor=qrqrqr](4,4)
\psdots[linecolor=qrqrqr](4,3)
\psdots[linecolor=qrqrqr](4,2)
\psdots[linecolor=qrqrqr](4,1)
\psdots[linecolor=qrqrqr](4,0)
\psdots[linecolor=qrqrqr](4,-1)
\psdots[linecolor=qrqrqr](3,-1)
\psdots[linecolor=qrqrqr](3,0)
\psdots[linecolor=qrqrqr](3,1)
\psdots[linecolor=qrqrqr](3,2)
\psdots[linecolor=qrqrqr](3,3)
\psdots[linecolor=qrqrqr](3,4)
\psdots[linecolor=qrqrqr](2,4)
\psdots[linecolor=qrqrqr](2,3)
\psdots[linecolor=qrqrqr](2,2)
\psdots[linecolor=qrqrqr](2,1)
\psdots[linecolor=qrqrqr](2,0)
\psdots[linecolor=qrqrqr](2,-1)
\psdots[linecolor=qrqrqr](1,-1)
\psdots[linecolor=qrqrqr](1,0)
\psdots[linecolor=qrqrqr](1,1)
\psdots[linecolor=qrqrqr](1,2)
\psdots[linecolor=qrqrqr](1,3)
\psdots[linecolor=qrqrqr](1,4)
\psdots[linecolor=qrqrqr](0,4)
\psdots[linecolor=qrqrqr](0,3)
\psdots[linecolor=qrqrqr](0,2)
\psdots[linecolor=qrqrqr](0,1)
\psdots[linecolor=qrqrqr](0,0)
\psdots[linecolor=qrqrqr](0,-1)
\psdots[linecolor=qrqrqr](-1,-1)
\psdots[linecolor=qrqrqr](-1,0)
\psdots[linecolor=qrqrqr](-1,1)
\psdots[linecolor=qrqrqr](-1,2)
\psdots[linecolor=qrqrqr](-1,3)
\psdots[linecolor=qrqrqr](-1,4)
\psdots[linecolor=qrqrqr](2,4)
\end{pspicture*}
\end{center}

\end{block}

\end{frame}

\begin{frame}
\begin{proof}
\begin{center}
\newrgbcolor{qrqrqr}{0 0 0}
\psset{xunit=0.6cm,yunit=0.6cm,dotstyle=*,dotsize=2pt 0,linewidth=0.8pt,arrowsize=3pt 2,arrowinset=0.25}
\begin{pspicture*}(-1.32,-1.42)(8.5,5.38)
\pspolygon[linecolor=qrqrqr,fillcolor=lightgray,fillstyle=solid](1,3)(1,0)(5,0)
\pspolygon[linecolor=qrqrqr,fillcolor=lightgray,fillstyle=solid](1,4)(1,3)(6,4)
\pspolygon[linecolor=qrqrqr,fillcolor=lightgray,fillstyle=solid](6,4)(6,0)(5,0)
\psline[linecolor=qrqrqr](1,3)(5,0)
\psline[linecolor=qrqrqr](5,0)(6,4)
\psline[linecolor=qrqrqr](6,4)(1,3)
\psline[linecolor=qrqrqr](1,3)(1,0)
\psline[linecolor=qrqrqr](1,0)(5,0)
\psline[linecolor=qrqrqr](5,0)(1,3)
\psline[linecolor=qrqrqr](1,4)(1,3)
\psline[linecolor=qrqrqr](1,3)(6,4)
\psline[linecolor=qrqrqr](6,4)(1,4)
\psline[linecolor=qrqrqr](6,4)(6,0)
\psline[linecolor=qrqrqr](6,0)(5,0)
\psline[linecolor=qrqrqr](5,0)(6,4)
\psdots[linecolor=qrqrqr](-1,5)
\psdots[linecolor=qrqrqr](0,5)
\psdots[linecolor=qrqrqr](1,5)
\psdots[linecolor=qrqrqr](2,5)
\psdots[linecolor=qrqrqr](3,5)
\psdots[linecolor=qrqrqr](4,5)
\psdots[linecolor=qrqrqr](5,5)
\psdots[linecolor=qrqrqr](6,5)
\psdots[linecolor=qrqrqr](7,5)
\psdots[linecolor=qrqrqr](8,5)
\psdots[linecolor=qrqrqr](8,4)
\psdots[linecolor=qrqrqr](8,3)
\psdots[linecolor=qrqrqr](8,2)
\psdots[linecolor=qrqrqr](8,1)
\psdots[linecolor=qrqrqr](8,0)
\psdots[linecolor=qrqrqr](8,-1)
\psdots[linecolor=qrqrqr](7,-1)
\psdots[linecolor=qrqrqr](7,0)
\psdots[linecolor=qrqrqr](7,1)
\psdots[linecolor=qrqrqr](7,2)
\psdots[linecolor=qrqrqr](7,3)
\psdots[linecolor=qrqrqr](7,4)
\psdots[linecolor=qrqrqr](6,4)
\psdots[linecolor=qrqrqr](6,3)
\psdots[linecolor=qrqrqr](6,2)
\psdots[linecolor=qrqrqr](6,1)
\psdots[linecolor=qrqrqr](6,0)
\psdots[linecolor=qrqrqr](6,-1)
\psdots[linecolor=qrqrqr](5,-1)
\psdots[linecolor=qrqrqr](5,0)
\psdots[linecolor=qrqrqr](5,1)
\psdots[linecolor=qrqrqr](5,2)
\psdots[linecolor=qrqrqr](5,3)
\psdots[linecolor=qrqrqr](5,4)
\psdots[linecolor=qrqrqr](4,4)
\psdots[linecolor=qrqrqr](4,3)
\psdots[linecolor=qrqrqr](4,2)
\psdots[linecolor=qrqrqr](4,1)
\psdots[linecolor=qrqrqr](4,0)
\psdots[linecolor=qrqrqr](4,-1)
\psdots[linecolor=qrqrqr](3,-1)
\psdots[linecolor=qrqrqr](3,0)
\psdots[linecolor=qrqrqr](3,1)
\psdots[linecolor=qrqrqr](3,2)
\psdots[linecolor=qrqrqr](3,3)
\psdots[linecolor=qrqrqr](3,4)
\psdots[linecolor=qrqrqr](2,4)
\psdots[linecolor=qrqrqr](2,3)
\psdots[linecolor=qrqrqr](2,2)
\psdots[linecolor=qrqrqr](2,1)
\psdots[linecolor=qrqrqr](2,0)
\psdots[linecolor=qrqrqr](2,-1)
\psdots[linecolor=qrqrqr](1,-1)
\psdots[linecolor=qrqrqr](1,0)
\psdots[linecolor=qrqrqr](1,1)
\psdots[linecolor=qrqrqr](1,2)
\psdots[linecolor=qrqrqr](1,3)
\psdots[linecolor=qrqrqr](1,4)
\psdots[linecolor=qrqrqr](0,4)
\psdots[linecolor=qrqrqr](0,3)
\psdots[linecolor=qrqrqr](0,2)
\psdots[linecolor=qrqrqr](0,1)
\psdots[linecolor=qrqrqr](0,0)
\psdots[linecolor=qrqrqr](0,-1)
\psdots[linecolor=qrqrqr](-1,-1)
\psdots[linecolor=qrqrqr](-1,0)
\psdots[linecolor=qrqrqr](-1,1)
\psdots[linecolor=qrqrqr](-1,2)
\psdots[linecolor=qrqrqr](-1,3)
\psdots[linecolor=qrqrqr](-1,4)
\psdots[linecolor=qrqrqr](2,4)
\end{pspicture*}
\end{center}

Since the formula is correct for the right triangles and for the rectangle, it also follows for the original triangle. This last step uses the fact that if the theorem is true for the polygon PT and for the triangle T, then it's also true for P; this can be proved in the same way as propostion one.
\end{proof}

\end{frame}

\begin{frame}
\begin{theorem}
Pick's formula is true for any lattice polygon.
\end{theorem}\pause
\begin{proof}
This theorem follows from lemma 3, proposition 1 and the fact that any lattice polygon can be cut into
triangles (triangulated).

\begin{center}
 \newrgbcolor{qrqrqr}{0 0 0}
\psset{xunit=0.75cm,yunit=0.65cm,dotstyle=*,dotsize=3pt 0,linewidth=0.8pt,arrowsize=3pt 2,arrowinset=0.25}
\begin{pspicture*}(1.24,-1.8)(10.18,4.2)
\psline[linecolor=qrqrqr](2.08,0.62)(2.82,-1.72)
\psline[linecolor=qrqrqr](2.82,-1.72)(7.48,-0.36)
\psline[linecolor=qrqrqr](7.48,-0.36)(9.78,3.36)
\psline[linecolor=qrqrqr](9.78,3.36)(6.7,1.98)
\psline[linecolor=qrqrqr](6.7,1.98)(4.9,3.6)
\psline[linecolor=qrqrqr](4.9,3.6)(3.98,1.48)
\psline[linecolor=qrqrqr](3.98,1.48)(2.08,0.62)
\psline[linecolor=qrqrqr](2.82,-1.72)(3.98,1.48)
\psline[linecolor=qrqrqr](3.98,1.48)(7.48,-0.36)
\psline[linecolor=qrqrqr](6.7,1.98)(7.48,-0.36)
\psline[linecolor=qrqrqr](6.7,1.98)(3.98,1.48)
\psdots[linecolor=qrqrqr](2.08,0.62)
\psdots[linecolor=qrqrqr](2.82,-1.72)
\psdots[linecolor=qrqrqr](7.48,-0.36)
\psdots[linecolor=qrqrqr](9.78,3.36)
\psdots[linecolor=qrqrqr](6.7,1.98)
\psdots[linecolor=qrqrqr](4.9,3.6)
\psdots[linecolor=qrqrqr](3.98,1.48)
\end{pspicture*}
\end{center}


\end{proof}
\end{frame}





\end{document}
