|
|
Explanation and Informal Proof of Pick's TheoremDate: 04/27/2004 at 13:26:38 From: Ozcar Subject: Trying to figure out Pick's Theorem We just learned Pick's Theorem, A = b/2 + I - 1, where b is the boundary pegs, I is the interior pegs, and A is the area. I don't get why it works. Why do you divide the boundary by 2 and subtract 1?
Date: 04/27/2004 at 13:57:54
From: Doctor Peterson
Subject: Re: Trying to figure out Pick's Theorem
Hi, Ozcar.
The usual way to prove Pick's Theorem uses induction, by first proving
it for triangles, and then proving the theorem for all polygons by
dividing them into triangles. Here are several pages that present
versions of this proof:
http://www.cut-the-knot.com/ctk/Pick_proof.shtml
http://planetmath.org/encyclopedia/ProofOfPicksTheorem.html
http://www.geometer.org/mathcircles/pick.pdf
This works well as a proof, but is not very satisfying, because it
does not show how you would see the theorem in the first place. And I
think that is what you would like to see: why should this surprisingly
simple formula be true??
Here is a more intuitive way to show that Pick's Theorem works for all
lattice polygons, which I wrote up some time ago. It is probably
harder to turn into a careful proof than the inductive approach,
because there are tricky cases to deal with; but it is very convincing
at least as to the general truth of the theorem.
Let's take the polygon ABCD as an example to see how it works:
o o B o o
/ \
/ \
/ \
o o / o o o
/ \
/ \
/ \
o o o o C
/ |
/ |
/ |
o / o o o o
/ |
/ |
/ |
A_______o o o o
\_______ |
\_______ |
\_______|
o o o o D
I'll draw a square around each lattice point, so each square has area
1:
+-------+-------+-------+-------+-------+
| | | | | |
| o | o | B | o | o |
| | | / \ | | |
+-------+-------+-/-----\-------+-------+
| | |/ | \ | |
| o | o / o | o | o |
| | /| | \ | |
+-------+-----/-+-------+-------\-------+
| | / | | | \ |
| o | o | o | o | C |
| | / | | | | |
+-------+-/-----+-------+-------+---|---+
| |/ | | | | |
| o / o | o | o | o |
| /| | | | | |
+-----/-+-------+-------+-------+---|---+
| / | | | | | |
| A___|___o | o | o | o |
| | \___|___ | | | |
+-------+-------+---\---+-------+---|---+
| | | | \___|___| |
| o | o | o | o | D |
| | | | | |
+-------+-------+-------+-------+-------+
We're going to look at three groups of lattice points:
V: the number of vertices (4 in our example), which must be on
lattice points
E: the number of lattice points on the edges (4 in our example)
I: the number of lattice points in the interior (9 in our example)
Note that B = V + E is the number of lattice points on the boundary.
We'll compare the area of the squares surrounding each kind of lattice
point with the area of the part of the polygon within those squares.
First, look at the edge points. In the following picture, I've filled
in the part of these squares that is within the polygon with dots:
+-------+-------+-------+-------+-------+
| | | | | |
| o | o | B | o | o |
| | | / \ | | |
+-------+-------+-/-----\-------+-------+
| | |/ |.\ | |
| o | o / o |...o | o |
| | /| |.....\ | |
+-------+-----/-+-------+-------\-------+
| | /..| | | \ |
| o | o...| o | o | C |
| | /....| | | | |
+-------+-/-----+-------+-------+---|---+
| |/ | | |...| |
| o / o | o | o |...o |
| /| | | |...| |
+-----/-+-------+-------+-------+---|---+
| / | | | |...| |
| A___|___o | o | o |...o |
| | \___|___ | |...| |
+-------+-------+---\---+-------+---|---+
| | | | \___|___| |
| o | o | o | o | D |
| | | | | |
+-------+-------+-------+-------+-------+
Note that since the edge runs through the center of each square, the
area of the polygon within these squares is exactly half the area of
the squares:
A[E] = E/2
In our example, this totals 2 square units.
(If you are smart, you will realize that an edge square might in fact
also be cut by another edge (or more!), so a complete proof would
have to account for this. We'll ignore such details, since we are not
trying to make a watertight proof, but just to convince ourselves that
the theorem makes sense.)
Now look at the squares surrounding vertices:
+-------+-------+-------+-------+-------+
| | | | | |
| o | o | B | o | o |
| | | /bb\ | | |
+-------+-------+-/-----\-------+-------+
| | |/ | \ | |
| o | o / o | o | o |
| | /| | \ | |
+-------+-----/-+-------+-------\-------+
| | / | | |c\ |
| o | o | o | o |cccC |
| | / | | |ccc| |
+-------+-/-----+-------+-------+---|---+
| |/ | | | | |
| o / o | o | o | o |
| /| | | | | |
+-----/-+-------+-------+-------+---|---+
| /aa| | | | | |
| Aaaa|___o | o | o | o |
| | \___|___ | | | |
+-------+-------+---\---+-------+---|---+
| | | | \___|ddd| |
| o | o | o | o | D |
| | | | | |
+-------+-------+-------+-------+-------+
Note that in this case (a quadrilateral), we can fit the four shaded
"sectors" together like this:
+-------+
|c\bb/aa|
|cccoaaa|
|ccc|ddd|
+-------+
To do this, start at one vertex, such as A; then go around the
polygon, making a ray parallel to each new side of the polygon, and in
alternating directions. For example, we start with angle a (as shown
below); then slide angle b into place next to it along ray AB; then
slide angle c into place, adjacent to b along a ray parallel to CB;
and then similarly fit in angle d. This makes "sectors" of a square,
congruent to those in each of the vertex squares, all fitting
together.
\ b /
\ /
B
/ \
/ \
/ \
/ o
/ \
/ \
/ \
o C
/ c |
/ |
/ |
/ o
/ | \ /
/ | \ b /
/ a | \ / a
A_______ o A_______
\_______ | c | \
\_______ | | d
\_______| |
D_______
| \
| d
For different numbers of vertices, the total angle will vary; for
instance, if you do the same with a triangle, you will fill exactly
half of the square, and for a pentagon, the five angles will cover a
full square and half of another. You can look elsewhere in Dr. Math
for proofs that the sum of the internal angles of a polygon is (V-2)
*180, where V is the number of vertices. Here are two:
Interior Angles of a Polygon
http://mathforum.org/library/drmath/view/54887.html
Sum of Interior and Exterior Angles
http://mathforum.org/library/drmath/view/62228.html
Since a 180 degree "sector" is half a square, this means that the
total area of the polygon within all the vertex squares is
A[V] = (V - 2)/2 = V/2 - 1
In our example this is 4/2 - 1 = 1 square unit, as I showed.
Now all that's left is to show that the area of the polygon EXCLUDING
the parts in the vertex and edge squares, is equal to the area of the
interior squares, as shown below:
+-------+-------+-------+-------+-------+
| | | | | |
| o | o | B | o | o |
| | | / \ | | |
+-------+-------+-/-----\-------+-------+
| | |/::::::| \ | |
| o | o /:::o:::| o | o |
| | /|:::::::| \ | |
+-------+-----/-+-------+-------\-------+
| | / |:::::::|:::::::| \ |
| o | o |:::o:::|:::o:::| C |
| | / |:::::::|:::::::| | |
+-------+-/-----+-------+-------+---|---+
| |/::::::|:::::::|:::::::| | |
| o /:::o:::|:::o:::|:::o:::| o |
| /|:::::::|:::::::|:::::::| | |
+-----/-+-------+-------+-------+---|---+
| / |:::::::|:::::::|:::::::| | |
| A___|:::o:::|:::o:::|:::o:::| o |
| |:::\:::|:::::::|:::::::| | |
+-------+-------+---\---+-------+---|---+
| | | | \___|___| |
| o | o | o | o | D |
| | | | | |
+-------+-------+-------+-------+-------+
To see this, consider one side of a polygon:
+-------+-------+-------+
|xxxxxxx|xxxxxxx| |
|xxxoxxx|xxxoxxx| B |
|xxxxxxx|xxxxxxx| / |
+-------+-------+-/-----+
|xxxxxxx|xxxxxxx|/::::::|
|xxxoxxx|xxxoxxx/:::o:::|
|xxxxxxx|xxxxxx/|:::::::|
+-------+-----/-+-------+
|xxxxxxx| / |:::::::|
|xxxoxxx| o |:::o:::|
|xxxxxxx| / |:::::::|
+-------+-/-----+-------+
|xxxxxxx|/::::::|:::::::|
|xxxoxxx/:::o:::|:::o:::|
|xxxxxx/|:::::::|:::::::|
+-----/-+-------+-------+
| / |:::::::|:::::::|
| A |:::o:::|:::o:::|
| |:::::::|:::::::|
+-------+-------+-------+
Notice the symmetry within this rectangle; the "x" squares on the
"outside" of the line are identical to the ":" squares on the
"inside", since they can be obtained by rotating the whole rectangle
180 degrees about its center. So any place an "inside" square
projects beyond the edge, there is an opposite place where an
"outside" square projects in over the edge the same amount:
B
/
+-/
|/ ---+ use extra here
/ |
/| <-+ |
/-+ | |
/ | |
o | |
/ | |
+-/ | |
|/ ---------+ |
/ |
/| <-----------+ to fill in here
/-+
/
A
Therefore, if we "fill in the holes", there is just enough area in the
"bumps" to level the zigzag off perfectly. The area of the interior
squares exactly fills the inside of the polygon that remains after
taking into account the vertex and edge squares.
A[I] = I
So we have three parts to the area:
+-------+-------+-------+-------+-------+
| | | | | |
| o | o | B | o | o |
| | | /VV\ | | |
+-------+-------+-/-----\-------+-------+
| | |/IIIIII|E\ | |
| o | o /IIIIIII|EEEo | o |
| | /|IIIIIII|EEEEE\ | |
+-------+-----/-+-------+-------\-------+
| | /EE|IIIIIII|IIIIIII|V\ |
| o | oEEE|IIIIIII|IIIIIII|VVVC |
| | /EEEE|IIIIIII|IIIIIII|VVV| |
+-------+-/-----+-------+-------+---|---+
| |/IIIIII|IIIIIII|IIIIIII|EEE| |
| o /IIIIIII|IIIIIII|IIIIIII|EEEo |
| /|IIIIIII|IIIIIII|IIIIIII|EEE| |
+-----/-+-------+-------+-------+---|---+
| /VV|IIIIIII|IIIIIII|IIIIIII|EEE| |
| AVVV|IIIIIII|IIIIIII|IIIIIII|EEEo |
| | \III|IIIIIII|IIIIIII|EEE| |
+-------+-------+---\---+-------+---|---+
| | | | \III|VVV| |
| o | o | o | o | D |
| | | | | |
+-------+-------+-------+-------+-------+
V = parts of triangle in vertex squares
E = parts of triangle in edge squares
I = parts of triangle not in vertex or edge squares
A = A[E] + A[V] + A[I]
= E/2 + V/2 - 1 + I
= I + (E + V)/2 - 1
= I + B/2 - 1
This is Pick's formula!
So the "I" term means that the interior squares can be smoothed out to
exactly fill their part of the polygon; the "B" term means that the
edge squares and all but two of the vertex squares are exactly cut in
half by the boundary; and the -1 term adjusts for the two extra vertex
squares.
Just to show that what I have said so far is not adequate as a
complete proof, consider a "bad" polygon like ABCDE:
+-------+-------+-------+-------+
| | | | |
| o | o | B | o |
| | | / \ | |
+-------+-------+-/--\--+-------+
| | |/ \ | |
| o | o / E \| o |
| | /| // \| |
+-------+-----/-+/-/ ---\-------+
| | / / / |\ |
| o | o / |/ o |\ o |
| | / / |/ | \ |
+-------+-/-/---/--- ---+--\----+
| |/ / /| | \ |
| o // o /| o | C |
| // / | / |
+-----//+----/--+---/---+-------+
| / | / / | |
| A | D | | o |
| | | | |
+-------+-------+-------+-------+
Here we have vertex, edge, and interior squares through which more
than one edge pass; try applying my analysis to this polygon, and you
will have to do some pretty complex thinking! The formula still
works, but it can't be related to the areas in the three types of
squares so easily, since many squares do double duty.
I think that in order to turn this into a complete proof, you would
probably have to first apply it only to convex polygons, and then use
the fact on which the usual proof is based, that the formula is
additive, to show that it applies to concave polygons as well. Even
restricting our proof to convex polygons, we would have trouble with
"needle-shaped" polygons (like ABE in the example above), narrow
enough for two edges to pass through the same square. But I think
this approach to the proof, at least as an introduction, is helpful
for understanding the theorem.
If you have any further questions, feel free to write back.
- Doctor Peterson, The Math Forum
http://mathforum.org/dr.math/
|
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. MathTM
© 1994-2011 The Math Forum
http://mathforum.org/dr.math/
