Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "Pick's Theorem"

(→‎Proof)
m (→‎Proof)
 
(10 intermediate revisions by 6 users not shown)
Line 17: Line 17:
  
 
== Proof ==
 
== Proof ==
−
If a triangle on the lattice points with no point in its interior or on its edges, it has an area of <math>\frac{1}{2}</math>. Such triangle must contain two lattice points distance <math>1</math> from each other and one lattice point on a line parallel to the opposite edge distance <math>1</math> apart. The minimum distance between two distinct lattice points is <math>1</math>. If no two lattice points have distance <math>1</math>, by <math>\frac{1}{2}bh</math> the area is more than 1 and similarly for the height.
+
If a triangle on the lattice points with exactly <math>3</math> points in its interior or on its edges, it has an area of <math>\frac{1}{2}</math>. Such triangle must contain two lattice points distance <math>1</math> from each other and one lattice point on a line parallel to the opposite edge distance <math>1</math> apart. The minimum distance between two distinct lattice points is <math>1</math>. If no two lattice points have distance <math>1</math>, then by <math>\frac{1}{2}bh</math> the area is more than 1 and similarly for the height.
−
Removing <math>1</math> of the mentioned triangles either removes <math>1</math> boundary point, turns <math>1</math> interior point into a boundary point, accounting for the <math>I+\frac{1}{2}B</math> part. The <math>-1</math> part is accounted for by looking at the area of the unit triangle with <math>3</math> boundary points, <math>0</math> interior points, and <math>\frac{1}{2}</math> area. <math>QED</math> <math>\blacksquare</math>
+
Removing a triangle either removes <math>1</math> boundary point or turns <math>1</math> interior point into a boundary point, accounting for the <math>I+\frac{1}{2}B</math> part. The <math>-1</math> part is accounted for by looking at the area of the unit triangle with <math>3</math> boundary points, <math>0</math> interior points, and <math>\frac{1}{2}</math> area.
 +
 
 
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.
 +
 +
Furthermore, 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 15:11, 14 September 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:

$A = I + \frac{1}{2}B - 1$

where $I$ is the number of lattice points in the interior and $B$ 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.

[asy] size(150); defaultpen(linewidth(0.8)); for (int i = -2; i <= 2; i=i+1) { for (int j = -2; j <= 2; j=j+1) { dot((i,j)); } } draw((-2,-2)--(-2,0)--(0,1)--(-1,2)--(2,2)--(0,0)--(1,-2)--cycle);[/asy]

Proof

If a triangle on the lattice points with exactly $3$ points in its interior or on its edges, it has an area of $\frac{1}{2}$. Such triangle must contain two lattice points distance $1$ from each other and one lattice point on a line parallel to the opposite edge distance $1$ apart. The minimum distance between two distinct lattice points is $1$. If no two lattice points have distance $1$, then by $\frac{1}{2}bh$ the area is more than 1 and similarly for the height. Removing a triangle either removes $1$ boundary point or turns $1$ interior point into a boundary point, accounting for the $I+\frac{1}{2}B$ part. The $-1$ part is accounted for by looking at the area of the unit triangle with $3$ boundary points, $0$ interior points, and $\frac{1}{2}$ 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 $x$-axis has length $a$, and the side parallel to the $y$-axis has length $b$, then: \[A = ab, \; I = (a-1)(b-1), \; B = 2a+2b,\] 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 $T$. Consider a rectangle $R$ containing $T$ with $R \setminus T$ 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 $T$ has vertices $V_1 = (x_1, y_1)$, $V_2 = (x_2, y_2)$ and $V_3 = (x_3, y_3)$ with $x_1 \le x_2 \le x_3$. Without loss of generality, suppose $y_1 \le y_3$. If $y_1 \le y_2 \le y_3$ and $V_2$ is below the segment $\overline{V_1V_3}$, then write \[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],\] where the vertices $V_4 = (x_1, y_3)$, $V_5 = (x_2, y_1)$, $V_6 = (x_3, y_2)$. If $y_2 < y_1$, then write \[R \setminus T = \Delta_{V_3 V_4 V_1} + \Delta_{V_1 V_7 V_2} + \Delta_{V_2 V_6 V_3},\] where the vertices $V_4 = (x_1, y_3)$, $V_6 = (x_3, y_2)$, $V_7 = (x_1, y_2)$. For the cases when $V_2$ is above the segment $\overline{V_1V_3}$, 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 $0$ interior points and $3$ boundary points. This is equivalent to showing that any triangles (whose vertices are lattice points) with $0$ interior points and $3$ boundary points, its area is $0 + 3/2 - 1 = 1/2$.

To show this, without loss of generality we can assume that one vertice is $(0,0)$. Suppose the other two vertices are $(x_1, y_1)$ and $(x_2, y_2)$, we see immediately that $gcd(x_1, y_1) = gcd(x_2, y_2) = 1$ from the fact that there are no boundary points other than the vertices. Since the are of the triangle is given by $|x_1 y_2 - x_2 y_1|/2$, our aim is to show that $|x_1 y_2 - x_2 y_1| = 1$.

We argue by contradiction. Since this is indeed a triangle (which means that $x_1 y_2 - x_2 y_1 \neq 0$), we have $d := |x_1 y_2 - x_2 y_1| \ge 2$. Without loss of generality, we can further assume the sign, i.e $d = x_1 y_2 - x_2 y_1 \ge 2$. Using the fact that $gcd(x_1, y_1) = 1$, there exists integers $a$ and $b$ thus that $b x_1 - a y_1 = 1$. One can show that the distance from the point $(a, b)$ to the line $L_1$ passing through $(0,0)$ and $(x_1, y_1)$ is $\frac{1}{\sqrt{x_1^2 + y_1^2}}$ and both $(a,b)$ and $(x_2,y_2)$ are on the same side of $L_1$. Since the distance from $(x_2, y_2)$ to $L_1$ is $\frac{d}{\sqrt{x_1^2 + y_1^2}}$, the distance from $(a,b)$ to $L_1$ is smaller.

Furthermore, for any integer $k$, the point $(a + kx_1, b + ky_1)$ also has a distance $\frac{1}{\sqrt{x_1^2 + y_1^2}}$ to $L$ and on the same side with $(x_2,y_2)$. Let $L_2$ be the line passing through $(0,0)$ and $(x_2,y_2)$, the distance from $(a + kx_1, b + ky_1)$ to $L_2$ is \[\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}}.\] Consequently, one can choose $k$ such that $0 \le ay_2 - bx_2 + kd < d$, i.e. the point $(a + kx_1, b + ky_1)$ is on the same side of $L_2$ with $(x_2, y_2)$ and has a smaller distance. Combining with the previous result, we show that the point $(a + kx_1, b + ky_1)$ is inside the closure of the parallelogram with vertices $(0,0), (x_1,y_2), (x_2,y_2), (x_1+x_2, y_1+y_2)$. So either $(a + kx_1, b + ky_1)$ or $( x_1 + x_2 - (a + kx_1), y_1 + y_2 - (b + ky_1) )$ is an interior point or boundary point for the traingle with vertices $(0,0), (x_1,y_2), (x_2,y_2)$. Due to that the distance from $(a + kx_1, b + ky_1)$ or $( x_1 + x_2 - (a + kx_1), y_1 + y_2 - (b + ky_1) )$ to $L_1$ is $\frac{1}{\sqrt{x_1^2 + y_1^2}}$ or $\frac{d-1}{\sqrt{x_1^2 + y_1^2}}$, this point must be different from the vertices, which finishes the proof.

Usage

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=Pick%27s_Theorem&oldid=227197"