Tuesday, December 9, 2014

Section 7-6: Properties of Special Figures (Day 76)

Section 7-6 of the U of Chicago text discusses special figures -- that is, parallelogram and regular polygons.

Dr. Hung-Hsi Wu already discussed how to prove the properties of a parallelogram using rotations, and we already gave Dr. Wu's proof. The U of Chicago text also gives a more traditional proof, by dividing the parallelogram into two triangles and showing that these triangles are congruent.

The text also provides the theorem:
The distance between parallel lines is constant.

Recall that we've discussed this theorem already -- back when we were discussing the webpage of Jen Silverman, who defines parallel lines as those having constant distance between them.

So the theorem that I want to focus on is the Center of a Regular Polygon Theorem:
In any regular polygon there is a point (its center) which is equidistant from all its vertices.

But before we get to this theorem, let me remind you that I promised you a Putnam problem. So here is question B-1 from the 75th annual Putnam exam. I obtain the text of the question from the website The Art of Problem Solving. It was posted by Kent Merryfield, a mathematician from California State University, Long Beach:


"A base 10 over-expansion of a positive integer N is an expression of the form N=d_k10^k+d_{k-1}10^{k-1}+\cdots+d_0 10^0 with d_k\ne 0 and d_i\in\{0,1,2,\dots,10\} for all i. For instance, the integer has two base 10 over-expansions: 10=10\cdot 10^0 and the usual base 10 expansion 10=1\cdot 10^1+0\cdot 10^0. Which positive integers have a unique base 10 over-expansion?"

(Ah, the LATEX symbols that Dr. Merryfield uses here cut and paste nicely here!)

So how does Dr. Merryfield solve Putnam problem B-1? As it turns out, he uses a proof technique called mathematical induction. Most proofs in a high school geometry course aren't proved used mathematical induction. Indeed, only one proof in the U of Chicago text is proved this way -- and it just happens to be the Center of a Regular Polygon Theorem! Furthermore, Dr. Wu uses induction in his proofs on similar triangles, so this is a powerful proof technique indeed. (On the other hand, Wu simply defines a regular polygon as an equilateral polygon with a circle through its vertices, so he would have no need to prove the following theorem at all.)

So here is the proof of the Center of a Regular Polygon Theorem as given by the U of Chicago -- in paragraph form, just as printed in the text (rather than converted to two columns as I usually do):

Analyze: Since the theorem is known to be true for regular polygons of 3 and 4 sides, the cases that need to be dealt with have 5 or more sides. What is done is to show that the circle through three consecutive vertices of the regular polygon contains the next vertex. Then that fourth vertex can be used with two others to obtain the fifth, and so on, as many times as needed.

Given: regular polygon ABCD...
Prove: There is a point O equidistant from A, B, C, D, ...

Draw: ABCD...

Write: Let O be the center of the circle containing A, B, and C. Then OA = OB = OC. Since AB = BC by the definition of regular polygon, OABC is a kite with symmetry diagonal OB. Thus ray BO bisects angls ABC. Let x be the common measure of angles ABO and OBC. Since triangle OBC is isosceles, angle OCB must have the same measure as angle OBC, namely x. Now the measure of the angles of the regular polygon are equal to 2x, so angle OCD has measure x also. Then triangles OCB and OCD are congruent by the SAS Congruence Theorem, and so by CPCTC, OC = OD. QED

Now the "Analyze" part of this proof contains the induction. If the first three vertices lie on the circle, then so does the fourth. If the fourth vertex lies on the circle, then so does the fifth. If the fifth vertex lies on the circle, then so does the sixth. If the nth vertex lies on the circle, then so does the (n+1)st. I point out that this is induction -- from n to n+1.

Every induction proof begins with an initial step, or "base case." In this proof, the base case is that the first three points lie on a circle. This is true because any three noncollinear points lie on a circle -- mentioned in Section 4-5 of the U of Chicago (delayed until Chapter 6 on this blog). The induction step allows us to prove that one more point at a time is on the circle, until all of the vertices of the regular polygon are on the circle.

To understand Dr. Merryfield's induction proof, let's begin by restating the problem. He writes:

"This is not part of the solution, but in order to actually write down over-expansions, I used the symbol X as the symbol for 10 as a digit. Hence we can write 103 as X3, or 203 as 1X3, or 2030 as 1X30 or 202X or 1X2X. We can write 110 as 10X or XX."

So now we see what exactly this "over-expansion" really is. In addition to the ten digits 0 to 9 that we normally use, there is this new digit called X, for ten. Many numbers that are written with this new digit X can be written without X. So, as Merryfield writes above, the number X3, with 3 in the ones place and X (or ten) in the tens place, really means 103. The current year 2014 is also 1X14.

Here's what the question is asking -- some numbers have two over-expansions, such as 103 = X3. But other numbers have just one over-expansion, such as 34. Which numbers have only one? And here is the answer:

"N has a unique over-expansion if and only if its ordinary decimal expansion has no zeros."

To prove this, Merryfield uses induction. He writes:

First, suppose that the decimal expansion of N has no zeros. That is, N=\sum_{k=0}^m d_k10^k where d_k\in\{1,2,\dots,9\}. Suppose also N=\sum_{k=0}^{m'}e_k10^k where e_k is also allowed to be 0 or 10. Note that N\equiv d_0\pmod{10} and N\equiv e_0\pmod{10}, so d_0\equiv e_k\pmod{10}. But with 1\le d_0\le 9, the only way to satisfy this congruence is to have

What Merryfield is doing here is the initial step of the induction -- the ones place. What he's saying is that if the ones place is a 0, it can be changed to a X and vice versa (say, from 20 to 1X and back), but if the number is from 1 to 9, it can't change. For example, if the ones place is 1, then the best we could do is convert a ten into ones, which would put an 11 in the ones place. But the highest digit that we can put in a place is X or ten. Therefore, the ones place cannot change.

Now for the induction step. Instead of the ones place, we're now in the tens, hundreds, or some other place, and we know that the current digit is from 1-9, and that we can't change any of the digits to the right of the current digit. Merryfield writes:

Now, suppose we have proved that for 0\le k\le j. Consider the number 10^{-j}\left(N-\sum_{k=0}^jd_k10^k\right), and find what it is congruent to \mod{10}. By a very similar argument to the above, we find that e_{j+1}=d_{j+1}. So by induction, we conclude that for all k and the over-expansion is unique.

In other words, all of the digits to the right are 1-9, so once again, at the current place, we can only change 0 into X and vice versa. The reason for this induction step is, for example, when we change from 20 to 1X, we did change the tens digit from 2 to 1 -- but that's because the ones digit changed from 0 to X. But if the ones digit were 1-9, then the tens digit can't change unless it's itself 0 or X. In other words, the rightmost digit that we change must be a 0 or an X, so if there are no 0's or X's, no digit can change, and so the standard decimal expansion is the only one.

But let's look at again what we need to prove -- the expansion is unique if and only if there are no zeros in the original number. This is a biconditional (Section 2-5 of the U of Chicago text), and so there are actually two things to prove. We already proved that if there are no zeros, then expansion is unique, so now we must prove that if the expansion is unique, then there are no zeros. In other words, we need to prove the converse of the original theorem. Here's how Merryfield proves the converse:

For the converse, suppose that N has a decimal expansion that has at least one zero. Let d_j be the left-most such zero, which implies that and d_{j+1}\ne 0. Hence a two-digit portion of the expansion is d_{j+1}10^{j+1}+0. Note that this equals (d_{j+1}-1)10^{j+1}+10\cdot 10^j. So we let and e_{j+1}=d_{j+1}=d_j-1 to get a different over-expansion. (Note: if it happens that d_{j+1}=1 and that was the left-most digit, then we omit that digit from the new over-expansion, which now has one fewer digit.)

We notice that Merryfield gives an indirect proof of the converse here. He assumes that N does have a zero, and shows how to find another expansion, so that the expansion is not unique. Basically, he takes the leftmost zero, changes it to an X, and then drops the digit to its left by one. So 20 becomes 1X, 90 becomes 8X, and 100 becomes X0.

The Putnam is fond of deducting points for missing special cases. If one forgets to prove the converse, or forgets the special case where 10- becomes X- with one fewer digit, then the student will lose points. Each of the twelve questions is worth 10 points. In reality, the only scores one can earn on each question are 0, 1, 2, 8, 9, and 10. The most common score on any question is, of course, 0. In certain years, the most common score on the whole test is 0.

When I show this to my student tonight, I'll use Merryfield's new digit X and introduce the problem by saying that we are inventing a new digit, rather than use his squiggly E -- I meant sigma -- notation. Then I'll ask which numbers have two expansions and which ones have only one. Hopefully, after seeing this Putnam proof and how hard it is, he'll never complain about his proofs in geometry class again.

Returning to geometry, we have seen how powerful a proof by induction can be. We have proved the Center of a Regular Polygon Theorem. But now we wish to prove another related theorem -- one that is specifically mentioned in the Common Core Standards:

Given a rectangle, parallelogram, trapezoid, or regular polygon, describe the rotations and reflections that carry it onto itself.

What we wish to derive from the Center of a Regular Polygon Theorem is that we can rotate this polygon a certain number of degrees -- about that aformentioned center, of course -- or reflect it over any angle bisector or perpendicular bisector. But the U of Chicago text, unfortunately, doesn't give us a Regular Polygon Symmetry Theorem or anything like that.

I'm of two minds on this issue. One way would be to take this theorem and use it to prove that when rotating about O, the image of one of those isosceles triangles with vertex O and base one side of the polygon is another such triangle. The other way is to do Dr. Wu's trick -- he defines regular polygon so that it's vertices are already on the circle. Then we can perform rotations on the entire circle. (Rotations are easier to see, but it's preferable to do reflections because a rotation is the composite of two reflections.) Notice that the number of degrees of the rotation depends on the number of sides. In particular, for a regular n-gon we must rotate it 360/n degrees, or any multiple thereof.

No comments:

Post a Comment