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. Math^{TM}
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/