| Transcript
for the Math
Jam "USAMTS Round 4 Math Jam"
on Mar 14. |
| Math Jam hosted by DPatrick
(Dave Patrick ). |
DPatrick19:29:22
Hello and welcome to the fourth and final 2007-08 USA Math Talent Search Math Jam.
DPatrick19:29:30
Before we get started I would like to take a moment to explain our virtual classroom to those who have not previously participated in a Math Jam or one of our online classes.
DPatrick19:29:41
The classroom is moderated, meaning that students can type into the classroom, but only the moderators can choose a comment to drop into the classroom. This helps keep the class organized and on track.
DPatrick19:29:53
This also means that only well-written comments will be dropped into the classroom, so please take time writing responses that are complete and easy to read.
DPatrick19:30:30
Generally it will not be possible for me to respond to each comment or question individually. Please do not take it personally if I do not post or respond to your comments. I will try to answer as many questions as I can.
DPatrick19:30:38
There will be images in this lecture. The images should appear directly in the classroom window, as in the example below:
DPatrick19:30:43
DPatrick19:30:55
If you click on the link, the image should appear in a separate window. (You may have to hold down the Ctrl key while you click on an image link, and/or you may have to disable your popup blocker.)
DPatrick19:31:04
You can view the Round 4 problems as we discuss them by clicking on the following link:
DPatrick19:31:14
Let's get started with Problem 1:
DPatrick19:31:19
DPatrick19:31:30
DPatrick19:31:54
What should we do first?
karatemagic719:32:13
get the factors of 2008
karatemagic719:32:13
2^3*251=2008
CatalystOfNostalgia19:32:13
note that there are 8 factors of 2008, and only 4 can be adjacent to 251
redcomet4619:32:13
factors 1,2,4,8,251,502,1004,2008
DPatrick19:32:25
Sure: first, we should factor 2008, so we know what the factors are.
DPatrick19:32:30
The prime factorization of 2008 is 2^3 x 251.
DPatrick19:32:38
Therefore, 2008 has 8 factors, namely 1, 2, 4, 8, 251, 2 x 251 = 502, 2^2 x 251 = 1004, and 2^3 x 251 = 2008.
DPatrick19:32:54
Just so we have some easy terminology, let's say that two numbers are connectable if one divides the other.
DPatrick19:33:21
Which two factors are in some sense the least connectable?
not_trig19:33:34
the only things connectable to 251 are 1,502,1004,2008; the only things connectable with 8 are 1, 2, 4, 2008
fireninja019:33:34
8, 251
andersonw19:33:34
251 and 8
DPatrick19:33:48
Right, I would say that 251 and 8 are going to be the most trouble.
DPatrick19:34:08
So there are many places to start, but with this in mind, perhaps the easiest place to start is by placing the prime 251.
DPatrick19:34:35
It doesn't matter where we place it (since rotations and reflections don't matter), so let's put it on top:
DPatrick19:34:42
DPatrick19:34:56
I've labeled the other points a through g so we can talk about them.
DPatrick19:35:03
Where can we put the 8?
redcomet4619:35:20
then 8 goes into either c,d,e
fireninja019:35:20
d, c, e
karatemagic719:35:20
c,d,e
DPatrick19:35:37
Right. The 8 must go in either c, d, or e. c and e are essentially the same since we can do a reflection.
redcomet4619:35:41
case 1. 8 in d Case 2. 8 in c or e
DPatrick19:35:48
Exactly...we have two cases.
DPatrick19:35:53
Case 1: d = 8.
DPatrick19:36:00
DPatrick19:36:06
Now what?
fireninja019:36:21
they have two connectors in common: 1, 2008
karatemagic719:36:21
b and f are 2008 and 1
andersonw19:36:21
1 and 2008 have to be in b and f
DPatrick19:36:35
Right. The only numbers connectable to both 251 and 8 are 1 and 2008. So they have to be b and f.
DPatrick19:36:44
Again, since we can reflect, it doesn't matter which is which.
DPatrick19:36:53
So we arbitrarily set b=1 and f = 2008.
DPatrick19:36:59
jfko10119:37:15
Now put the last factors
DPatrick19:37:31
Right: we've got 2, 4, 502, and 1004 left.
karatemagic719:37:47
a can only be 502 or 1004
redcomet4619:37:47
then 2 and 4 in c and e
FloodFilter:19:37:47
2 has to go either c or e
redcomet4619:37:47
502, 1004 in a and g
DPatrick19:38:05
Right: we can either look at placing 502 and 1004 into a and g, or we can look at placing 2 and 4 in c or e.
karatemagic719:38:26
2 ways to do this
not_trig19:38:31
and either way works
DPatrick19:38:40
Yes. For instance, let's focus on a and g.
DPatrick19:38:50
Either a=502, g=1004 or a=1004, g=502.
DPatrick19:39:04
Whichever we choose, we then have only 1 way to place 2 and 4, since 4 and 502 are not connectable.
DPatrick19:39:11
DPatrick19:39:44
You can double-check that these are indeed different: note that on the left, 1 and 2 are connected, but on the right they're not.
DPatrick19:39:55
So these are the only two arrangements in our first case.
DPatrick19:40:17
Our other case is Case 2: c = 8.
DPatrick19:40:25
DPatrick19:40:36
Again, what's the next step?
Note: Unfortunately, at this point, something broke with our transcription software. There are no student comments after this point of the transcript. I apologize that this makes the transcript a little choppy, but I think that you can still follow the general discussion. -DP
DPatrick19:41:06
Right, once again we see that a and b have to be 1 and 2008, in either order.
DPatrick19:41:31
Note that a=1, b=2008 and a=2008, b=1 are NOT the same.
DPatrick19:41:52
What else? What about 4 and 502?
DPatrick19:42:44
Right. 4 and 502 must lie in d,e,f,g. But they're not connectable. The only non-connected pair among d,e,f,g is d and g.
DPatrick19:43:06
Right. 502 can't be d since 502 doesn't connect to 8. So g must be 502 and d must be 4.
DPatrick19:43:11
DPatrick19:43:20
(Remember that a,b are 1,2008 in either order)
DPatrick19:43:27
Now what about 2 and 1004?
DPatrick19:43:48
Can they be either way?
DPatrick19:44:24
2 doesn't connect to 251. So 2 can't be f, it must be e. Similarly 1004 must be f (it doesn't connect to 8).
DPatrick19:44:31
DPatrick19:44:46
So our only choice is which of a and b is 1 and which is 2008. Either choice works.
DPatrick19:44:56
DPatrick19:45:11
So Case 2 has two possible arrangements as well.
DPatrick19:45:28
Right, that gives us a grand total of 4 arrangements.
DPatrick19:45:49
On to Problem 2:
DPatrick19:45:53
DPatrick19:46:17
There are lots of ways to approach this, but what might be a good first step?
DPatrick19:46:46
A good first step might be to sum the left-side terms where we ignore the floor function.
DPatrick19:46:52
DPatrick19:47:25
This might suggest writing n = 858k + r where k is a nonnegative integer and 0 <= r < 858 is the remainder when n is divided by 858.
DPatrick19:47:31
(As I said, there are other possible methods too.)
DPatrick19:48:00
Our inequality then becomes
DPatrick19:48:06
DPatrick19:48:32
And when we move all the k terms to one side and all the r terms to the other, we get:
DPatrick19:48:37
DPatrick19:48:52
How do we analyze the right side?
DPatrick19:50:06
That's a good idea. What I did is broke up r into terms that look like the various greatest integer terms.
DPatrick19:50:11
DPatrick19:50:32
So we can "combine like terms":
DPatrick19:50:37
DPatrick19:50:49
What do we know about all those terms in parentheses?
DPatrick19:51:13
True, they're all less than 1. But can we get a better bound on them?
DPatrick19:51:28
Remember...r is an integer!
DPatrick19:51:41
What does that tell us about r/2 - [r/2]?
DPatrick19:52:01
Exactly. It's either 0 or 1/2.
DPatrick19:52:26
That essentially what we're doing. x - [x] is the fractional part of x, often denoted {x}.
DPatrick19:52:41
So all I really need is that the first term r/2 - [r/2] is at most 1/2.
DPatrick19:53:03
Right, or since we're probably only going to need the bounds,
DPatrick19:53:07
The first term is at most 1/2.
The second term is at most 2/3.
The third term is at most 10/11.
The fourth term is at most 12/13.
DPatrick19:53:29
Exactly, let me put up the equation again:
DPatrick19:53:34
DPatrick19:53:42
The sum of the first four terms is at most 1/2 + 2/3 + 10/11 + 12/13 = 2573/858, which is a little less than 3.
DPatrick19:54:11
But what else do we know about the entire right side?
DPatrick19:54:34
Right...remember the entire right side is an integer!
DPatrick19:54:46
(It was r minus a bunch of floors)
DPatrick19:55:00
Exactly, the most that the right side can be is 2.
DPatrick19:55:21
Yep...that tells us that k < 2, so the greatest k can be is 1.
DPatrick19:55:36
We can also check that when r = 857, the right side is 2.
DPatrick19:55:41
This means that our upper bound is when k = 1 and r =857.
DPatrick19:56:12
Right: therefore the answer is 858 + 857 = 1715.
DPatrick19:56:19
As a final check, we can compute all the terms in the original expression for n=1715:
857+571+155+131 = 1714 < 1715.
DPatrick19:56:43
(Recall than n = 858k + r, and we found k=1, r=857 is the highest we can get.)
DPatrick19:57:31
As I said, there are other methods to use, but I like this proof since it's not in the least bit "hand-wavy"/: every step is clear and it's clear at the end that you've got the upper bound.
DPatrick19:57:43
Let's move on to Problem 3:
DPatrick19:57:48
DPatrick19:57:57
(So that it's easier to type, you can type "u" for the greek letter mu in the problem.)
DPatrick19:58:07
How can we approach this?
DPatrick19:59:10
Right, every term in the sum is going to have a u(1-u) term since a_2k = ua_k and a_2k+1 = (1-u)a_k.
DPatrick19:59:34
DPatrick20:00:02
How do we express all the a_k's?
DPatrick20:00:51
There are a couple of ways to think about it.
DPatrick20:01:14
Very informally speaking, what does each term a_k look like?
DPatrick20:01:44
Right. It's a product of a bunch of u's and a bunch of (1-u)'s.
DPatrick20:02:15
DPatrick20:02:27
(oops...I meant a_k^2 there...)
DPatrick20:02:51
Aha...that's a key insight! How many of each pair (a,b) show up in the entire sum?
DPatrick20:03:02
In other words, how many terms have u^a and (1-u)^b?
DPatrick20:03:58
Exactly. To get a term with a u's and b 1-u's, we have to start at a_1, and apply the "even" rule a times to multiply by u, and apply the "odd" rule b times to multiply by 1-u.
DPatrick20:04:10
There are C(a+b,a) orders in which we can do this.
DPatrick20:04:19
So the sum is equal to:
DPatrick20:04:27
DPatrick20:05:06
Yeah, this looks like a job for the Binomial Theorem.
DPatrick20:05:27
If we let n = a+b, then all the terms of this sum where a+b = n is just the Binomial Theorem for (u^2 + (1-u)^2)^n.
DPatrick20:05:37
So our sum is:
DPatrick20:05:45
DPatrick20:06:17
And now the sum is just a geometric series!
DPatrick20:06:26
DPatrick20:06:56
Right, now it's just algebra to simplify.
DPatrick20:07:31
The denominator is just 1 - (2u^2 - 2u + 1) = -2u^2 + 2u = 2(u - u^2) = 2u(u-1).
DPatrick20:07:51
Yes, all the u terms cancel, and we're just left with 1/2 as the answer.
DPatrick20:08:16
There's another somewhat different solution that I'd like to also show you.
DPatrick20:08:26
Let S be the sum we want.
DPatrick20:08:37
DPatrick20:08:58
Let's look at all of the terms that are "children" of a_2 (that is, a_4, a_5, a_8 through a_11, a_16 through a_23, etc.). What do they contribute to S?
DPatrick20:09:39
These children give us a mini-copy of S, except all the terms are multiplied by u^2.
DPatrick20:09:53
DPatrick20:10:05
And the rest? What about the terms that are "children" of a_3 (that is, a_6, a_7, a_12 through a_15, a_24 through a_31, etc.)?
DPatrick20:10:46
DPatrick20:10:55
DPatrick20:11:15
DPatrick20:11:36
Let me go back to the original definition for the a's:
DPatrick20:11:42
DPatrick20:12:11
So, for example, a_4 = ua_2. I think of a_4's "parent" as a_2 and I think of a_4 as being a_2's "child".
DPatrick20:12:26
Similarly a_5 = (1-u)a_2, so a_5 is a child of a_2.
DPatrick20:12:31
etc
DPatrick20:12:51
All the terms that are "descendants" of a_2 sum to u^2S. All the terms that are "descendants" of a_3 sum to (1-u)^2S.
DPatrick20:13:22
There's actually a third solution, which is really nice, that use geometry of all things! Now that I've teased you, think about it some more and maybe post on the message board.
DPatrick20:13:37
But I think the first solution that we did is the most straightforward.
DPatrick20:13:43
Let's move on to Problem 4:
DPatrick20:13:47
DPatrick20:14:20
I agree, our general strategy is a proof by contradiction: assume that all three inequalities hold, and end up with something impossible.
DPatrick20:14:32
To clarify things, let's write them all as inequalities on one side:
DPatrick20:14:36
DPatrick20:14:58
It might even be helpful to expand them all out:
DPatrick20:15:07
DPatrick20:15:29
These look a little like Vieta's Formulas for a polynomial with roots w,x,y,z! Except the signs are all funny.
DPatrick20:15:40
Indeed, that's the same thing.
DPatrick20:15:59
Yes: in fact, the right sides are the Vieta's Formulas for a polynomial with roots w, x, -y, and -z.
DPatrick20:16:04
Or to say it another way:
DPatrick20:16:13
DPatrick20:16:27
When we multiply f(t) out, we get:
DPatrick20:16:32
DPatrick20:16:49
Under our assumptions, what do we know about f(t)?
DPatrick20:17:25
Right: all of its coefficients are positive. (wxyz>0 too since w,x,y,z are all positive.)
DPatrick20:18:00
But polynomials with all positive coefficients can have no positive roots: if we plug in a positive number for t, we have to get a positive output for f(t).
DPatrick20:18:31
How do we wrap it up and get our contradiction?
DPatrick20:19:28
Right: w and x are roots, and they're positive.
DPatrick20:19:39
But we just said that f(t) has no positive roots.
DPatrick20:19:44
That's our contradiction.
DPatrick20:19:50
So the inequalities cannot all be simultaneously satisfied.
DPatrick20:20:06
Let's finish up with Problem 5.
DPatrick20:20:12
DPatrick20:20:26
DPatrick20:20:49
(I'm making the pictures huge so that we can see sufficient detail. You might need to widen your window.)
DPatrick20:21:18
There are lots of ugly solutions with trig, or with complex numbers, or with coordinates, or with a number of similarly nasty things.
DPatrick20:21:29
I'm not going to use any of those. :)
DPatrick20:21:53
There are two clues in the problem as to how to proceed. First, the 13-gon is a figure that has a lot of symmetry. Symmetry is a very powerful tool, and we should exploit it as much as possible.
DPatrick20:22:03
Second, we want to express a length in terms of other lengths. This suggests trying to construct auxiliary lines in the diagram that will help relate these lengths.
DPatrick20:22:17
Let's start by drawing what we want to find:
DPatrick20:22:25
DPatrick20:22:40
Now you see why the diagram has to be big, so that we can tell A and B apart!
DPatrick20:23:03
For the record, A is the intersection of diagonals P_4 P_11 and P_5 P_12, and B is the intersection of diagonals P_4 P_11 and P_3 P_10.
DPatrick20:24:02
Well, there aren't too many parallel lines yet, but that will be the general idea...parallelograms are the key.
DPatrick20:24:16
Let's start by noting that AB is a portion of diagonal P_4 P_11. How does that help?
DPatrick20:24:41
Remember, the goal is to express AB in terms of the various diagonals. So P_4 P_11 is the obvious place to start.
DPatrick20:25:05
Excellent.
DPatrick20:25:17
By symmetry, AP_11 has the same length as BP_4. (Remember that symmetry is our friend here!)
DPatrick20:25:25
DPatrick20:25:44
Aha, good start. We've got a d_6 term in there.
DPatrick20:26:00
Now we want AP_11 in terms of some other diagonals.
DPatrick20:26:11
What can we do now?
DPatrick20:26:55
Somebody mentioned parallel lines and parallelograms before...how can we make a parallelogram with one side AP_11?
DPatrick20:27:38
Aha! And what other diagonal is AP_11 on, and what's parallel to it?
DPatrick20:28:06
(After we answer this question I'll update the diagram...but the diag is so huge we lose our discussion if I do it now!)
DPatrick20:28:33
oops..I didn't mean AP_11, I just meant A. What other diagonal is A on?
DPatrick20:28:51
Aha...that's it.
DPatrick20:29:01
Now let me update the picture and watch the magic happen:
DPatrick20:29:09
DPatrick20:29:23
A P _11 C P_5 is a parallelogram!
DPatrick20:29:45
We want to compute A P_11.
DPatrick20:29:54
We now know that it's equal to C P_5.
DPatrick20:30:10
What's C P_5 in terms of a diagonal that know?
DPatrick20:30:41
Right, it's part of P_5 P_10, so it's part of d5.
DPatrick20:30:47
Exactly:
DPatrick20:30:54
Since CP_5 is a portion of diagonal P_5 P_10, we can say CP_5 = P_5 P_10 - CP_10 = d_5 - CP_10. Thus, we have reduced the problem to expressing CP_10 in terms of the diagonals.
DPatrick20:31:22
DPatrick20:31:43
Right: we just do the exact same thing again!
DPatrick20:31:53
DPatrick20:32:16
C P_10 D P_6 is another parallelogram!
DPatrick20:32:34
So C P_10 is the same as D P_6.
DPatrick20:32:42
And what's D P_6?
DPatrick20:33:29
Right.
DPatrick20:33:34
So we can update our computation:
DPatrick20:33:50
DPatrick20:34:15
Right! So we know what DP_9 is.
DPatrick20:34:20
It's just d1.
DPatrick20:34:55
DPatrick20:35:10
No trig, no coordinates, nothing icky. Just parallelograms!
DPatrick20:35:38
I wish I could take credit for it, but I can't.
DPatrick20:35:43
This is my colleague Naoki Sato's solution.
DPatrick20:35:50
It's really pretty.
DPatrick20:36:02
That's it for Round 4, and thus, for 2007-08.
DPatrick20:36:05
Thanks for participating!
