*Note:* To protect the privacy of our members, e-mail addresses have been removed from the archived messages. As a result, some links may be broken.

### Fw: 3 projects in color and math

**[ Thread ][ Subject ][ Author ][ Date ]****Larry Cox** (

*L_J_Cox*)

*Tue, 16 Feb 1999 10:17:34 -0700*

*>Subject Terms: Secondary school students*
*> Middle school students*
*> Mathematics education*
*> Geometry*
*> Color*
*>Three activities in discrete mathematics that involve the coloration of*
*>geometric objects--counting colored regions of overlapping simple closed*
*>curves, counting colored triangulations of polygons and determining the*
*>number of colors either necessary or sufficient to paint the points of*
*>the plane while satisfying a distance rule--are presented for students*
*>in grades 6-12.*
*>*
*>TEACHER'S GUIDE*
*>*
*>In this article, we suggest three activities in discrete mathematies, all*
*>of which involve the coloration of geometric objects: counting colored*
*>regions of overlapping simple closed curves, counting colored*
triangulations

*>of polygons, and determining the number of colors either necessary or*
sufficient

*>to paint the points of the plane while satisfying a distance rule. They*
*>are designed to be used in small groups and can also serve as topies for*
*>whole-class discussions, offering opportunities for generating, collecting,*
*>and organizing data and examples; identifying, describing, and studying*
*>patterns; and making, testing, and verifying conjectures.*
*>*
*>The activities are independent of one another and need not be done*
consecutively.

*>Sheet 1 is very accessible and makes a nice stand-alone investigation.*
*>Sheet 2 makes connections to the angle-sum formula for polygons and to*
*>Euler's formula. Sheet 3 enhances work on tiling and distance.*
*>*
*>Coloring problems are not a staple of the secondary curriculum, but they*
*>have an important place in mathematics. The most famous coloring problem*
*>is the four-color problem: If a map is to be colored so that countries*
*>sharing a border must receive contrasting colow, will more than four colors*
*>ever be needed? The problem originated in 1850 and eluded solution until*
*>1976 when Kenneth Appel and Wolfgang Haken proved that four colors suffice.*
*>Other coloring problems originate in the classification of border and*
wallpaper

*>patterns in which motifs are distinguished by color as well as by geometric*
*>shape. Although not a focus of these activities, a variety of real-world*
*>problems in scheduling, communications, traffic flow, and inventory control*
*>and storage can be interpreted and solved using concepts of color.*
*>*
*>Grade levels: 6-12. These activities, or portions thereof, have been used*
*>in grades 6 through 12. The discovery of the patterns does not depend on*
*>any specific formulas or theorems from other sources. The slightly of meat*
*>topics are real attention grabbers. Indeed, it has been our experience*
*>that even some of the more average students rise to the occasion and become*
*>major contributors to the class discussion. Especially gratifying has been*
*>the request from students to pursue the question of why these unexpected*
*>patterns hold, giving the teacher a wonderful opportunity to work through*
*>a proof or derivation that is truly appreciated by the class. These proofs*
*>are outlined subsequently. Each teacher should assess the readiness of*
*>students to tackle these proofs.*
*>*
*>Materials: Scratch paper; activity sheets; rulers; colored pencils in at*
*>least four distinct colors, preferably red, yellow, green, and blue;*
compasses

*>(optional)*
*>*
*>Prerequisites: Students should be familiar with the following terms and*
*>concepts from elementary geometry: polygon, vertex of a polygon, interior*
*>angle of a polygon, regular hexagon, and polygon sum property (the sum*
*>of the interior angles of an n-gon is (n - 2)180).*
*>*
*>Sheet 1: Before handing out the sheet, review or introduce the definition*
*>of a simple closed curve: a closed curve that does not intersect itself.*
*>Have students draw on the chalkboard with colored markers or chalk several*
*>examples and nonexamples, as shown in figure 1. (Figure 1 omitted) Mention*
*>that any simple closed curve separates the plane into two disjoint regions,*
*>the interior and the exterior. This important result is called the Jordan*
*>curve theorem, which was developed by Camille Jordan (1838-1922). If*
necessary,

*>display and discuss one or two examples before letting students investigate*
*>the questions in small groups.*
*>*
*>If sheets of yellow and blue plastic are available--report covers work*
*>nicely--use scissors to cut along fairly complex, but still simple, closed*
*>curves from each sheet to create two regions. When the yellow and blue*
*>shapes are overlapped on the overhead projector, four types of regions*
*>are created: white (outside both curves), yellow (inside the yellow curve*
*>only), blue (inside the blue curve only)l and green (inside both the yellow*
*>and the blue curves). The colored plastic sheets can be used to emphasize*
*>the crossing rules of intersection and are easy to reposition to recount*
*>the number of regions.*
*>*
*>Students should discover that all properly overlapping simple closed curves*
*>have the following properties:*
*>*
*>i. The number of yellow regions is always equal to the number of blue*
regions.

*>*
*>ii. The number of green regions is always equal to the number of white*
*>regions.*
*>*
*>A nice extension can be used to challenge cooperative groups that find*
*>these properties quickly and want to look further. Suggest that they also*
*>consider the number of points of intersection of the two curves and how*
*>that number compares with the number of colored regions. They will find*
*>this property:*
*>*
*>iii. The number of intersection points is always even, say 2n, and is 2*
*>less than the total number of regions. If y, b, g, and w denote,*
respectively,

*>the numbers of yellow, blue, green, and white regions, then we have y =*
*>b, g = w, and b + w = n + 1.*
*>*
*>An informal but convincing argument, the rubberband proof, can be given*
*>to justify these properties. Imagine that the blue curve is allowed to*
*>shrink to a small circle that intersects the yellow curve in just two*
points.

*>This case is much like the two-circle case shown in the example, which*
*>clearly shows that each of the four colors has one region and that n equals*
*>two points of intersection. Next imagine that the blue circle grows and*
*>distorts as it returns to its original shape. Each time the growing blue*
*>curve intersects the yellow curve at two new points of intersection, two*
*>new regions are formed. Either one new region is blue and one is yellow*
*>or one new region is green and the other is white. Either way, the counts*
*>of blue and yellow regions, and of green and white regions, are kept equal*
*>at each step, and the relationship b + w = n + 1 is maintained. When the*
*>blue curve is stretched to coincide with its original shape, properties*
*>i, ii, and iii follow.*
*>*
*>Sheets 2A and 2B: The first three explorations on sheet 2 lay the*
groundwork

*>for exploration 4. However, they are interesting in their own right and*
*>can be pursued even if exploration 4 is not used. Exploration 1 is*
strightforward

*>and should be accessible to almost all students. For exploration 2,*
polygons

*>with n equal to 5, 6, 7, and 8 work well. The result of exploration 2 is*
*>surprising; an explanation follows.*
*>*
*>CONJECTURE. The parity of the number of vertices of each type and the*
parity

*>of the total number of vertices must be the same. Inegers have the same*
*>parity ifall are even or all are odd.*
*>*
*>PROOF. Each side of the polygon contains two vertices. Hence, the number*
*>of red-green (rg) vertices plus the number of blue-green (bg) vertices*
*>is equal to twice the number of green sides and is, therefore, an even*
*>number. Thus the parity of rg must be the same as the parity of bg. By*
*>a similar argument, the parity of rg must be the same as the parity of*
*>rb. Since the parity of all three types is the same, and since the sum*
*>of three odd or even numbers is odd or even, respectively, the total number*
*>of vertices is odd if all three types are odd and is even if all three*
*>types are even.*
*>*
*>Before assigning exploration 3, discuss the definition of a triangulated*
*>polygon and review what is meant by a vertex of the polygon and how it*
*>differs from an interior vertex, which was introduced in the triangulation*
*>process. Also make sure that the notation is clear.*
*>*
*>If students have trouble discovering the pattern in the table, suggest*
*>that they draw figures that maintain one variable constant to see the*
relationship

*>between the other two. For example, they can use i = 1, vary n, and see*
*>what happens to t, then keep n constant while they vary i. If students*
*>get stuck, suggest that an extra row be added to the table, showing 2i.*
*>The formula is t = n + 2i - 2. An outline of the proof follows.*
*>*
*>Suppose that the degree measures of all interior angles of all t triangles*
*>in a triangulation are added. Why is this sum equal to 180t? Why is this*
*>sum also given by 360i + 180(n - 2) for a triangulated n-gon having i*
interior

*>vertices? What formula connecting n, i, and t results when these*
expressions

*>are equated? Is the formula consistent with the data?*
*>*
*>Another proof of this formula, based on Euler's formula in graph theory,*
*>is presented subsequently. This formula leads to a nice proof of Pick's*
*>formula for the area of a lattice polygon; for details, request a copy*
*>of the first reference from the author.*
*>*
*>Before assigning exploration 4, discuss the coloring rules carefully. All*
*>interior vertices should be checked to see if all three colors mistakenly*
*>appear; if so, the error must be corrected. Illustrate how to color the*
*>example on the sheet. It is actually instructive to make an error, point*
*>it out, and then show how some edges can be recolored to correct the error.*
*>A proof of the final result requires familiarity with the basics of graph*
*>theory. A copy of the proof is available from the author. However, students*
*>can do the exploration and make a conjecture even if they cannot understand*
*>the proof. The new results entered in the table from exploration 2 often*
*>amaze them] The last three questions consolidate an understanding of the*
*>conjecture.*
*>*
*>Note that a valid coloring always exists: one permissible color can always*
*>be assigned to any edge. For example, the edge between a red-blue and a*
*>blue-green vertex can--in fact, must--be colored blue.*
*>*
*>If geometry-drawing software is available, the polygons and triangulations*
*>can first be drawn in black; edges are next selected and colors are*
assigned.

*>Using this software is a convenient way to draw the figures and correct*
*>easily the inevitable coloring errors.*
*>*
*>If students are familiar with the basic definitions and concepts of graph*
*>theory, this section will help the teacher connect those ideas with sheet*
*>2. Recall that a graph is a set of vertices, denoted V sub 0 , V sub 1*
*>, ..., v sub n , and a set of eges that join certain pairs of distinct*
*>vertices. A graph is depicted by drawing dots for vertices and joining*
*>pairs of dots to indicate edges.*
*>*
*>An alternative proof of the exploration-3 formula follows. Euleis formula,*
*>V-E + R = 1, relates the number of vertices V, edges E, and bounded regions*
*>R in a connected plane network. For a triangulated n-gon with i interior*
*>vertices and t triangles, V = n + i and R = t. Since each triangle is*
bounded

*>by three edges, 3t counts each inner edge of the triangulation twice and*
*>each n edge of the polygon once. Thus 2E = 3t + n. Rewriting Euler's*
formula

*>as 2V - 2E + 2R = 2 gives 2 (n + i) - (3t + n) + 2t = 2. This equation*
*>is easily solved for t, resulting in t = n + 2i - 2.*
*>*
*>Sheets 3A and 3B: Be sure that the one-inch color rule is understood*
correctly.

*>Explain that the smallest number of colors needed to paint the plane*
according

*>to the rule is not known and that the work on this sheet aims to show how*
*>a lower and an upper bound for this number have been found.*
*>*
*>A compass set at a one-inch opening can be useful, but an inch ruler also*
*>works. Instead of coloring the hexagons, it is easier to put a letter or*
*>number inside a hexagon to indicate its color.*
*>*
*>Sheets 3A and 3B prove the following theorem:*
*>*
*>THEOREM. The minimum number of colors needed to paint the points of the*
*>plane so that no two points one inch apart are of the same color is at*
*>least four but no more than seven.*
*>*
*>The required number of colors is four, five, six, or seven, but determining*
*>which of these four numbers is the precise minimum value is still an*
unsolved

*>problem of geometry some thirty-five years after it was proposed by Gardner*
*>(1960) and Hadwiger (1960). A discussion of the problem, and other painting*
*>problems in the plane, can be found in Klee and Wagon (1991).*
*>*
*>Answers to selected problems: Sheet 1*
*>*
*>Example: One region of each color exists. The other figure given as an*
*>example has four yellow and four blue regions and three white and three*
*>green regions.*
*>*
*>Exploration. See the teacher's guide.*
*>*
*>Sheets 2A and 2B*
*>*
*>Exploration 1. When n is even, two colors are enough, alternating about*
*>the edges of the polygon. When n is odd, alternating two colors will no*
*>longer satisfy rule 1, and a third color, say, for the last edge, is*
required.

*>*
*>Exploration 2. The first four numbers in each column will be all even or*
*>all odd. That is, the number of vertices of each type, and the total number*
*>of vertices, all have the same parity.*
*>*
*>Exploration 3. The relationship is t = n + 2i - 2. See the teacher's guide*
*>for a proof.*
*>*
*>Exploration 4. The six numbers in each column have the same parity. See*
*>the teacher's guide for a proof.*
*>*
*>Answers to follow-up questions*
*>*
*>1. If the number of red-blue vertices is 7, then the parity of all the*
*>entrie in that column is odd. Since an odd positive integer is 1 or larger,*
*>at least one blue-green veTtex of the polygon must exist.*
*>*
*>2. Since all the entries in a column have the same parity, the number of*
*>complete triangles is also odd. In particular, at least one complete*
triangle

*>always exists.*
*>*
*>3. The number 13 is odd, so all numbers in the column are odd and, as in*
*>question 2, this fact alone indicates that at least one complete triangle*
*>exists.*
*>*
*>Sheet 3A*
*>*
*>Exploration 1. Let point A be painted any color, say, red. Since B is one*
*>inch from A, it cannot be red, so paint it blue. Point C, being one inch*
*>from both A and B, cannot be red or blue, and so a third color is required.*
*>Thus three, or perhaps more, colors are required to paint the points of*
*>the plane to satisfy the one-inch color rule.*
*>*
*>Exploration 2. From the foregoing discussion, we know that three colors*
*>are necessary to paint A, B, and C. Suppose that A is red, B is blue, and*
*>C is green. Point D, since it is one inch from B and C, cannot be blue*
*>or green. But since D is more that one inch from A, it can be red. Only*
*>three colors are needed to paint A, B, C, and D, but then A and D must*
*>have the same color.*
*>*
*>Exploration 3. Suppose that A is red. From exploration 1, we know that*
*>B and C must be painted two other colors, say, blue and green. Similarly*
*>B' and C' must be blue and green or green and blue. By exploration 2, if*
*>we are attempting to use just three colors, then poinC D would have to*
*>be red, the color of A. But the same reasoning shows that D' would also*
*>need to be red. Since D and D' are one inch apart and both are red, we*
*>see that it is impossible to use just three colors to color the points*
*>A, B, C, D, B: C: and D' according to the one-inch rule. A fourth color,*
*>say, yellow, is needed for D'. The following conclusion can be reached:*
*>If each point of the plane is painted a color such that no two points one*
*>inch apart are painted the same color, then at least four colors are*
needed.

*>*
*>Note that we do not claim that four colors are enough; perhaps some more*
*>ingenious set of points would show that even four colors are not enough.*
*>*
*>Sheet 3B*
*>*
*>Exploration 1. No two points of any one hexagon are one inch apart, so*
*>painting a hexagon and its interior all the sme color is permissible. If*
*>hexagon 1 is, say, red, then hexagon 2 must be of a different color, say,*
*>blue, since it has points that are one inch from points in hexagon 1.*
Similarly,

*>hexagon 3 must get a different color, say, green, than either hexagon 1*
*>or hexagon 2. Hexagon 4 cannot be blue or green, but since all its points*
*>are more than one inch from all the points in hexagon 1, it is permissible*
*>to paint hexagon 4 red, the same color as hexagon 1. Notice that the points*
*>along the edges of the hexagons can be painted with either color of the*
*>adjoining hexagons.*
*>*
*>Exploration 2. Every one of the seven hexagons contains points that are*
*>exactly one inch from some point in any other hexagon. Thus, if all the*
*>points of the hexagon are to be of the same color, we need seven colors.*
*>*
*>Exploration 3. The seven adjoining hexagons, each with a different color,*
*>form a tile that can cover the plane. The following conclusion can be*
reached:

*>If each point of the plane is assigned a color such that no two points*
*>one inch apart receive the same color, then seven colors are sufficient.*
*>*