Proximity
Problem
|
We are given a regular icosahedron having three red vertices. Show that it has a vertex that has at least two red neighbours.
If you're stuck, try this proof sorting activity.
|
Image
|
Getting Started
We have to prove the statement:
If a regular icosahedron has three red vertices then it has a vertex that has at least two red neighbours.
We can use an argument by contradiction. We suppose that NO vertex has more than one red neighbour and reach a contradiction thus showing that this statement must be false
Without loss of generality you can think about the top vertex being red and decide what that means for the other vertices around it.
Student Solutions
Solution to Proximity by Tony and John, State College Area High School, PA, USA.
Image
|
We give a proof by contradiction.
Suppose no vertex has more than one red neighbour.
Without loss of generality say the vertex at the top is red.
Then none of the five vertices around the upper horizontal
pentagon, which are neighbours of the top vertex, are red. This is
because if any of them were red then there would be two vertices
each having two red neighbours which is not allowed.
|
Now consider the five vertices around the lower horizontal pentagon. Only one of these can be red because if two were red then there would be a vertex with two red neighbours which is not allowed.
The argument shows that of the eleven vertices discussed only two can be red. We know that there is a third red vertex so it must be the vertex at the bottom. However if the bottom vertex is red then there will be two vertices on the lower horizontal pentagon having two red neighbours which is not allowed.
We have reached a contradiction.
So the assumption that no vertex has more than one red neighbour is false.
We have proved that there is at least one vertex with two red neighbours.
Teachers' Resources
Why do this problem?
The result can be proved by an argument using proof by contradiction and it is a useful example of this type of reasoning. It also calls for visualisation and to clearly explain the reasoning provides learners with another challenge.
Possible approach
You might discuss arguments by contradiction with the class first. We often use arguments by contradiction in ordinary conversations that are nothing to do with mathematics.
You might want the class to realise that a statement and its contrapositive are always logically equivalent. If we consider a statement and its contrapositive, and we can prove one of them, then we have also proved the other statement.
One approach is to ask the learners to make up 'If ...then... " statements of their own and write down their contrapositives. (See Possible support below).
Invite the class to try to prove the Proximity result using an argument by contradiction. A good strategy in cases like this is to ask the learners to work individually for a short time, then to work in pairs and explain their arguments to their partner and agree on the best argument, then to work in fours so that each pair explains their argument to the other pair and they try to get the best
argument possible between them. Then invite groups to come to the board and try to convince the whole class that their argument works.
An alternative approach to consider is to work with your learners on the NRICH resource Contrary Logic first and then to tackle the Proximity problem.
Key Questions
If you turn the statement you are trying to prove round to use a proof by contradiction what would you start by assuming?
If the icosahedron has 3 red vertices is there any loss of generality in taking the top vertex to be red?
If the top vertex is red, what can you say about the other vertices around it?
Possible extension
Learners might try Proof Sorter to prove that the square root of 2 is irrational.
A natural follow up, and re-inforcement for confidence in using this sort of argument, would be to work on the resource Contrary Logic.
Read the article on Proof by Contradiction .
Possible support
Even small children will understand the logical equivalence of the following statements, supposing the only money they have to spend is the pocket money they get on Saturdays:
(1) If you spend all your money on Saturday you will have none to spend for the rest of the week.
(2) If you have money to spend in the rest of the week you did not spend it all on Saturday.
These two statements are contrapoitives of each other. For another example, if we are talking about polygons, then the two statements (3) and (4) below are logically equivalent.
(3) If this figure is a triangle then it has three sides
(4) If this figure does not have three sides then it is not a triangle.