Pick's Theorem
Pick's Theorem expresses the area of a polygon, all of whose vertices are lattice points in a coordinate plane, in terms of the number of lattice points inside the polygon and the number of lattice points on the sides of the polygon. The formula is:
where is the number of lattice points in the interior and being the number of lattice points on the boundary. It is similar to the Shoelace Theorem, and although it is less powerful, it is a good tool to have in solving problems.
Proof
If a triangle on the lattice points with exactly points in its interior or on its edges, it has an area of . Such triangle must contain two lattice points distance from each other and one lattice point on a line parallel to the opposite edge distance apart. The minimum distance between two distinct lattice points is . If no two lattice points have distance , then by the area is more than 1 and similarly for the height. Removing a triangle either removes boundary point or turns interior point into a boundary point, accounting for the part. The part is accounted for by looking at the area of the unit triangle with boundary points, interior points, and area.
Solution by a1b2
The above proof is questionable. Let me added the sketch of two proofs below.
Sketch of Proof 1:
Step 1: Prove the theorem for rectangles whose sides are parallel to the axes. Suppose that the side parallel to the -axis has length , and the side parallel to the -axis has length , then: and thus the asserted formula holds.
Step 2: Prove the theorem for right triangles whose bases are parallel to the axes. This can be checked by cutting a rectangle in step 1 into two right triangles.
Step 3: Prove the theorem for an arbitrary triangle . Consider a rectangle containing with can be divided into several right triangles and rectangles. This enables us to subtract off the right triangles and rectangles from the rectangles to verify the claimed formula.
To be more specific, suppose that has vertices , and with . Without loss of generality, suppose . If and is below the segment , then write where the vertices , , . If , then write where the vertices , , . For the cases when is above the segment , this can be done in a similar way.
Step 4: Prove the theorem for any polygon: simply triangulate the polygon.
Sketch of Proof 2:
Since one can triangulate any polygon, it suffices to prove for triangles. Since if a triangle has any interior points or boundary points other than its vertices, one can further divide this triangle into smaller triangles, it suffices to prove the theorem for triangles with interior points and boundary points. This is equivalent to showing that any triangles (whose vertices are lattice points) with interior points and boundary points, its area is .
To show this, without loss of generality we can assume that one vertice is . Suppose the other two vertices are and , we see immediately that from the fact that there are no boundary points other than the vertices. Since the are of the triangle is given by , our aim is to show that .
We argue by contradiction. Since this is indeed a triangle (which means that ), we have . Without loss of generality, we can further assume the sign, i.e . Using the fact that , there exists integers and thus that . One can show that the distance from the point to the line passing through and is and both and are on the same side of . Since the distance from to is , the distance from to is smaller.
Furthermore, for any integer , the point also has a distance to and on the same side with . Let be the line passing through and , the distance from to is Consequently, one can choose such that , i.e. the point is on the same side of with and has a smaller distance. Combining with the previous result, we show that the point is inside the closure of the parallelogram with vertices . So either or is an interior point or boundary point for the traingle with vertices . Due to that the distance from or to is or , this point must be different from the vertices, which finishes the proof.