Difference between revisions of "Pick's Theorem"
Jeffersonj (talk | contribs) (→Discussion) |
Runninterp (talk | contribs) (→Proof) |
||
(6 intermediate revisions by 3 users not shown) | |||
Line 21: | Line 21: | ||
Solution by [[User:a1b2|a1b2]] | Solution by [[User:a1b2|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 <math>x</math>-axis has length <math>a</math>, and the side parallel to the <math>y</math>-axis has length <math>b</math>, then: | ||
+ | <cmath> | ||
+ | A = ab, \; I = (a-1)(b-1), \; B = 2a+2b, | ||
+ | </cmath> | ||
+ | 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 <math>T</math>. Consider a rectangle <math>R</math> containing <math>T</math> with <math>R \setminus T</math> 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 <math>T</math> has vertices <math>V_1 = (x_1, y_1)</math>, <math>V_2 = (x_2, y_2)</math> and <math>V_3 = (x_3, y_3)</math> with <math>x_1 \le x_2 \le x_3</math>. Without loss of generality, suppose <math>y_1 \le y_3</math>. If <math>y_1 \le y_2 \le y_3</math> and <math>V_2</math> is below the segment <math>\overline{V_1V_3}</math>, then write | ||
+ | <cmath> | ||
+ | R \setminus T = \Delta_{V_3 V_4 V_1} + \Delta_{V_1 V_5 V_2} + \Delta_{V_2 V_6 V_3} + [x_2,x_3] \times [y_1, y_2], | ||
+ | </cmath> | ||
+ | where the vertices <math>V_4 = (x_1, y_3)</math>, <math>V_5 = (x_2, y_1)</math>, <math>V_6 = (x_3, y_2)</math>. If <math>y_2 < y_1</math>, then write | ||
+ | <cmath> | ||
+ | R \setminus T = \Delta_{V_3 V_4 V_1} + \Delta_{V_1 V_7 V_2} + \Delta_{V_2 V_6 V_3}, | ||
+ | </cmath> | ||
+ | where the vertices <math>V_4 = (x_1, y_3)</math>, <math>V_6 = (x_3, y_2)</math>, <math>V_7 = (x_1, y_2)</math>. For the cases when <math>V_2</math> is above the segment <math>\overline{V_1V_3}</math>, 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 <math>0</math> interior points and <math>3</math> boundary points. This is equivalent to showing that any triangles (whose vertices are lattice points) with <math>0</math> interior points and <math>3</math> boundary points, its area is <math>0 + 3/2 - 1 = 1/2</math>. | ||
+ | |||
+ | To show this, without loss of generality we can assume that one vertice is <math>(0,0)</math>. Suppose the other two vertices are <math>(x_1, y_1)</math> and <math>(x_2, y_2)</math>, we see immediately that <math>gcd(x_1, y_1) = gcd(x_2, y_2) = 1</math> from the fact that there are no boundary points other than the vertices. Since the are of the triangle is given by <math>|x_1 y_2 - x_2 y_1|/2</math>, our aim is to show that <math>|x_1 y_2 - x_2 y_1| = 1</math>. | ||
+ | |||
+ | We argue by contradiction. Since this is indeed a triangle (which means that <math>x_1 y_2 - x_2 y_1 \neq 0</math>), we have <math>d := |x_1 y_2 - x_2 y_1| \ge 2</math>. Without loss of generality, we can further assume the sign, i.e <math>d = x_1 y_2 - x_2 y_1 \ge 2</math>. Using the fact that <math>gcd(x_1, y_1) = 1</math>, there exists integers <math>a</math> and <math>b</math> thus that <math>b x_1 - a y_1 = 1</math>. One can show that the distance from the point <math>(a, b)</math> to the line <math>L_1</math> passing through <math>(0,0)</math> and <math>(x_1, y_1)</math> is <math>\frac{1}{\sqrt{x_1^2 + y_1^2}}</math> and both <math>(a,b)</math> and <math>(x_2,y_2)</math> are on the same side of <math>L_1</math>. Since the distance from <math>(x_2, y_2)</math> to <math>L_1</math> is <math>\frac{d}{\sqrt{x_1^2 + y_1^2}}</math>, the distance from <math>(a,b)</math> to <math>L_1</math> is smaller. | ||
+ | |||
+ | Furhtermore, for any integer <math>k</math>, the point <math>(a + kx_1, b + ky_1)</math> also has a distance <math>\frac{1}{\sqrt{x_1^2 + y_1^2}}</math> to <math>L</math> and on the same side with <math>(x_2,y_2)</math>. Let <math>L_2</math> be the line passing through <math>(0,0)</math> and <math>(x_2,y_2)</math>, the distance from <math>(a + kx_1, b + ky_1)</math> to <math>L_2</math> is | ||
+ | <cmath> | ||
+ | \frac{| (a + kx_1)y_2 - (b + ky_1)x_2 |}{\sqrt{x_2^2 + y_2^2}} = \frac{| ay_2 - bx_2 + kd |}{\sqrt{x_2^2 + y_2^2}}. | ||
+ | </cmath> | ||
+ | Consequently, one can choose <math>k</math> such that <math>0 \le ay_2 - bx_2 + kd < d</math>, i.e. the point <math>(a + kx_1, b + ky_1)</math> is on the same side of <math>L_2</math> with <math>(x_2, y_2)</math> and has a smaller distance. Combining with the previous result, we show that the point <math>(a + kx_1, b + ky_1)</math> is inside the closure of the parallelogram with vertices <math>(0,0), (x_1,y_2), (x_2,y_2), (x_1+x_2, y_1+y_2)</math>. So either <math>(a + kx_1, b + ky_1)</math> or <math>( x_1 + x_2 - (a + kx_1), y_1 + y_2 - (b + ky_1) )</math> is an interior point or boundary point for the traingle with vertices <math>(0,0), (x_1,y_2), (x_2,y_2)</math>. Due to that the distance from <math>(a + kx_1, b + ky_1)</math> or <math>( x_1 + x_2 - (a + kx_1), y_1 + y_2 - (b + ky_1) )</math> to <math>L_1</math> is <math>\frac{1}{\sqrt{x_1^2 + y_1^2}}</math> or <math>\frac{d-1}{\sqrt{x_1^2 + y_1^2}}</math>, this point must be different from the vertices, which finishes the proof. | ||
== Usage == | == Usage == |
Latest revision as of 14:29, 26 June 2024
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.
Furhtermore, 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.