# Cut The Knot!

An interactive column using Java applets
by Alex Bogomolny

# Pick's Theorem

May 1998

Georg Alexander Pick, born in 1859 in Vienna, perished around 1943 in the Theresienstadt concentration camp. [8]

First published in 1899, the theorem was brought to broad attention in 1969 through the popular Mathematical Snapshots by H. Steinhaus. The theorem gives an elegant formula for the area of simple lattice polygons, where "simple", as usual, only means the absence of self-intersection. Polygons covered by the theorem have their vertices located at nodes of a square grid or lattice whose nodes are spaced at distance 1 from their immediate neighbors. The formula does not require math proficiency beyond middle grade school and can be easily verified with the help of a geoboard.

### Pick's Theorem

Let P be a lattice polygon. Assume there are I(P) lattice points in the interior of P, and B(P) lattice points on its boundary. Let A(P) denote the area of A. Then

A(P) = I(P) + B(P)/2 - 1

The most illuminating proof comes from [15].

The applet below is an online variant of the common geoboard. To create a vertex click next to a lattice node. It dose not matter which node you choose. You'll be able to drag an existent vertex to any other node later on. Edges are added automatically. The new node is always inserted between the very first and last vertices. Intersecting edges are shown in red.

(The applet uses an adaptation of a scan conversion algorithm from [13]. The book is replete with ideas. It just appears that this one was not worked out completely.)

With Pick's theorem one may determine area of a (polygonal) portion of a map. On a transparent paper draw a grid to scale and superimpose the grid over the map. Count the number of nodes inside and on the boundary of the map region. Apply Pick's formula with the selected scale.

More importantly, there are links to several other beautiful results. Pick's formula is equivalent to the celebrated Euler's formula [7]. It also implies the basic property of the Farey Series.

The Farey series FN of order n is the ascending sequence of irreducible fractions m/n between 0 and 1 whose denominators do not exceed N. A fraction m/n belongs to FN if and only if

0mnN, gcd(m,n) = 1,

where gcd(m,n) is the greatest common divisor of m and n. For example, F5 is

0/1, 1/5, 1/4, 1/3, 2/5, 1/2, 3/5, 2/3, 3/4, 4/5, 1/1

Farey series is characterized by two wonderful equivalent properties.

G.H.Hardy who prided himself in not having done anything "useful", found it worthwhile to include three different proofs of the basic property of the Farey series in his and E.M.Wright's book. (This is a classical work with the Index located not at the end of the book but, in a contemporary manner, elsewhere on the Web.)

The sequence of denominators of terms in the Farey series is palindromic. The proof may not be immediately obvious. But, as is often the case, having a bigger picture proves useful. The Farey series are embedded into the Stern-Brocot tree for which this property comes almost for free.

The area measurement application of Pick's theorem I mentioned above comes from the real world experience. Grünbaum and Shepard quote D.W.DeTemple who attended a presentation on application of mathematics in the forest industry:

 Although the speaker was not aware that he was essentially using Pick's formula, I was delighted to see that one of my favorite mathematical results was not only beautiful, but even useful.

I am rather curious whether the forester shared in the delight. There is no surprise in that mathematics is useful. Even G.H.Hardy will be remembered in part because of the Hardy-Weinberg law which became centrally important in the study of many genetic problems [6]. I am charmed by the title of an undergraduate text, Applied Abstract Algebra (R.Lidl and G.Pilz, Springer-Verlag, 1997, 2nd edition.) What would Hardy say?

The goal of course is to pass the delight on.

### References

1. A.H.Beiler, Recreations in The Theory of Numbers, Dover, 1966
2. M.Bruckheimer and A.Arcavi, Farey Series and Pick's Area Theorem, The Mathematical Intelligencer v 17 (1995), no 4, pp 64-67.
3. J.Cofman, Numbers and Shapes Revisited, Clarendon Press, 1995
4. J.Conway and R.Guy, The Book of Numbers, Copernicus, 1996
5. H.S.M.Coxeter, Introduction to Geometry, John Wiley & Sons, NY, 1961
6. Encyclopædia Britannica
7. W.W.Funkenbusch, From Euler's Formula to Pick's Formula Using an Edge Theorem, The Am Math Monthly v 81 (1974), pp 647-648
8. B.Grünbaum and G.C.Shepard, Pick's Theorem, The Am Math Monthly v 100(1993), pp 150-161
9. G.H.Hardy, A Mathematician's Apology, Cambridge University Press, 1994.
10. G.H.Hardy and E.M.Wright, An Introduction to the Theory of Numbersm Oxford University Press, Fifth Edition, 1996
11. R. Graham, D. Knuth, O. Potashnik, Concrete Mathematics, 2nd edition, Addison-Wesley, 1994.
12. R.Honsberger, Ingenuity in Mathematics, MAA, 1970
13. T.Pavlidis, Algorithms for Graphics and Image Processing, Computer Science Press, 1982
14. H.Steinhaus, Mathematical Snapshots, Oxford University Press, 1969
15. D.E.Varberg, Pick's Theorem Revisited, The Am Math Monthly v 92(1985), pp 584-587

### On the Internet

Alex Bogomolny has started and still maintains a popular Web site Interactive Mathematics Miscellany and Puzzles to which he brought more than 10 years of college instruction and, at least as much, programming experience. He holds M.S. degree in Mathematics from the Moscow State University and Ph.D. in Applied Mathematics from the Hebrew University of Jerusalem. He can be reached at alexb@cut-the-knot.com