Recall that Putnam questions are numbered A1 to A6 and then B1 to B6. Usually, the first question in each section is the easiest, so I'd normally want to post A1 here, if not B1. But unfortunately, both A1 and B1 this year require some Calculus, and I normally want to post only questions that a student in a Geometry class would understand.
Question B4 starts out promising for a Geometry class:
B4. Let T be the set of all triples (a, b, c) of all positive integers for which there exist triangles with side lengths a, b, and c...
This, of course, sounds just like the Triangle Inequality. Notice that these triples aren't Pythagorean triples where c needs to be the longest side -- either a, b, or c can be the longest. But let's look at the rest of the problem:
Express sum_(a,b,c in T) 2^a / (3^b * 5^c) as a rational number in lowest terms.
And of course T is an infinite set, so now we'd have to introduce infinite series, which is now too complex for Geometry students. So I can't do B4 today.
Of all the Putnam questions, A2 and B2 are the most accessible to high school Geometry students, since these only involve whole numbers. Both of them are similar in difficulty to the problem that I posted last year (2014 B1). Here is A2:
A2. Let a_0 = 1, a_1 = 2, and a_n = 4a_(n-1) - a_(n-2) for n > 2. Find an odd factor of a_2015.
We see that this is a sequence of whole numbers, and we are asked to find the 2015th term. The fact that this is the year 2015 is not a coincidence -- there's almost always a Putnam problem that mentions the year somehow. This year, there are three questions that mention 2015 -- A2, A3, and B2.
How can we attack this problem? Sequences sound like something that don't appear in Algebra II, but in some Common Core Algebra I texts there are actually some sequences! Some such texts use the notation a_n, while others use function notation f (n).
We see that each term a_n depends on two previous terms, a_(n-1) and a_(n-2). This immediately reminds us of the Fibonacci sequence, where each term is the sum of the previous two terms. It is defined as follows:
a_0 = 0, a_1 = 1,
a_n = a_(n-1) + a_(n-2)
The first few terms of the Fibonacci sequence are 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, and so on. But it is much too hard to find the 2015th term, because it's too big -- it has over 400 digits! And the terms of the Putnam sequence grow even faster -- the 2015th has over a thousand digits! Its first few terms are 1, 2, 7, 26, 97, 362, 1351, and so on.
But notice that the Putnam question doesn't ask for the 2015th term -- it asks for some odd factor of that 2015th term. The 2015th term may have over a thousand digits, but it could be that 3 divides that huge number, so that the correct answer would be three. But how could we ever find out, considering that most calculators don't even go up that high?
There is a little trick I knew of that works for Fibonacci numbers. If we start counting from zero and call the nth Fibonacci number F_n, then F_0 = 0, F_1 = 1, F_2 = 1, F_3 = 2, F_5 = 5, F_6 = 8, etc.
Now notice that F_3 = 2. Let's look at the sequence again and find the other numbers that are also divisible by two -- the even numbers. These are F_6 = 8, F_9 = 34, F_12 = 144, and so on. The indices follow an obvious pattern -- every third term is a multiple of two.
Now notice that F_4 = 3. Let's look at the sequence again and find the other numbers that are also divisible by three. These are F_8 = 21, F_12 = 144, F_16 = 987, and so on. The indices follow an obvious pattern -- every fourth term is a multiple of three.
Now notice that F_5 = 5. Take a guess where the other multiples of five are -- that's right, every fifth term is a multiple of five. And just as F_6 = 8, every sixth term is a multiple of eight. We can generalize this as follows:
For all whole numbers m and n, F_mn is a multiple of F_n (and of F_m, for that matter).
So if we want to find factors of F_2015, we find the factors of 2015 first. One obvious factor of 2015 is five -- the other prime factors are 13 and 31. So we already know that one of the factors of F_2015 must be F_5 = 5. Another factor is F_13 = 233, and yet another is F_31 = 1,346,269 (which isn't prime, as its factors are 557 and 2417).
Of course, that only works for the Fibonacci sequence, but what about the sequence a_n that actually appears on the Putnam? As it turns out, we can prove that a_mn sometimes has a_n as a factor -- it only works when m is odd. Fortunately, 2015 and thus all of its factors are odd, so it works. We know that a_2015 has a_5 = 362 as a factor. The question asked for an odd prime, and since half of 362 is the prime number 181, we have that 181 is a valid answer.
But how exactly do we prove that if m is odd, then a_n is a factor of a_mn? This part is somewhat difficult and requires something more sophisticated than high school math. Just like last year, today I will link to the website of Dr. Kent Merryfield, a mathematician from right here in Southern California who regularly posts Putnam problems:
https://www.artofproblemsolving.com/community/c7h1171023_putnam_2015_a2
Notice at the link that the proof begins by finding an explicit formula for a_n. Even in high school algebra, we have students distinguish between recursive and explicit formulas. As it turns out, the explicit formula is a_n = ((2 + sqrt(3))^n + (2 - sqrt(3))^n) / 2.
Although several posters in that thread gave different answers, notice how many of the proofs use the same techniques, such as induction. We used induction to solve question B1 last year (2014), and we found out that even the U of Chicago text uses induction to prove the Center of a Regular Polygon Theorem in Lesson 7-7, and Dr. Hung-Hsi Wu uses induction to prove his Fundamental Theorem of Similarity when the scale factor is a natural number n. Indeed, induction works well when dealing with natural numbers, including sequences of natural numbers. For many mathematicians, as soon as they see "prove for every natural number n that...," they immediately start thinking about induction.
So induction comes up over and over and over again in proofs. Here's something else that comes up frequently in proofs, and that's CPCTC -- the subject of today's lesson. Officially, we haven't actually covered Lesson 6-7 yet, but we've implied it since CPCTC has already appeared in proofs. Still, I think that it's important to review with the students what CPCTC actually is.
Lesson 6-7 of the U of Chicago text covers the Corresponding Parts in Congruent Figures Theorem, which the text abbreviates as CPCF. But a special case of this theorem is more widely known -- corresponding parts in congruent triangles are congruent, or CPCTC.
When I was young, a local PBS station aired a show called Homework Hotline. After school, middle and high school students would call in their homework questions in math and English, and some would be chosen to have their questions answered on the air by special teachers. Even when I was in elementary school, I often followed the geometry proofs that were called in, and more often than not, there were triangle congruence two-column proofs where the Reason for a step was often CPCTC. So this was where I saw the abbreviation CPCTC for the first time. (By the time I reached high school, a few calculus problems were called in to the show. Nowadays, with the advent of the Internet, the show has become obsolete.)
Here's a link to an old LA Times article about Homework Hotline:
http://articles.latimes.com/1992-02-09/news/tv-3184_1_homework-hotline
When I reached geometry, our text usually either wrote out "corresponding parts in congruent triangles are congruent," or abbreviated as "corr. parts of cong. tri. are cong.," probably with a symbol for congruent and possibly for triangle as well. But our teacher used the abbreviation CPCTC. Now most texts use the abbreviation CPCTC -- except the U of Chicago, that is. It's the only text where I see the abbreviation CPCF instead.
Dr. Franklin Mason, meanwhile, has changed his online text several times. In his latest version, Dr. M uses the abbreviation CPCTE, "corresponding parts of congruent triangles are equal."
Well, I'm going to use CPCTC in my worksheets, despite their being based on a text that uses the abbreviation CPCF instead, because CPCTC is so well known.
Once again, it all goes back to what is most easily understood by the students. Using CPCTC would confuse students if they often had to prove congruence of figures other than triangles. But as we all know, in practice the vast majority of figures to be proved congruent are triangles. In this case, using CPCF is far more confusing. Why should students had to learn the abbreviation CPCF -- especially if they have already seen CPCTC before (possibly by transferring from another class that uses a text with CPCTC, or possibly even in the eighth grade math course) -- for the sole purpose of proving the congruence of non-triangles, which they'd rarely do anyway?
So it's settled. On my worksheet, I only use CPCTC.
Notice that for many texts, CPCTC is a definition -- it's the meaning half of the old definition of congruent polygons (those having all segments and angles congruent). But for us, it's truly a theorem, as it follows from the fact that isometries preserve distance and angle measure.
Another issue that comes up is the definition of the word "corresponding." Notice that by using isometries, it's now plain what "corresponding" parts are. Corresponding parts are the preimage and image of some isometry. Unfortunately, we use the word "corresponding angles" to mean two different things in geometry. When two lines are cut by a transversal and, "corresponding angles" are congruent, the lines are parallel, but when two triangles are congruent, "corresponding angles" (and sides) are congruent as well. The phrase "corresponding angles" has two different meanings here! Of course, one could unify the two definitions by noting that the corresponding angles at a transversal are the preimage and image under some isometry. I tried this earlier, remember? It turns out that the necessary isometry is a translation. This is one of the reasons that I proved the Corresponding Angles Test using translations -- it now becomes obvious what "corresponding angles" really are. I mentioned yesterday, however, that in many ways using translations to prove Corresponding Angles is a bit awkward since it took so much work to avoid circularity. (This is why some authors, like Dr. Hung-Hsi Wu, uses rotations to prove Alternate Interior Angles instead.)
Since students have already seen CPCTC, I decided that I'd continue to inspire the students by replacing the second page with one based on the Putnam question I mentioned today. It's an easier version of the same question, where we start with the Fibonacci sequence and ask students to look for patterns, which they can then prove. For example, to prove that every third Fibonacci number is even, students can use even + odd = odd and odd + odd = even to help them.
Afterward I give the Putnam sequence. Notice that the answer to the question "For what values of n is a_n a multiple of three?" is none. Can you figure out why?
No comments:
Post a Comment