How to Guard an Art Gallery and Other Discrete Mathematical Adventures

2. Count on Pick’s Formula

2 Count on Pick’s Formula Questions are never indiscreet. Answers sometimes are. Oscar Wilde 2.1 The Orchard and the Dollar An area question. What is the area of the orchard in Figure 2.1 if the rows and columns of trees are 1 unit apart? Figure 2.1: Find the area of the pentagonal orchard Counting questions. How many ways are there to make change for a dollar from a supply of quarters, dimes, and nickels? What about change for D dollars? Although the questions we have posed appear entirely unrelated, a remarkable formula discovered by the Austrian 33 34 D is c r e t e M a t he m a t ic a l A d v en t u r es mathematician Georg Pick (1859–1942) can be used to answer both of them. Pick’s formula relates problems from two entirely different worlds—counting problems from discrete mathematics and area problems from plane geometry, the quintessential branch of “indiscrete” (continuous) mathematics . Pick’s formula lets us find the orchard’s area by counting trees, and let us answer dollar-changing questions by computing areas of polygons. Our goal is to understand Pick’s formula and its applications . We first use several different methods to find the orchard’s area and to count the ways to make change for a dollar. The solutions lead us naturally to Pick’s formula, which we then state, verify in a few special cases, and apply to more general money-changing problems. We next give two proofs of Pick’s formula, both relying on elementary geometric notions. Finally, we explore generalizations to higher dimensions. 2.2 The Area of the Orchard While it is not immediately clear how to compute the exact area of the orchard, there is a quick way to find the approximate area. Merely count trees. Each of the orchard’s 27 trees is the center of a 1-by-1 square, as shown in Figure 2.2. The total area of these unit squares is approximately the area of the orchard, and so area of orchard ≈ number of trees = 27. (The notation X ≈ Y means X is approximately equal to Y.) Closer scrutiny of Figure 2.2 yields a better approximation . If a tree is on the orchard’s boundary, then about half of the surrounding unit square protrudes outside the or- C o u n t o n P i c k ’ s F o r m u l a 35 Figure 2.2: Each tree is the center of a unit square chard. There are eight such boundary trees, and thus area of orchard ≈ number of trees − half the number of boundary trees = 27 − 1 2 (8) = 23. We will soon see that the exact area of the orchard is 22. So our tree-counting approximation is off by 1 unit of area. Let us outline two standard geometric methods to compute the exact area of the orchard. It is convenient to introduce Cartesian coordinates and partition the pentagonal orchard into three triangles, as shown in Figure 2.3. We want to find the areas A1, A2, and A3 of the triangles. Applying the familiar formula area of triangle = base × height 2 is awkward because none of the sides of the triangles is parallel to the x- or y-axes. Further geometric analysis is needed to find the bases and heights; we do not delve into the details. A second approach relies on Heron’s formula, a more complicated and less well-known formula that gives 36 D is c r e t e M a t he m a t ic a l A d v en t u r es A1 A2 A3 x y (0, 0) (3, 6) (7, 5) (5, 4) (6, 1) Figure 2.3: The pentagon is partitioned into three triangles the area of a triangle in terms of its sides. The details are again somewhat messy. See Problem 3. Getting Framed Figure 2.4 illustrates a framing method that leads directly to the area of a triangle. The figure frames one of the orchard’s triangles in a 6-by-4 rectangle. The areas of the three unshaded right triangles surrounding the shaded triangle are A2 1 1 3 4 5 6 Figure 2.4: The area of the framed triangle is A2 = 19/2 C o u n t o...