The Role of Proofs in Lower Grades

Prepared by:

Joseph Malkevitch
Department of Mathematics
York College (CUNY)
s Jamaica, New York 11451

Email: malkevitch@york.cuny.edu (for additions, suggestions, and corrections)

web page: http://york.cuny.edu/~malk

Introduction

What sets mathematics apart from other areas of knowledge such as political science, spanish literature, chemistry, and geology? Is mathematics a science in the same sense that physics and biology are sciences?

While these are very subtle and complex questions, it is important for future teachers to have pragmatic answers to them so that they can help their pupils deal with these important and multifaceted questions.

Mathematicians may use methods that are sometimes akin to what scientists do when they do experiments, but the nature of mathematics appears to be very different from the nature of science. Scientists are attempting to answer questions about the world, the universe as it is. What are stars made of? What are the processes which bring new stars into existence and cause existing stars to stop shining? How does the genome of a giraffe differ from that of a zebra? By contrast, there seems to be no physical location where mathematical facts, known as theorems, are located the way one can locate the planet Saturn. If there were no people there still would presumably be stars and lions. However, if there were no people, most mathematicians think there would be no theorems. Horses seem not to do mathematics.

The way most mathematicians view their subject is that one creates a collection of rules, often called axioms, and deduces consequences from these rules, called the theorems of mathematics. Baseball has rules and the game of baseball emerges from following and carrying out these rules. The game where 5 strikes make an out but otherwise identical to baseball is similar to baseball but not baseball. In a like manner, Euclidean geometry is a body of knowledge obtained from a collection of rules initially set down by Euclid and expanded by others (notably David Hilbert). If one changes the rules one gets new "games" and mathematicians have developed a complex aesthetic to argue why one of these "games" is more "interesting" than some other "game." In particular, if the theorems one proves help one get insights into phenomena outside the field of mathematics, this is a powerful reason to study the type of mathematics that proved valuable. This use of mathematics in areas outside of mathematics has happened over and over again. Results in "so-called" pure mathematics have made CT scans possible, as well as most recent communications technology breakthroughs. Examples include cell phones, DVD discs, and HDTV. However, one can pursue mathematics for its own sake, just for the fun of it, the way so many children do when they play baseball after school.

The nature of mathematics is fairly "heady" stuff for students in early grades. It is pretty "heady" stuff at any level! In this framework of "consequences" of rules, what sets mathematics apart from other subjects is that mathematicians prove theorems. By way of contrast, scientists develop theories which explain what is currently understood but which are always subject to being updated by new discoveries (experiments). Newton's Laws seemed like the ultimate triumph of physics, providing clarity about the nature of how planets moved around the sun in elliptical orbits. These laws worked with such precision that one could make exact predictions about where a planet would be in the future. However, it turned out that Newton's Laws were not fully correct. When discrepancies started to appear in the location of where the planet Mercury should have been, based on Newton's Laws, physicists were initially uncertain as to the cause. However, with the work of Albert Einstein on what has come to be known as the Theory of General Relativity, it became apparent that in the vicinity of objects with large amounts of mass such as the sun, Newton's Laws had to be "modified." With these modifications we now have a better way of viewing the motion of the planets than what was true using only Newton's Laws, though for many purposes the original Newton Laws work fine.

Unlike the need to take current views of the way the physical world works and modify these views or even scrap them as new insights become available, the facts of mathematics, its theorems, stay immutable. Once proved, theorems stay proved and do not have to be modified. (It is true that on rare occasions the standards that constitute a valid mathematics proof have changed and sometimes errors have been found in what were accepted as proofs in the past.)

While children in lower grades can do experiments to help them understand basic ideas in chemistry and physics, are there examples of theorems with non-obvious content that can be proved in lower grades?

While I tend to believe that proving theorems is important, I think it is more important for students and teachers to see more in the way of mathematical ideas and tools. You can not use as a problem solving tool ideas and or concepts of which you are unaware. Thus, I think it is important for teachers to see as broad a range of mathematics during their training as possible.

However, I would like to offer two examples, both of which provide rich possibilities for students in lower grades to see the breadth and depth of mathematics at work.

Pot hole inspection

Imagine that an inspection must be made for pot holes along each section of street indicated in the diagram below (Figure 1). The vehicle carrying out the inspection must start at the location labeled S and as it moves along a street (represented by a line segment in the diagram) the whole street can be surveyed. These are two-way streets so you do not have to worry about that issue. Your goal is to start at S, traverse each section of street once and only once and return back to S. Is such a route possible? If so, give an example of such a route. If a route which traverses each street once and only once is not possible, what is the minimum number of sections of street (line segments in the diagram) that must be be repeated? Can you see why problems of a similar kind to this often occur in urban environments? It is a valuable skill to get students to find other problems that seem similar to ones that they are learning to solve. Figure 1

Repeat the same questions for the street network whose diagram is shown in Figure 2. Figure 2

Facilities location

The location of a collection of apartment complexes (with approximately equal numbers of residents) can be understood by giving them coordinates with respect to a line. For example, in Figure 3 below, complex E is located
at milepost 4 along a highway while complex C is located at milepost -3. The regional department of health wants to locate a mobile vaccination van at a good location, so as to encourage people living along the road to get vaccinated easily. The letters shown in Figure 3 correspond to the locations of the apartment complexes and, here, and in similar facility location problems, they will be called sites. Figure 3

Where should the mobile vaccination van be located?

One can attack each of these problems by "trial and error" and determine a solution. The diagram in Figure 1 admits a tour starting at S which traverses each segment once and only once, while the diagram in Figure 2 does not. For Figure 2 a tour which repeats exactly 3 edges is possible. For Figure 3, if one wishes to minimize the maximum distance that the resident of any apartment complex must drive to the vaccination center, one would locate the center at the milestone numbered one along the highway. If one wanted to minimize the total distance from the vaccination center to the 5 apartment complex sites, one would locate the vaccination center at milepost 2.

What is there about the street network in Figure 1 which makes it possible toavoid repeating edges in an optimal pothole inspection tour? What is there about the street network in Figure 2 that makes repeated edges necessary? Is there an easy way to see how many repeats might be needed? For the facility location problem can this problem be solved easily for any number of sites and pattern of distances between them?

What is attractive about the two situations above is that one can easily describe mathematical answers to these questions, which apply for diagrams similar to but not identical with those in Figures 1, 2, and 3. Thus, while it is possible to solve questions of this type using ad hoc methods, there is an especially simple way to use basic mathematical ideas to answer the questions just raised in general terms, rather than for the specific example given here. Although the pothole problem is perhaps more complex to treat, let us look at that example first.

The general result is given by a theorem of Euler from 1732. Strictly speaking Euler did not answer both directions of the result I will now discuss but his seminal idea was using the diagrams with dots and line segments (or curves) such as those above to get insight into problems of this sort. From there, things are relatively easy.

Diagrams such as those in Figure 1 and Figure 2 are known as graphs. The dots are known as vertices and the line segments are known as edges. The number of line segments that meet at a vertex is called the degree or valence of a vertex.

Here is another graph diagram to help make sure the ideas are clear. The numbers next to each vertex give the degree or valence of that vertex. Figure 4

Vertices that have an even number of edges at a vertex are called even-valent; vertices that have an odd number of edges at a vertex are called odd-valent.

Here is Euler's amazing theorem:

A diagram which consists of dots and lines and for which it is possible to walk along edges between dots using line segments has a tour that starts and ends at any vertex S if and only if the diagram has an even number of edges at each vertex.

Graphs which have the property that one can walk between any pair of vertices using edges are called connected. In honor of Euler, a tour which starts and ends at the same vertex S of a connected graph, and which traverses each once and only once is called an Eulerian Circuit.

Thus, we can start the result that interests us as saying that a connected graph has an Eulerian circuit only if all its vertices are even-valent. Amazingly, not only is this true but the converse statement is also true. If a connected graph is even-valent then it has an Eulerian Circuit.

Here is the proof of the easier result, namely, that when a (connected) graph has an Eulerian Circuit the graph must be even-valent. Suppose that a connected graph G has an Euler Circuit C starting at S. Then S must be even valent because every time one leaves S using some edge of C one must come back to S on a different edge of C because the definition of an Eulerian Circuit precludes using the same edge twice. Thus, the edges at S must be used in pairs, and, hence, S is even-valent. Similarly, if T is any other vertex of G different from S one must enter and leave T on different edges. Again, this means that the edges at T can be paired and, thus, it, too, must be even-valent.

The proof that a graph has an Eulerian Circuit if it is connected and even-valent is a little harder. One idea is to pick a start vertex and construct a "loop" of edges (e.g. a simple circuit) which starts and ends at that vertex. Delete the edges in this circuit and then paste together other circuits to this one using vertices of this circuit until one builds up an Eulerian Circuit. As each new circuit is added to the original collection we traverse the new circuit before returning to the existing collection of edges we are building up.

If a graph does not have all of its vertices being even-valent, then it turns out that the number of vertices which are of odd degree must be even. The number of repeated edges that must be traversed when there are 2m odd degree vertices is at least m. For example, for the graph in Figure 2 there are 6 vertices of odd degree. Thus, the number of repeated edges in a tour which visits each edge at least once and returns to its start vertex is at least 3.

Once one has this result one can take a quick glance at a diagram such as the one in Figure 5 and tell that it can not have an Eulerian Circuit because it has vertices of odd valence. Since there are four odd-valent vertices there must be at least 2 repeated edges for a tour that visits each edge at least once and starts and ends at the same vertex. Figure 5

It is rare that one can see as transparently with such a simple argument the proof a very important pure and applied mathematical result.

Now let us turn our attention to the facility location problem.

Given the points located along a line as shown in Figure 3 or Figure 6 Figure 6

which point X along the line will:

a. Minimize the maximum distance from the seven sites?

b. Minimize the sum of the distances from the sites to X?

A bit of trial and error will convince you that if one takes the coordinates of the points and computes their median, this will be the answer for problem b., while if one takes the mean of the coordinate for the point on the far left and the far right, this will answer the question for problem a.. The fancy name for this number is the mid-range value. The range of a set of data is the largest value minus the smallest value. Thus, the mid-range value is a number which marks the halfway point between the largest and smallest values. This number can be computed by taking the mean of the largest and smallest values. Note that if there is an odd number of measurements, the median must be one of those measurements while the mid-range value may or may not correspond to one of the sites. Thus, for Figure 3 the mid-range value is 1, which is not a site, while for Figure 6 the mid-range value is 2 where one of the sites is located. The same is true for the median when there is an even number of sites. The median may or may not be located at one of the sides. Also, when there is an even number of sites the location L which minimizes the total distance need not be unique but L may be located at infinitely many points. Furthermore, you should verify for yourself that locating the vaccination van at the mean of the coordinates of the sites does not minimize the total distance (when the mean and the median do not coincide).

Here is the proof that when there is an odd number of sites, the median minimizes the total distance to the sites involved. Note that when one minimizes the total distance, one also minimizes the mean distance. Suppose the coordinate of the median is M, and that we move m units to the left of the median to position the vaccination van. Since there is an equal number of points to the left and right of the median, the points to the left will have to go less far to reach the vaccination van and those to the right will have to go further, but by exactly the same amounts. Since in this new location people located at the median will have to go m units, we see that the new location of the van requires a larger total distance of travel. A similar argument shows that locating the van to the right of the median will also raise the total distance. Can you see how to argue when there is an even number of sites that the median will still be the optimal place to locate in order to minimize the total distance? Very similar arguments go to show that the mid-range value will minimize the maximum distance from any site to the vaccination van.

A challenging way to extend the domain of thinking with regard to the facility location situation is to consider where the optimal location should be to minimize the maximum distance (or minimize the total distance) when the vaccination van must be located at one of the existing sites. It is also useful to have students brainstorm about problems similar to this one where one is locating some service other than an vaccination van. This might be a hot dog stand at the beach, an ice cream truck or a new firehouse. Students might also consider what to do when there are different numbers of people at the different site locations.

Acknowledgment

This work was supported in part by the Teacher Academy of York College. Specific funding was provided by: FIPSE (46274-07 01) and the Fund for PS (72042-07 01) to the Teacher Academy of CUNY.