Discussion of other student solutions

A. Proof by verification
Student, say Aron, writes a computer program to produce the complete list of groupings - 1680÷6 groupings in all. The list could start like this.
1,2,3  4,5,6  7,8,9
1,2,3  4,5,7  6,8,9
1,2,3  4,5,8  6,7,9
1,2,3  4,5,9  6,7,8
1,2,3  4,6,7  5,8,9
....
Then the computer checks each group and eventually VERIFIES that the statement of the problem is correct. This verification does not constitute a mathematical proof, for the reader has to TRUST that the algorithm used by the computer program indeed works. Therefore the solution will be worth no points. Some students will even write out a few groupings and verify that the statement of the problem is true for the groupings, and therefore, it will likely hold for all groupings. Such false proofs come under what are called Empirical Proof schemes.

B. Brute Force method
A student, say, Emily, produces an argument that considers all the possibilities arranged under a few cases. She places the numbers in one of three sets labeled X,Y,Z. She considers 9 and says it can go into any one of the three sets. So she places 9 in set X. Now, she observes that 8 can not go in to set X (why?). So she puts 8 in set Y. Her sets now look like this:
 Set X   Set Y   Set Z   
 9 ? ?    8 ? ?    ? ? ?
The next step is to place 7. What are the consequences of placing 7 in to each of the sets in turn?
7 with 9
If 7 is paired with 9, then 1 must go with the pair (why?). Similarly, 2 and 4 must be grouped with 8 (why?) But then the remaining numbers, which are 3,5, and 6, when multiplied together, give 90 - too high. Therefore, 7 can not be paired with 9.
7 with 8
Again, 1 must go with 7 and 8 (why?). But then, 2 and 3 must be with 9 (why?). The remaining numbers 4, 5, and 6 multiply together to too much.
7 alone
Our sets now look like this:
 Set X   Set Y   Set Z   
 9 ? ?    8 ? ?    7 ? ?
What numbers can go in set X now? Try 6. If 6, then 1 must also go with it. So the sets look like this now.
 Set X   Set Y   Set Z   
 9 6 1    8 ? ?    7 ? ?
Where would 5 go now? If 5 is placed with 8, the lowest remaining number is 2 and even it can not be placed together with 8 (why?). So 5 must be placed with 7. But if 5 is placed with 7, the only other number that can go with them is 2. But then, the remaining numbers 3 and 4 would have to be placed with 8 (oops!). This means that 6 (and therfore 1) can not go with 9. So we try to put 5 in X with 9. But then, we end up with the same difficulties as with 6 in set X. The only other possibility is a 3 and a 2 with the 9, making our sets look like this.
 Set X   Set Y   Set Z   
 9 2 3    8 ? ?    7 ? ?
Now where does 6 go? Suppose we put 6 in set Y. Then 1 also must go in Y. But then set Z won't work. Same problem arises if we place 6 with 7. Having thus exhausted all the possibilities, the conclusion is that no such groupings exist where none of the sets has products greater than 72. QED
(This solution by Brute Force was sent by André Monette, Thornhill, Ontario, Canada, who qualified for MathPath 2002.)

Remark
Note that André's solution by Brute Force, which is a valid argument, is long. This is often the case with Brute Force. It is the method of proof by exhaustion of all the cases. It is appropriate for some problems. In fact, it is the last resort for some problems. A long-standing famous problem called the "Four Color Problem" was solved by Brute Force in the mid 1970's. It was a very long proof. Two decades later, a shorter proof was found - again using Brute Force. There are problems that only admit a Brute Force solution. You can find many instances of this in the area of mathematics known as Combinatorics. The Four Color Theorem is in that area. However, that theorem has many equivalent formulations in other areas of mathematics, and it is this writer's belief that a proof that does not use Brute Force exists for the theorem. Mathematicians prefer a proof other than by Brute Force, because the Brute Force proof is usually longer and less elegant. However, Brute Force helps us understand the anatomy of the impossibilities that prevent the opposite of the statement we are trying to prove. The proof above by André illustrates this.

Problem 2.
Find the maximum number of acute angles that a convex octagon can have.

We will prove a stronger result. That is, the maximum number of acute angles in a convex n-gon is three.
We will use two results that hold for convex n-gons:
The sum of the exterior angles equals 360°.
The sum of the interior angles is (2n-4) right angles.
These assertions are part of mathematics folklore. The proof of the second assertion rests on the observation that a convex n-gon can be partitioned into n-2 triangles and that the sum of the angles from all these triangles equals the sum of the internal angles of the polygon. The first assertion follows from the second assertion and the fact that the exterior angle at a vertex is supplementary to the internal angle of the polygon at the vertex.

Solution of Problem
Suppose the number of acute angles in the polygon is at least 4. Let I be one of these angles and E its exerior angle. Then, from I acute and I + E = 2 right angles, we get that E > one right angle. So the sum of the four exterior angles is more than four right angles, which contradicts that the sum of all exterior angles is four right angles.
So the number of acute angles is at most three. Can it be three?

We have proved that the number of acute angles in a convex n-gon is at most three. To complete the proof that the maximum number of acute angles is three, we need to prove that, for any n, there is a convex n-gon with three acute angles. We can do this by giving a geometric construction that works for all n. On each of the two ends of a straight line segment BC, erect rays on one side of the segment such that BC makes the same 82.5° angle with each of the rays. Why? Because we need an angle, that is greater than 60 and less than 90, that is constructible with compass and straight edge. On the ray at B, mark a point A that is far enough away from B so that a straight line drawn on A makes 82.5° with AB and meets the ray on C at a point D distinct from C. We now have a quadrilateral with three acute angles A,B, and C. Now draw a line to cut DC at E and meet DA in a point between A and D. Now we have a convex pentagon with three acute angles A,B, and C, as shown in the diagram at left below. From this pentagon, the red line in the right diagram produces a hexagon, again with the three acute angles. By adding lines successively, we get convex n-gons with three acute angles, for all n.

A second solution
Suppose all angles in a convex n-gon are acute.
Then the sum of angles is less than n right angles.
But sum of angles in a convex n-gon is (2n-4) right angles.
So, 2n-4 < n
That is, n < 4
Thus all angles can be acute if n < 4. We know this to be true - the acute 3-gons!
So we consider convex n-gons with n ≥ 4.
Let t be the number of non-acute angles. From the foregoing, t ≥ 1.
Each angle in a convex n-gon is less than two right angles.
So each of the non-acute angles is less than two right angles.
The sum of the angles = t non-acute angles + (n-t) acute angles < 2t right angles + (n-t) right angles
So (2n-4) right angles < 2t +(n-t) right angles
That is, 2n-4 < 2t + n-t
Therefore, n-t < 4. Since n-t is the number of acute angles, we are done.

Remark
This second solution is superior to the first because, in the second, we do not start with a value for the number of acute angles.

A version of the second solution for octagon
A convex octagon has 1080 degrees in it. If only acute angles were used, the total would be less than 720 degrees. Each non-acute angle can be expressed as 90 +acute angle. Therefore, 1080 < 90t + 720, where t is the number of non-acute angles.
12 < t + 8
4 < t, so t is at least 5.
The number of acute angles is at most 8-t = 3.
(This solution was submitted by Henry Scher in his MathPath 2002 Quaifying Quiz answers.)

Example of an incorrect solution
Student S from Maryland submitted the following. This is his exact wording.

"As we are supposed to find the maximum number of acute angles in a convex octagon, we should make the angles as large as possible, which is 89°. Below is a chart I constructed. An octagon has 1080° total by the (n-2)180 formula.
Key:
Column A = Number of 89° angles.
Column B = Number of degrees in total of the acute angles (89×A)
Column C = Number of non-acute angles (8-A)
Column D = Total number of degrees in the non-acute angles (1080-B)
Column E = Average number of degrees in each non-acute angle (D÷C)

A	B	C	D	E
3	267	5	813	162.6
4	356	4	723	181
5	445	3	635	211
6	534	2	546	273
7	623	1	457	457

As can be seen, with angles of 89°, the octagon that is formed is convex. The largest number of acute angles in a convex octagon is three."

Remark
The illustration above using the table shows the PLAUSIBILITY that there can be at most three 89° angles. The illustration also points to the fact that if the sum of the acute angles exceeds 180°, then you can fit three acute angles in to a convex octagon - or any convex n-gon, for n >3. So the illustration helps us to construct a proof based on the idea in the illustration. Because of this, one could be generous and award 50% of the full score for this illustration. The proof given below uses the idea of the illustration.

A third solution
Consider a convex octagon with interior angles A,B,C,D,E,F,G, and H.
Then A+B+C+D+E+F+G+H = 1080, and each angle is less than 180°.
Assume that A,B,C, and D are acute.
Let A = B = C = D = 90-ε, where ε is a positive number less than 90/4.
Then E+F+G+H = 1080 - (A+B+C+D) = 1080 - (360 - 4ε) = 720 + 4ε
Average (E,F,G,H) = 180 + ε
This makes at least one of E, F, G, and H higher than 180, which is not possible in a convex polygon.
If any of E,F,G, or H is made acute, the remaining ones will still have at least one that is higher than 180. However, if D = 90 + 4ε, then A+B+C+D = 360+ε, and E+F+G+H = 720-ε.
Average(E,F,G,H) = 180 - ε/4.
This proves that three acute angles are possible in a convex octagon.
( This proof was sent by André Monette, Thornhill, Ontario, Canada who qualified for MathPath 2002.)

What André proved was that a convex octagon can not have four equal acute angles but can have three acute angles. However, André received full points for his solution because it can be shown that if the polygon can not have four equal acute angles then it can not have four acute angles and, therefore, he has proved that a polygon has atmost three acute angles.

The minor blemish in André's proof may be corrected by revising as follows:
Assume that A,B,C, and D are acute.
Let A = 90-α, B = 90-β, C = 90-g, and D = 90-δ, where α, β, g, δ are postive angles less than 90.
Then E+F+G+H = 1080 - (A+B+C+D) = 720 + (α+β+g+δ). Average (E,F,G,H) = 180 + (α+β+g+δ)/4
This makes at least one of E, F, G, and H higher than 180, which is not possible in a convex polygon.
If any of E,F,G, or H is made acute, the remaining ones will still have at least one that is higher than 180. However, if one of A, B, C, D is made obtuse, say D = 90+ε, then A+B+C+D = 360+ε- (α+β+g), and E+F+G+H = 720+(α+β+g)-ε.
Average(E,F,G,H) = 180 + (α+β+g-ε)/4. If ε > α+β+g, then Average(E,F,G,H) < 180, proving that three acute angles are possible in a convex octagon.

Notice that the revised version of the proof is substantially the same as André's proof. This revised proof can be made to work for any convex polygon, as follows.
Consider a convex n-gon. An equilateral triangle ABC gives a trigon with three acute angles. With AC as base, construct a triangle ACD so that D is not on the side of AC in which B lies and ÐDAC = ÐDCA = 15°. (Note that 15° can be constructed by bisecting 60° and then bisecting one of the resulting angles.)
Then ABCD is a quadrilateral with three acute angles. And a quadrilateral can not have all angles acute because the angle sum needs to be 360°.
So let n > 4.
Let A,B,C,D be acute angles as in the revised version of André's proof. Let E,F,G,H, … be obtuse angles.
Then (E+F+G+H+…) = 2(n-2)90° - [360° - (α+β+g+δ)] = 2(n-4)90° + (α+β+g+δ).
So Average(E+F+G+H+…) = (E+F+G+H+…)/(n-4) = 180° + (α+β+g+δ)/(n-4), etc., showing as in the revised version of André's proof that the n-gon has at most three acute angles.

Remark
André's attempt exemplifies the use of illustrations/examples in motivating proof. Aside from being motivators of proof design, illustrations serve two uses: (a) in clarifying an argument in a proof and (b) in showing that a statement is false. The latter is the main use of illustration: To prove that a statement is false, it suffices to show a single instance where the statement does not hold. Thus if someone said that the square root of every integer is irrational, we could prove it false by exhibiting a single instance such as √4. This is called a counterexample. Occasionally a mathematics proof that looked correct is destroyed by a single counterexample. But the most common use of counterexample is in disproving conjectures - that is, plausible statements that have not yet been proved. Here is a famous example. Pierre de Fermat conjectured that numbers of the form F_n = 2²ⁿ + 1 are all primes. These are called Fermat numbers. In 1732, Leonard Euler found that F₅ = 2²⁵ + 1 = 641×6700417, and hence composite.
(Proof [1]: 641 = 5⁴+ 2⁴ = 5×2⁷+1 divides each of 5⁴ ×2²⁸ + 2³² and 5⁴ ×2²⁸ - 1 and so divides their difference F₅.)
The Fermat numbers are of great interest. Perhaps, the most beautiful aspect of them is the theorem Carl Friedrich Gauss proved at age 17 that, if F_n is a prime p, then a regular polygon of p sides can be inscribed in a circle using only a compass and a straight edge.

REFERENCES
[1]G. H. Hardy and E. M. Wright, An Introduction to the Theory of Numbers, Fifth Edition, Oxford University Press, 1978

Page last updated December 15, 2004
Copyright © 2001–   MathPath
Send suggestions to webmaster@mathpath.org