By

Adam P. Deutsch

Allderdice High School

Guided Entry

Introduction

Unit Overview

Lesson 1 – Problem Solving and Argument

Lesson 2 - Mine Sweeper, Logic and Argument

Lesson 3 - What Do We Know About Tic-Tac-Toe?

Lesson 4 – An Introduction to Proof by Definitions and Axioms

Connections

Appendix A

Appendix B

Sources

In 1989 the National Council of Teachers of Mathematics (NCTM) released its Standards for mathematics curriculum and evaluation. The standards recommended "that Euclidean geometry no longer be developed as a complete axiomatic system" (p.186). Repeatedly, the document seemed to imply that formal methods for doing proof – rigorous deductive reasoning, indirect proof, and proof by induction – be reserved for "college-intending" students (p. 143). Many interpreted the Standards as denouncing the teaching of proof. Numerous geometry texts have since been published which sweep proof into the corner, paying it little more than lip service. More and more frequently the question is asked by teachers and students alike, "why teach/learn proof?" Now we learn of the "death of proof", another in a history of crises in mathematics which makes the question seem even more relevant.

Very little of today’s mathematics seems to take on the classical form of the logical, deductive proof. At least that is how it appears. Proofs of hundreds of pages, understandable to only a handful of mathematicians with expertise in highly specialized branches of mathematics, are now more typical of the work being done in mathematics. So if what we "fondly" remember as "proof", the axiomatic system of logic we learned in our high school geometry classes doesn’t resemble the work that mathematicians are currently doing, why indeed should we be teaching proof? And if in fact we do believe that teaching proof is valuable, what exactly, should we be teaching students that proof is?

Proof is the method mathematicians use to communicate the truth or validity of a piece of knowledge. While the specific form proof takes may have undergone transformations over the centuries – generally changing as the kind of mathematics being done has changed – the notion of communicating an important result through an argument meant to convince the reader of the validity of the result is still at the heart of doing proof and in fact, doing mathematics. . And the notion of proof transcends mathematics – logical argument is at the heart of philosophy, the law, rhetoric and debate. The idea of proof certainly influences the scientific method and is part of the formal presentation scientists use to forward a new idea or result. The value of teaching students the fundamentals of mathematical proof cannot be denied.

At their annual meeting in Chicago in April of 2000, the NCTM released their revised Principles and Standards for School Mathematics. In this new document the reasoning standard of the 1989 document was changed to "Reasoning and Proof". Specifically, the standard now states:

Instructional programs from pre-kindergarten through grade 12 should enable all students to -

• recognize reasoning and proof as fundamental aspects of mathematics;

• make and investigate mathematical conjectures;

• develop and evaluate mathematical arguments and proofs;

• select and use various types of reasoning and methods of proof.

(p. 56)

It appears that it was never the intended message of the NCTM’s 1989 Standards that high-school mathematics programs do away with formal proof as part of the general mathematics curriculum. In developing the reasoning and proof standard, the NCTM goes on to say, "High School students should be able to present mathematical arguments in written forms that would be acceptable to professional mathematicians" (p. 58). In the "Geometry" standard in particular, the Standards state, "judging, constructing, and communicating mathematically appropriate arguments remain central to the study of geometry. Students should see the power of deductive proof in establishing the validity of general results from given conditions" (p. 310).

High-school geometry is the traditional course in which students have first encountered the idea of formal proof. This is natural as Euclidean geometry is a relatively simple yet fully developed axiomatic system which provides an excellent vehicle for introducing formal proof. Geometry also comes relatively early in the traditional sequence of high-school mathematics thus setting the stage for proof in higher level courses such as elementary analysis (pre-calculus) and calculus. In the Pittsburgh Public Schools however, proof is no longer part of the regular or even "scholars" geometry classes.

The purpose of this unit is to enrich the current curriculum of the Pittsburgh Public Schools Geometry course, and to provide a stepping stone toward integrating proof throughout the current course. The unit has a two-fold emphasis. First, the unit will focus on mathematical proof as a means of communication. The unit will open with a series of problem solving activities geared to demonstrate to students an informal notion of proof as a well stated argument for the correctness of a result (in this case the solution to a problem). Good communication skills will be stressed as students both write their arguments and present them orally. The second emphasis is naturally, the formal notion of proof. The formal idea of proof will be developed and refined as the unit progresses until students are working on proofs within a very formal axiomatic system.

This unit is to serve as an introductory unit to the course of study of geometry for the Pittsburgh Public Schools (and as a replacement for the first unit of the current course). It could just as easily be used in other courses (for example as an enrichment unit in an Algebra 1 class or in a Problem Solving class). As such it is designed for students who have a rudimentary knowledge of algebra but little or no formal exposure to the content of plane geometry. In addition, it is understood that students taking this course will have had little or no exposure to formal methods of mathematical proof.

Where used as the introductory unit to geometry, the intention of the unit is to serve as a platform for integrating proof throughout the course. At the end of the description of the lessons given here, suggestions will be given on how this might be done. These suggestions will be based on the current geometry course being taught in the Pittsburgh Public Schools, but the suggestions should be adaptable to most basic geometry courses.

Each of the "lessons" in this unit will require three to four days to complete. The entire unit, with time included for assessment, should take no more than 17 days (3.5 weeks). This is essentially equivalent to the amount of time spent on the first unit of the current course of study in the Pittsburgh Public Schools.

Objectives: Students will construct well reasoned arguments about their solutions to problems. Students will discuss and critique the arguments presented by their peers.

Rationale: Solutions to problems are clear opportunities for students to communicate how they know what they know. The following problems have been chosen because they allow for a "reasoned" explanation of the solution as opposed to a simple "demonstration" of the solution. In other words, these problems present opportunities for students to develop arguments in defense of their solutions. At this point, the operating definition of proof in the classroom will be an informal one – based on student understanding of the concept. When students have solved these problems and suggested an answer, the demand will be "prove it!"

Consider an 8x8 square (like a checkerboard). If two opposite corners of the board are removed, can you cover the square in 1x2 rectangles (like dominoes)? Why or why not?

This problem is an excellent problem which students at all levels can engage and experience some degree of success with. Simple trial and error will convince most students that it is not possible to cover the checkerboard with the dominoes. Students will then have the opportunity to attempt to formulate arguments for why it is not possible. Students will attempt this at varying levels of sophistication and with varying degrees of success. The problem is also quite useful in demonstrating the idea of an elegant/surprising/insightful proof. The argument is simple and relies on thinking about the 8x8 square as a checker (or chess) board. On such a board, adjacent squares are different colors. A domino always covers adjacent squares, and therefore must always cover two squares of different colors. Opposite corners of an 8x8 board however have the same color. Thus removing these squares leaves 30 squares of one color and 32 squares of the other color. Since these two values are not equal, it is not possible to cover the board given the conditions described.

A man is camped at the foot of a mountain, at dawn he breaks camp and begins hiking up the mountain. He reaches the peak of the mountain at sunset and camps out for the night at the summit. At sunrise on the next day he breaks camp and begins hiking down the mountain using the same path he took on the way up. He reaches his original camp at sunset. Is there necessarily a point on the path at which the man arrives at the same time of day on both days? Why or why not?

This problem once again has an elegant proof providing insight into the problem. It is included here because whether or not students are successful with the problem, simply engaging the problem requires reasoning. As with all the problems in this section, students should be made to focus on their own reasoning processes by communicating with others (orally and/or in writing) their thinking on the problem. The answer to problem is that yes, there must be a point on the path at which the man arrives at the same time of day on both days. Students may argue based on elements of distance, rate and time in this problem, or argue graphically. An elegant verbal argument for the solution to this problem is to consider the two hikes as occurring simultaneously – that is as if taken by two different men on the same day rather than the same man on two different days. When the problem is considered in this way, the solution becomes clear, the two men making the hike will of course pass each other at some time during the day. This corresponds to the point that the man alone would have reached at the same time on the two days.

Cryptarithmetic problems provide good opportunities for students to construct reasoned arguments for their solution. A classic example is the one about the young man who was away at college and sent home the message:

SEND

+ MORE

MONEY

Each letter stands for a different digit from 0 – 9 and the object is to find the values which make the expression true.

Cryptarithms provide students opportunities to reason by cases and to reason by contradiction. By breaking the problem down into possible values for the letters and then reasoning backwards into contradictions, the values for each letter can be deduced. These types of problems then, give students an opportunity to organize their work and systematically work out a deductive argument. This gives valuable experience for later when formal methods of proof are introduced.

Classic logic problems. Example: Ted, Ken, Allyson, and Janie (two married couples named in no particular order) each has a favorite sport. The sports are running, swimming, biking and golfing (again, in no particular order). Determine from the following clues who likes which sport:

A. Ted hates golf: he agrees with Mark Twain who said that "golf is nothing but a good walk spoiled."

B. Kent wouldn’t run around the block much less run a few miles. His wife doesn’t enjoy running either.

C. Each woman’s favorite sport is one of the sports featured in triathlons.

Allyson bought her husband a new bike for his birthday as his old one was pretty well worn out from all the riding he does.

Classic deductive reasoning is the key to solving these types of logic problems. Essentially students are reasoning from initial given information to conclusions about that information, similar to the classic proof process of geometry. The "givens" being axioms of a logical system and the conclusions being the "theorems". Once again students should focus on how they communicate their arguments for their solutions. At this point structure of an argument may be highlighted. For example, in this problem it is stated that the women prefer sports featured in a triathlon. Now a triathlon is a grueling marathon of swimming, running and biking. From this we can conclude that golf is not one of the sports favored by either of the women, it must be preferred by one of the men. But from clue A it is given that Ted hates golf, thus golf must be the sport enjoyed by Kent. The same argument can be given structure by syllogistic reasoning as follows:

1. A triathlon consists of running, swimming and biking.

2. From clue 3 we know that the women prefer sports featured in a triathlon.

3. Therefore from statements 1 and 2 we can conclude that neither woman prefers golf.

Thus, golf must be the favorite sport of one of the men.

4. From clue 1 we know that Ted hates golf.

5. Therefore Kent must be the person who enjoys golf.

The SHIP/DOCK Theorem. In this problem a given word (SHIP) is to be changed into another word (DOCK) by changing just one letter at a time. Given that every word in the English language contains at least one vowel (a, e, i, o, u, or y) prove that any solution to the above problem (for there are many different solutions), must contain at least one word with two vowels.

Once several solutions to this problem have been found by students, students should be given the opportunity to compare solutions and to attempt for formulate an argument for the conclusion suggested. Once again, this problem provides an opportunity to introduce formal structure to the arguments given. Consider:

1. It is given that every word in the English language contains at least one vowel.

2. In the word SHIP, the vowel is located at position 3 (from left to right).

3. In the word DOCK, the vowel is located at position 2 (from left to right).

4. Therefore when transforming SHIP to DOCK, the letter in position 3 must shift from a vowel to a consonant, and the letter in position 2 must shift from a consonant to a vowel.

5. This may happen in one of three ways:

Case 1 – The letter in position 3 is changed to a consonant before the letter in position 2 is changed to a vowel. But this creates a word with no vowels which violates statement 1.

Case 2 – The letter in position 3 is changed to a consonant at the same time as the letter in position 2 is changed to a vowel. But this requires that both letters change in the same step which violates the rules of the problem.

Case 3 – The letter in position 2 is changed to a vowel before the letter in position 3 is changed to a consonant. This creates a word with two vowels.

Development: It is expected that this lesson should take 3 to 4 days to complete. The problems posed here are only suggested problems and are not intended to form the entire basis for this lesson. It is recognized that all teachers have a bank of favorite problems and teachers of this unit should supplement the problems given here. The problems selected were chosen because each provides an opportunity for students to apply skills of reasoning to solve and therefore defend their solutions. Since it is the purpose of this lesson to begin developing powers of argument, problems with mainly computational solutions would not be as useful for this lesson. The emphasis during this lesson should be on the development of good argument. Students should be given the opportunity to write out explanations for their problem solutions and much time should be given during class for students to present their solutions and discuss the them. Opportunities will arise to compare arguments for solutions and the teacher should highlight particularly elegant solutions and well communicated solutions.

Objectives: Students will develop and communicate reasoned arguments about the locations of bombs and "safe spots" in the game mine-sweeper.

Rationale: Mine Sweeper is a simple game of strategy in which a player must use logic to determine which cells (squares on an nxm rectangular grid) contain bombs, and which do not. The game provides the opportunity for students to construct brief logical arguments regarding the placement of bombs or the location of "safe" cells on the board.

Development: In the game Mine Sweeper (a solitaire computer game), a player is given an nxm grid with a predetermined number of bombs hidden in the square. The player "opens" cells looking for the bombs. A cell may be blank, contain a bomb, or contain a value which reveals the number of bombs in immediately neighboring cells (see figure). Mine Sweeper comes with most PC’s as a demonstration game and is easily available on the Internet as free-ware – that is, it may be downloaded and used free of charge.

One class period should be devoted to students learning and playing the game. No connection should be made in the beginning to argument or proof. Students will learn the game and play several rounds to get a feel for the game. On day 2, a class discussion on how a player can determine where bombs are located or where they are not located will give students the opportunity to express their reasoning in playing the game. If possible, the teacher should begin a game and allow students to give input on moves. For each move, the teacher should ask the student to defend their thinking ("Why should I open this square?" "How do you know it is safe?" "How do you know a bomb is located in this square?") In assessing students understanding of the game and the logical thinking required by the game, students will then be given several "mock" mine-sweeper situations and be questioned as to how they would proceed in the play of the game. Students would be required to explain their strategy by giving reasoned arguments for whether or not a given square might contain a bomb. For example in the

illustration pictured at the right, reasoned arguments can be given to identify one cell which definitely contains a bomb and to identify one cell which cannot possibly contain a bomb and is therefore safe to uncover. An analysis of this problem is given in the supplement to this lesson.

This lesson should take 3 to 4 days to complete.

Supplement –One Mine Sweeper analysis: In the board pictured at the right it can be concluded that there must be a bomb in the shaded square adjacent to the lower right hand corner square. This must be true because this is the only uncovered square which borders the lower right hand corner square and the corner square contains a 1 which means it must border a square with a bomb in it.

From this result we can conclude that the second column from the left contains at most two bombs. One of the top two cells in this column must contain a bomb because the top cell of the third column has a 1 in it meaning it borders a bomb. Now consider this as two cases:

CASE 1: The top cell contains a bomb. In this case, the second and third cells in the column cannot contain bombs because the second cell in the third column borders both of these cells (as well as the top cell), and it only borders one cell with a bomb.

CASE 2: The second cell in the column contains a bomb. In this case, the first and third cells must be bomb free because the top cell of the third column borders both the first and second cells of the second column and it borders only one bomb. The third cell of the third column only borders 2 bombs, and we know the placement of one of those bombs, so if the second bomb is located in the second cell of the second column, the third cell must be empty.

Notice that in both of these two cases, the third cell in column two must be bomb free. This means that we can proceed to open this square safely and learn more about how the bombs are situated.

See Appendix A for additional Mine Sweeper problems which may used as practice exercises or assessments of student understanding.

Objectives: Students will develop and communicate well reasoned arguments about their knowledge of Tic-Tac-Toe.

Rationale: Almost all students are familiar with the game tic-tac-toe and most have some fairly well formulated understandings about the game and strategies for playing the game. The game is simple enough to allow students to construct reasoned arguments about those strategies. The goal of this lesson is to help students to construct those arguments and communicate them clearly.

Development: As a whole group, the class will discuss the game of tic-tac-toe. The teacher will guide the discussion asking students to express their knowledge of the game and strategies for the game. After an overview of the structure and rules of the game have been established, the teacher should guide the discussion to questions of strategy. In particular, reasoned arguments should be developed to answer questions such as: given the game of tic-tac-toe (already in progress) at the right, prove that as long as player X plays by a winning strategy, X will win this game.

Building on similar examples, students should work at developing an argument to prove that there is a strategy for the first player (generally X) such that player X can ensure that the second player (generally O) cannot win. This argument may be developed by exhaustively considering cases of the game move by move. Initial consideration should be done as a class discussion in class with other cases remaining as student assignments to assess student understanding and to give students practice in developing logical arguments. Complete analysis of one case is given below. It can be proved that tic-tac-toe is a trivial game, that is, that there is no winning strategy for either player (i.e. both players X and O have strategies which can prevent the other from winning the game). Though this is a much lengthier result to prove, students should be able to construct a framework for such an argument – it is not necessary at this point for student to complete such a proof.

Supplement - Tic-Tac-Toe Cases: By breaking down the game of Tic-Tac-Toe into cases based on moves made by each player, the game can be exhaustively analyzed. This is because the game is a finite game – there are only a limited number of possible game outcomes. For player one (X) there are essentially three possible opening moves. The player may move in the center square (case 1), one of the four corner squares (case 2) or on of the four side squares (case 3):

Some class discussion should take place to allow students to convince themselves that in fact a all first moves into any one of the four corner squares are equivalent (and likewise for any first move into one of the four side squares). Thus there are three opening cases. We will consider just case one here. In fact, it is only necessary to consider this one case, because all we are attempting to do here is produce a strategy for X which will make it impossible for O to win. We will find from an exhaustive consideration of Case 1 that by choosing the center square, it is always possible for X to prevent O from winning. Thus we can conclude that this is in fact the desired first move to meet our goal. Note that this is very different from attempting to find a winning strategy for X.

If player X moves into the center square, there are two possible moves for his opponent, a corner square or a side square. Once again students should be given the opportunity to discuss why in fact all possible eight moves for O can be considered as just two cases. Thus we now have:

As a class discussion the teacher should now focus on case 1A. How many moves are now possible for player X? Which moves are equivalent, and which moves are truly different? In fact there are now 4 different moves X may make. X may move into (1) a side square adjacent to O’s move, (2) a corner square adjacent to one of those aforementioned side squares, (3) one of the side squares not adjacent to O’s move, or (4) the corner square opposite to O’s move.

Thus we now must consider four sub-cases of 1A:

Three of these four cases (i, ii and iii) can be shown to be winning cases for X if O does not make a specific "blocking move" on the next move. In each of these instances, the strategy chosen by X has been successful in that we have attained our goal of preventing O from winning. It is not necessary for us to continue in these cases. Students will see this immediately and there should be no difficulty in proceeding with these three cases as if O had already made the blocking move. Let’s consider Case1Ai from that perspective now. Once again we must answer the question, what are the possible moves for X and break the problem down further into cases.

Most of the cases from this point on can be quickly dispatched. In the specific example here, X has five possible moves. Four of the moves will require that O make a blocking move, or else lose the game. Only a move by X into the lower right hand corner leaves O with other options. In addition, in two of the four moves which force O to make a blocking move (X moving into the upper right hand corner or right side block), when O makes the required move, X will be required to make a blocking move as well to prevent O from winning. It can quickly be shown that each of these cases will result in a draw which means success – that is, preventing O from winning. Naturally, in class, these arguments will need to be considered in full as they give students the opportunity to completely argue a case to its full conclusion. This of course is the desired result of this lesson.

In two other cases (X moving into the lower left hand corner or left hand side block), O will be forced to make a blocking move but X will have a number of alternative moves after O makes the blocking move. It can be quickly shown once again that further moves by X and O will result in draws. Again, such a result means success for X in that X has prevented O from winning. These cases are left to the reader and to students to analyze and dispatch.

Finally we must consider the case where X moves in the lower right hand corner of the board. Let’s call this case Case 1Ai-Final. The situation is pictured at the right. Here, O has four possible moves. Two of them (either the side or corner square on the left) result in forcing X to make a blocking move. In both cases, the move made by X forces O to make a blocking move or lose, and the last move will result in a draw because it becomes impossible for either X or O to get 3 in a row.

The other two options left to O are the two open squares on the right hand side. Once again it can be easily shown that either one of these moves either allows X ultimately to win or to force a draw (it is left to the reader to exhaust these cases) in either case successfully preventing O from winning the game.

To the extent that time permits, students should be given the opportunity to explore as many of the open cases presented here as possible. An exhaustive analysis of all cases forms a proof of our assertion that player X has a strategy which prevents O from winning the game.

Objectives: Students will develop a simple number theoretic system of definitions and an axiom in which to construct simple proofs.

Rationale: The classical study of geometry is the study of a formal axiomatic system. A body of knowledge is constructed from a set of basic elements (point, line, plane), definitions based on those elements and assumptions about the behaviors of those elements. Simple number theory of evens, odds and divisibility provide a basic arena for constructing formal proof.

Development: In this lesson, proof will be considered quite formally. Students will first be introduced to the idea of building a knowledge base from a set of basic, described (though undefined) elements and assumptions about the behaviors of those elements which are agreed to, but left unproved. In the system to be developed here, the undefined elements will be the set of natural numbers (unsigned integers), and two operations on those numbers (addition and multiplication):