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



\begin{document}

\module{Proving Pick's formula}{3}{02}{2 periods}
\en\nocouleur

%\prereq{}

\object{\begin{itemize}
        \item Find, step by step, a proof of Pick's formula.
	\end{itemize}}

\mater{\begin{itemize}
	\item Lesson : Proof of Pick's formula.
	\item Beamer : Proof of Pick's formula.
	\item Paper for posters.
	\end{itemize}}

\modpart{Devise a plan for the proof}{10 mins}

A brainstorming session to devise a plan for the proof, moderated by the teacher.

\modpart{Part 1 : Prove that Pick's formula is additive}{45 mins}

The aim of this first part is to prove that 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$.

\modpart{Part 2 : Prove Pick's formula for any polygon}{55 mins}

Follow the steps : unit square, rectangle, right-angled triangle, any triangle, any convex polygon.

\pagebreak

\moddocdis{Proof of Pick's formula}{3}{02}{Lesson}

\prop{}{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.}

\proo{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 we see that $$I_{PT}=I_P+I_T+(c-2)$$ and also $$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.
}

\lemma{Pick's formula is true for the unit square and for any rectangle with sides parallel to the axes.}

\proo{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.}

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

\proo{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*}
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 we also know from the previous Lemma that $\mathscr{A}_R=\frac12B_R+I_R-1$, so we deduce
$$2\mathscr{A}_{T}=\mathscr{A}_{R}=\frac12B_R+I_R-1=2(\frac12B_T+I_T-1)$$
which implies that the formula is true for triangle $T$ : $\mathscr{A}_{T}=\frac12B_T+I_T-1$.}

\lemma{Pick's formula holds for any lattice triangle.}

\begin{multicols}{2}

\proo{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. 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.}

\begin{center}
\newrgbcolor{qrqrqr}{0 0 0}
\psset{xunit=0.75cm,yunit=0.75cm,algebraic=true,dotstyle=*,dotsize=3pt 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{multicols}

\begin{multicols}{2}

\theo{}{Pick's formula is true for any lattice polygon.}



\proo{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.75cm,dotstyle=*,dotsize=3pt 0,linewidth=0.8pt,arrowsize=3pt 2,arrowinset=0.25}
\begin{pspicture*}(1.24,-2.42)(10.18,4.64)
\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{multicols}

\end{document}
