Pick's Theorem
Pick's theorem gives a way to find the area of polygons in a plane whose endpoints have integer vertices.
Lattice Polygons
Lattice points are points whose coordinates are both integers, such as \((1,2), (-4, 11)\), and \((0,5)\). The set of all lattice points forms a grid. A lattice polygon is a shape made of straight lines whose vertices are all lattice points and Pick's theorem gives a formula for the area of a lattice polygon.
First, observe that for any lattice polygon \(P\), the polygon contains some lattice points on its boundary edges \((\)including the lattice points that are the vertices of \(P)\) and may contain some lattice points in its interior (not counting the points on the boundary). Let
\[\begin{align} B(P) &= \mbox{ number of points on the boundary of the polygon}\\ I(P) &= \mbox{ number of points in the interior of the polygon}. \end{align}\]
Pick's Theorem
Let \(P\) be a lattice polygon, let \(B(P)\) be the points on the boundary of the polygon, and let \(I(P)\) be the number of points in the interior of the polygon. Then
\[(\mbox{Area of the polygon } P) = I(P) + \frac{1}{2} B(P) -1.\]
Notice that Pick's theorem applies to any polygon, not only convex polygons.
For a rectangle \(R\) of length \(l\) and height \(h,\) there are \(B(R) = 2l + 2h\) points along the boundary of the rectangle, and \(I(R) = (l-1)(h-1) = lh - l - h + 1\) points in the interior of the rectangle. Applying Pick's theorem gives
\[\begin{align} \mbox{Area}(R) &= I(R) + \frac{1}{2} B(R) - 1\\ &= lh - l - h + 1 + \frac{1}{2} (2l + 2h) - 1\\ &= lh - l - h + 1 + l + h - 1\\ &= lh. \end{align}\]
Without Pick's theorem, we might calculate the area of a lattice polygon by decomposing the lattice polygon into triangles, computing the area of each triangle using the sine rule, and then summing the resulting triangle areas to obtain the area of the lattice polygon. As a powerful tool, the Shoelace theorem works side by side finding the area of any figure given the coordinates. Pick's theorem gives a way to find the area of a lattice polygon without performing all of these calculations. Pick's theorem also implies the following interesting corollaries:
The area of a lattice polygon is always an integer or half an integer.
Proof: By Pick's theorem, the area of a lattice polygon \(P\) is given by \( \mbox{Area}(P) = I(P) + \frac{1}{2} B(P) - 1.\) In a lattice polygon, the number of points in the interior of \(P\) and the number of points on the boundary of \(P\) are both integers. Then \( \mbox{Area}(P) = I(P) + \frac{1}{2} B(P) - 1\) is an integer if \(B(P)\) is even and is half an integer if \(B(P)\) is odd. \(_\square\)
It is impossible to draw an equilateral triangle as a lattice polygon.
Proof: Suppose we could draw an equilateral triangle as a lattice polygon with lattice vertices \(A\), \(B\) and \(C\) with side length \(s\). By distance formula and Pythagorean theorem, \(s^2\) represents the square of distance between any of these 2 vertices, and must be an integer. Also note that the area of an equilateral triangle can be expressed as \( \text{Area} = \frac{s^2 \sqrt3}4 \), thus the area must be irrational.
On the other hand, the area of \(\triangle ABC\) must be an integer or half an integer by the previous theorem, which means the area must be rational, a contradiction. Therefore, it is impossible to draw an equilateral triangle as a lattice polygon. \(_\square\)
Example Problems
An integer lattice point is a point with coordinates \( (n, m) \), where \(n\) and \(m\) are integers. As \(N\) ranges from 1 to 905, what is the maximum number of integer lattice points in the interior of a triangle with vertices \( (0,0),\) \((N, 907-N),\) and \((N+1, 907-N-1)?\)
Note: The point \( (0,0) \) is not in the interior of any of the triangles described above.
Sketch of Proof
We can prove this using the following sequence of steps:
- It is true for rectangles whose sides are parallel to the axes: This is obvious. An \( a \times b \) rectangle has \(2a+2b\) points on the boundary, \( (a-1)(b-1) \) points in the interior, and an area of \( (a-1)(b-1) + \frac{1}{2} (2a+2b) - 1 = ab \).
- It is true for right triangles whose bases are parallel to the axes: We can double the triangle to form a rectangle and track the points that lie on the hypotenuse.
- It is true for an arbitrary triangle: We take the rectangle whose sides are parallel to the axes that contains this triangle and then subtract off the right triangles whose bases are parallel to the axes.
- It is true for any polygon: We triangulate the polygon.
The main idea here is to show that the sum and difference of polygons still obey Pick's theorem, which is what allows us to glue/detach triangles.