\documentstyle[12pt,twoside,macpsfig]{article}
\input{macros-course}

\begin{document}

\handout{ps1-addendum}{Addendum to Problem Set 1}{February 4, 1994}
\pset{1}

\medskip

A few changes have been made in Problem Set number~1
in order to provide you with additional information.
Problem~O1-9 is reprinted here for your convenience
with an addition made in boldface. 
Problem~W1-11 has been entirely rewritten.

\medskip

\begin{problems}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\pnumset{9}
\oproblem For any integer $n\ge 3$, consider a simple, not
necessarily convex, polygon of $n$
vertices drawn in the plane.  (A polygon is \defi{simple} if it does
not cross itself.)  An \defi{\boldmath $n$-gon} is a polygon with $n$
vertices.  A \defi{triangulation} of an $n$-gon $P$ is a partition of
the interior of $P$ into triangles such that the vertices of any such
triangle are vertices of $P$.
{\bf You may assume that any simple polygon has a chord, i.e. a
line connecting two vertices of the polygon, which lies in the
interior of the polygon and which separates the polygon into
two other simple polygons.}

\begin{problemparts}

\problempart Use induction to show that any triangulation of an
$n$-gon is comprised of exactly $n-2$ triangles.

\problempart Using the fact the sum of the interior angles of a
triangle is $\pi$, give a formula for the sum of the interior angles
of an $n$-gon.  Prove that your formula is correct.

\end{problemparts}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\newpage

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\pnumset{11}
\wproblem

Consider a simple polygon drawn with vertices on the integer
$\integers\times\integers$ lattices, as is shown in
Figure~\ref{fig:picks}.  Let $i$ be the total number of lattice points
in the interior of the polygon, and let $b$ be the total number of
lattice points on the boundary.

\begin{problemparts}

\problempart
We say a rectangle is \defi{rectilinearly oriented} if its edges are parallel
to the $x$ and $y$ axes. For the polygons considered here, this
implies that the edges lie along rows or columns of lattice points.
Prove that the area of any rectilinearly oriented rectangle is $i + b/2 -1$
where again $i$ is the number of lattice points interior to the
rectangle, and $b$ is the number of lattice points on the rectangle's
boundary.

\problempart
We say a right triangle is rectilinearly oriented if its two legs are
parallel to the $x$ and $y$ axes.
Prove that the area of any rectilinearly oriented right triangle is $i+b/2-1$.
{\hint{Assume there are $r$ points on the hypotenuse. It turns out that the
area calculation may be shown to be independent of $r$.}}

\problempart
Prove that any triangle (with vertices on the lattice)
has area $i + b/2 -1$ by inscribing it in a rectilinearly
oriented rectangle.

\problempart
Prove that any simple lattice polygon has area $i+b/2-1$.

\end{problemparts}


\begin{figure}[h]
\centerline{\psfig{figure=figures/picks.ps,height=2in}}
\figcaption{A simple polygon in the lattice $\integers\times\integers$,
with 15 lattice points in its interior, 10 lattice points on its
boundary and area 19.}
\label{fig:picks}
\end{figure}



\end{problems}


\end{document}


