| Transcript
for the Math
Jam "2009 Alternate AIME Math Jam"
on Apr 3. |
| Math Jam hosted by rrusczyk
(Richard Rusczyk ). |
rrusczyk18:59:49
Hello and welcome to the 2009 AIME II Math Jam!
rrusczyk18:59:56
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
rrusczyk19:00:04
The classroom is moderated, meaning that students can type into the classroom, but only the moderator can choose a comment to drop into the classroom. This helps keep the class organized and on track. 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.
rrusczyk19:00:17
There are a lot of students here! As I said, only well-written comments will be passed to the entire group. Please do not take it personally if your comments do not get posted, and please do not complain about it. I expect this Math Jam to be much larger than our typical class, so please be patient with me---there are quite a few of you here tonight!
rrusczyk19:00:32
Also, we won't be going through the math quite as thoroughly as we do in our classes -- I can't teach all the prerequisite material for every problem as we go (and certainly not to 200+ students -- this Math Jam won't be as orderly or as thorough as our typical online classes.)! If you do not know a particular concept necessary for a problem, I probably will not be able to explain it to you tonight.
rrusczyk19:01:08
(I don't think we'll get 200+ students tonight like we had for the first AMC Math Jam. Phew.)
rrusczyk19:01:18
Please also remember that the purpose of this Math Jam is to work through the solutions to the AIME problems, and not to merely present the answers. "Working through the solutions" includes discussing problem-solving tactics. So please, when a problem is posted, do not simply respond with the answer. That's not why we're here. We're going to work through the problems step-by-step, and people who post comments that skip key steps or jump ahead in the problem, without providing explanation or motivation, are going to be ignored.
rrusczyk19:01:59
I don't claim that the solutions that we'll present today are the "definitive" or "best" solutions to each problem. Many of the problems have more than one plausible approach. We don't have time to consider every possible approach to every problem, but you can discuss other approaches on the Forum or post them in the AoPSWiki.
rrusczyk19:02:12
Our agenda is to work through all 15 problems on the 2009 AIME II, in order.
rrusczyk19:02:30
Let's get to the problems!
rrusczyk19:02:32
rrusczyk19:03:07
Here are a couple ways to tackle the problem:
Recursive Acronym19:03:12
Since you need the white, red, and blue paint levels to be equal *before* painting the white, red, and blue stripes, you need to use up enough paint in the pink stripe to bring all three levels to 130.
GoldenFrog161819:03:12
let x be the amount of paint for each stripe
Hullohihell019:03:12
set up an equation
rrusczyk19:03:33
We could set up an equation and do some algebra. Or, we can reason our way to the answer pretty quickly.
rrusczyk19:03:43
Let's look at Recursive's solution first:
Recursive Acronym19:03:45
So you use 34 ounces of red and 58 ounces of white on the pink.
rrusczyk19:04:13
We use 164 - 130 = 34 more ounces of red and 188 - 130 = 58 more ounces of white paint in making the stripes, since in the end we must have the same amount of all three colors.
Recursive Acronym19:04:22
Which means 92 ounces a stripe.
GoldenFrog161819:04:22
92 ounces per stripe
rrusczyk19:04:34
So there's a total of 34 + 58 = 92 ounces in the pink stripe
tinytim19:04:38
Thus, you use 92 ounces of blue because the stripes are the same size
Recursive Acronym19:05:00
So then you use 92 on the pink stripe, and are left with 130 of each, which means that after using 92 on Red, White, and Blue, you have 38 left on each stripe.
rrusczyk19:05:03
Therefore, there are 92 ounces of paint in the blue stripe, leaving 130 - 92 = 38 ounces of blue paint.
GoldenFrog161819:05:22
130*3-92*3=114
mathspee19:05:22
so there are 114 ounces left
geoffreywong19:05:22
so subtract 130-92 and multiply by three
Recursive Acronym19:05:22
38 ounces left of each color times 3 colors equals 114 ounces left.
tinytim19:05:22
Which gives an answer of 38*3=114 ounces
rrusczyk19:05:29
This means we have 3(38) = 114 ounces of paint left over.
rrusczyk19:05:37
We also could have tackled this with algebra.
rrusczyk19:05:58
We let the amount of paint in each stripe be t.
rrusczyk19:06:12
Then what?
GoldenFrog161819:06:52
(188-t)+(164-t)-t=2(130-t)
tinytim19:07:04
2(180-t)=(164-t)+(188-t)-t
rrusczyk19:07:08
Where does this come from?
tinytim19:07:18
130 I mean
tinytim19:07:38
We know that the same amount of each paint are left
rrusczyk19:07:42
Then, we have used t ounces of blue, so there is 130-t blue left.
chessmaster719:07:45
the stripes are all the same size, so two stripes should equal two stripes
rrusczyk19:07:49
We must also have 130-t red and 130-t white, for a total of 260-2t.
GoldenFrog161819:07:51
t ounces is removed from each stripe and another t ounces is removed from the red and white
MathWhiz200919:08:04
2(130-t)=188+164-t-t-t
rrusczyk19:08:06
We started with 164 + 188 = 352 ounces of red and white combined, and used 3t total on the red, white, and pink stripes, so we have 352 - 3t left.
rrusczyk19:08:10
Therefore, we must have 352 - 3t = 260 - 2t.
GoldenFrog161819:08:28
t=92
tinytim19:08:28
so t=92 as we earlier found
mathq19:08:37
t=352-260=92
saszs19:08:40
t=92
chessmaster719:08:49
this provides t=92, and 130*3-92*3=114
MathWhiz200919:08:49
then solve the equation to find t, then subtract 4t from 130+164+188
GoldenFrog161819:08:49
188+130+164-92*4=114
rrusczyk19:08:50
From here, we find t=92, just like before, and we have a total of 3(130-t) = 114 ounces left.
rrusczyk19:09:01
On to #2!
rrusczyk19:09:02
rrusczyk19:09:11
There sure doesn't look like any easy way to combine the three numbers we have to add, so let's see if we can compute one individually.
rrusczyk19:09:18
Recursive Acronym19:10:02
Rewrite x^(y^2) as (x^y)^y
dgreenb80119:10:02
a^{x^2}=(a^x)^x
GoldenFrog161819:10:02
Hyperboloid19:10:02
rrusczyk19:10:17
rrusczyk19:10:19
Then what?
spelljack82519:10:47
substitute
mathq19:10:48
then it becomes 27^log7(base 3)
chessmaster719:10:48
then substitute in 27 for 27^(log_3(7))
rrusczyk19:10:53
rrusczyk19:11:06
All we did here was substitute the given information.
rrusczyk19:11:12
Can we simplify this further?
GoldenFrog161819:11:34
27^(log_3 7)=7^3=343
spelljack82519:11:34
27 = 3^3
m1sterzer019:11:34
27=3^3
tinytim19:11:34
3 to "something" equals 7. Thus, 27 to that "something equals 7^3=343.
maxschindler19:11:34
3^3log_3{7}
rrusczyk19:11:52
rrusczyk19:12:01
tinytim19:12:18
11^2
Hyperboloid19:12:18
121
GoldenFrog161819:12:18
121
rrusczyk19:12:21
rrusczyk19:12:39
This is basically the same thing we did for the first one.
rrusczyk19:12:43
sj020119:12:54
then 5
tinytim19:12:54
25^(1/2)=5
kohjhsd19:12:54
25^.5
nechesskid1319:12:54
5
GoldenFrog161819:12:54
e71421283519:12:54
25^1/2, or 5
Hyperboloid19:13:00
rrusczyk19:13:01
rrusczyk19:13:10
So what's our answer?
tinytim19:13:24
Adding these gives an answer of 469.
geoffreywong19:13:24
469
sj020119:13:24
343+121+5 = 469
GoldenFrog161819:13:24
469
Hyperboloid19:13:24
So the answer is 469.
sherlock19:13:24
469
rrusczyk19:13:29
Adding our results gives 343 + 121 + 5 = 469.
rrusczyk19:13:38
Two down. 13 to go.
rrusczyk19:13:43
mathq19:13:55
make a diagram
sj020119:13:57
diagram!!
Recursive Acronym19:13:59
Draw a picture!
rrusczyk19:14:04
rrusczyk19:14:17
What are we likely to use to solve this problem?
dgreenb80119:14:24
similar triangles
tinytim19:14:24
Bunch of similar tirangles
Recursive Acronym19:14:24
So many similar right triangles...
rrusczyk19:14:30
We have lots of right triangles, and we have similar triangles all over the place.
rrusczyk19:14:47
We let AE = x so we can start building equations. (Notice that this is easier than letting AD = x, since we avoid fractions.)
rrusczyk19:14:55
What next?
all4math19:15:26
we use ratios
rrusczyk19:15:29
Which ones?
dgreenb80119:15:59
ABE and CBA are similar
dgreenb80119:15:59
AE/AB=AB/AC
MathWhiz200919:15:59
ABE~ABC
m1sterzer019:15:59
AB/AE=BC/AC
motoe12319:15:59
AE:AB=AB:BC
rrusczyk19:16:11
Here's a reason we focus on these:
Hyperboloid19:16:13
One involving AB, since we know its length.
MathWhiz200919:16:22
actually ABE~BCA
rrusczyk19:16:29
Since AE = x, we have BC = 2x.
rrusczyk19:16:42
So what equation do we get?
MathWhiz200919:16:58
x/100=100/(2x)
GoldenFrog161819:16:58
2x^2=BA^2
sj020119:16:58
2x/100 = 100/x
mathq19:16:58
x:100=100:2x
chessmaster719:16:58
2x/100=100/x
rrusczyk19:17:01
From ABC ~ EAB, we have AE/AB = AB/BC, so x/100 = 100/(2x).
rrusczyk19:17:27
So?
tinytim19:17:53
x=50sqrt{2}
mismatchtea19:17:54
2x^2 = 10000
sj020119:17:54
x^2 = 5000
GoldenFrog161819:17:54
x=50*sqrt(2)
sa31419:17:54
x^2 = 5000
dgreenb80119:17:54
x=100/sqrt{2}=50sqrt{2}
mathspee19:17:54
10000=2x^2
rrusczyk19:17:57
rrusczyk19:18:03
Keep going . . .
rrusczyk19:18:09
What is AD?
Recursive Acronym19:18:24
Double.
tinytim19:18:24
so 2x is 100sqrt{2}
e^i_penguin19:18:24
100sqrt2
mathspee19:18:24
2x=100 root2
GoldenFrog161819:18:24
AD=100*sqrt(2)
rrusczyk19:18:26
rrusczyk19:18:29
And what is our answer?
Yongyi78119:18:43
2x = 100sqrt(2) = 141
sj020119:18:43
141
GoldenFrog161819:18:43
141
chundai19:18:43
141.
mathspee19:18:43
141
tinytim19:18:43
Hullohihell019:18:43
141
rrusczyk19:18:46
rrusczyk19:18:56
Three down.
rrusczyk19:18:59
rrusczyk19:19:34
Note: If you are here for the Intro Geometry class, please leave and then refresh the Classroom page. This is the AIME Math Jam.
rrusczyk19:19:40
We could just set this up like a typical arithmetic series problem. We have
n + (n-2) + (n-4) + . . . + (n-2(m-1)) = 2009,
where there are m children in the contest.
rrusczyk19:19:44
Ick.
rrusczyk19:19:50
Anyone have a nicer way to approach this?
rrusczyk19:20:29
What is typically an easier way to think about the sum of an arithmetic series?
Recursive Acronym19:21:01
First term plus last term divided by two times number of terms.
chundai19:21:01
the average of the first and last terms multiplied by the number of terms?
rrusczyk19:21:39
A nicer way of thinking about the sum of an arithmetic series is the average of the terms times the number of terms. Letting m be the number of students and t be the average, we now have simply mt = 2009.
rrusczyk19:21:46
It appears that m and t must divide 2009, but first we must make sure both are integers. Are they?
rrusczyk19:22:38
We have to make sure the *average*, t, is an integer.
Hyperboloid19:23:04
Yes
GoldenFrog161819:23:04
n and k must have the same parity
nechesskid1319:23:04
The numbers all have the same parity, so the average is an integer.
rrusczyk19:23:07
Yes -- the average of the terms equals the average of the first and last terms. These two terms have the same parity (both odd or both even), so their average is an integer.
mismatchtea19:23:12
the prime factors of 2009 are 41 and 7 and 7
Hyperboloid19:23:12
rrusczyk19:23:18
rrusczyk19:23:22
We don't have many options for (m,t) to check. Do we have to try every factor of 2009 for m?
rrusczyk19:24:06
Are there any we know we'll be able to exclude?
mismatchtea19:24:09
only 3*2/2 possibilities
rrusczyk19:24:20
Why do we only have to test half the possibilities for m?
rrusczyk19:24:46
m and t are not the same -- they mean different things.
BenM19:25:41
t must be greater than m
Hyperboloid19:25:41
m<t
m1sterzer019:25:41
we can't have anyone having to eat 'negative grapes' to make the average too low
tinytim19:25:41
The average must be greater than the number of people.
rrusczyk19:25:47
Students can't eat a negative number of grapes, so we only need to check those cases for which the last-place student eats a positive number of grapes.
tinytim19:26:09
Thus, we only need to try 1,7,and 41 for m.
rrusczyk19:26:14
Those cases are (m,t) = (1,2009); (7, 287); (41,49). If (m,t) = (49, 41), then we have 49 kids eating an average of 41 grapes, so the last place kid eats 41 - 2(24) = -7 grapes. Ooops! Similarly, if we have even more kids and a lower average of grapes, we'll have a kid eating a negative number of grapes, which would not be pretty.
rrusczyk19:26:34
What do we get for n in each of these cases?
tinytim19:27:31
rrusczyk19:27:36
So, all that's left is to find the smallest n. If (m,t) = (1,2009), we have n = 2009.
rrusczyk19:27:43
If (m,t) = (7,287), then 7 kids average 287 grapes, so n = 287 + 3*2 = 293.
rrusczyk19:27:48
If (m,t) = (41,49), then 41 kids average 49 grapes, and n = 49 + 2*20 = 89.
rrusczyk19:27:50
So. . . .
sucker092319:28:03
smallest
Hullohihell019:28:03
89 is the answer
sucker092319:28:03
=89
lukezli19:28:03
89 is the answer.
rrusczyk19:28:14
The smallest of these is obviously 89, so that's our answer.
rrusczyk19:28:38
Four down in a half hour. Still on track to get that perfect 15!
rrusczyk19:28:43
rrusczyk19:28:57
rrusczyk19:29:12
Where do we start?
Hullohihell019:29:24
where's the triangle?
rrusczyk19:29:42
The triangle is formed by connecting the outer points of tangency.
dgreenb80119:30:07
Canter of big circle, center of smaller circle, point of tangency collinear
Recursive Acronym19:30:07
Draw a lot of lines.
rrusczyk19:30:16
Let's play connect the dots.
m1sterzer019:30:18
usually i start by drawing a lot of lines
rrusczyk19:30:30
What lines are the first ones to start with here?
tinytim19:30:56
AED(or AEC) is a good triangle to try and use.
chessmaster719:30:57
AC, CD, AD, BA, BC, and BD
GoldenFrog161819:30:57
CE, DE, BE
tinytim19:31:17
Connect centers of circles
rrusczyk19:31:21
rrusczyk19:31:29
We definitely want to start by connecting up the centers.
rrusczyk19:31:39
What's going to be our general strategy here?
chessmaster719:32:25
now we can write in lengths using the given radiuses, and maybe try pythagoras or trig
tinytim19:32:25
Find expressions for lengths in terms of r, the radius of E.
rrusczyk19:32:41
Our goal is to build an equation for r, the radius of E.
rrusczyk19:33:04
So, let's find some lengths.
rrusczyk19:33:10
What lengths can we find?
geoffreywong19:33:43
AC
mismatchtea19:33:43
AC
rrusczyk19:33:46
What is AC?
tinytim19:34:17
10-2=8
geoffreywong19:34:17
8
mismatchtea19:34:17
10-2=8
chessmaster719:34:17
8
daydreamer111619:34:22
10-2?
rrusczyk19:34:48
We have AC = 10-2 = 8, since the radius of C is 2, and if we continue AC, it will hit the point of tangency of C and A.
daydreamer111619:34:54
and AC=AD
rrusczyk19:34:58
True.
rrusczyk19:35:20
So, we have AC = 8. What other sides can we find (either find the length, or find them in terms of r).
mismatchtea19:35:26
AB = 10-3=7
daydreamer111619:35:26
and doesn't AB=10-3=7?
rrusczyk19:35:37
Exactly. For the same reason, we have AB = 10 - 3 = 7.
GoldenFrog161819:35:41
E is on line BA
rrusczyk19:35:51
True -- by symmetry, E is on AB.
MathWhiz200919:35:54
but how does this help us
rrusczyk19:35:59
How does this help?
chessmaster719:36:10
EC = r+2
rrusczyk19:36:21
EC = r + 2, since it is the sum of the radii of E and C.
rrusczyk19:36:37
(Please use capital letters for points - I don't read the ones that have lowercase letters for points.)
rrusczyk19:36:49
Are there any other lengths we can find?
tinytim19:37:04
m1sterzer019:37:04
EA = EB-AB = (r+3)-7=r-4
GoldenFrog161819:37:04
AE=r-4
rrusczyk19:37:41
We have AE = r-4, since the distance from A to the point of tangency of A and B is 7-3 = 4.
rrusczyk19:37:45
Now what?
tinytim19:38:16
Now we can use Law of Cosines
GoldenFrog161819:38:17
EAD=60 degrees
dgreenb80119:38:17
EAD=60?
tinytim19:38:20
We have enough information to use Law of Cosines.
m1sterzer019:38:20
we know angle EAD is 60 degrees
rrusczyk19:38:22
We have three sides of ACE: AC = 8, AE = r-4, CE = 2+r. . .
rrusczyk19:38:27
If we're stuck here, we ask ourselves what we haven't used yet. We haven't used the information about the equilateral triangle. The outer points of tangency on circle A are vertices of an equilateral triangle. The rays from A through B, C, and D will pass through these three points, so <BAC = <CAD = <DAB = 120. By symmetry, AE bisects <CAD, so <CAE = 60. Now, we're set.
rrusczyk19:38:38
In triangle ACE, we have AC = 8, CE = 2 + r, AE = r - 4, and <CAE = 60.
rrusczyk19:39:22
Now we break out the law of cosines.
chessmaster719:39:33
(r+2)^2=8^2+(r-4)^2-2(8)(r-4)*1/2
tinytim19:39:33
rrusczyk19:39:38
rrusczyk19:39:46
And what do we find?
chessmaster719:40:38
we get 20r=108
m1sterzer019:40:38
r=108/20=27/5
charles.du19:40:38
27/5 so answer is 32
rrusczyk19:40:43
tinytim19:41:14
or we could have Pythagoras bashed...
rrusczyk19:41:25
You can indeed build some right triangles and bash away.
charles.du19:41:30
yeah, extend BA to meet CD
rrusczyk19:41:39
Like that. You can work out that solution on your own.
rrusczyk19:41:45
For now, we're on to #6!!
HiDN42819:41:55
we would get 32 using the pythag as well
rrusczyk19:41:59
I sure hope so :)
rrusczyk19:42:00
rrusczyk19:42:10
"At least" in a counting problem. What should that make us think?
jeffreyyan819:42:21
well right off the bat, i used PIE-principle of inclusion exclusion
rrusczyk19:42:32
That's one thing I sometimes think, but usually I think this first:
BenM19:42:42
find the opposite
spelljack82519:42:42
complement counting
chundai19:42:42
complimentary counting!
tinytim19:42:42
Count the total number of 5-element subsets and then use complementary counting.
GoldenFrog161819:42:42
complimentary counting
maxschindler19:42:42
complementary counting
rrusczyk19:42:49
Any time we see "at least" in a counting problem, we should consider counting what we don't want instead of directly counting what we want. (We at AoPS sometimes call this "complementary counting".)
rrusczyk19:43:04
Complimentary counting is nice, but it's complementary counting that we want to do here.
GoldenFrog161819:43:17
without restriction there are C(14,5)
tinytim19:43:17
The total number of sets is easy. Simply 14C5=2002.
rrusczyk19:43:23
rrusczyk19:43:39
Next, we have to count the number of five-element subsets that don't satisfy the problem. In words, what are these?
tinytim19:44:11
Now we think of how to "construct" a set such no two members are consecutive.
e71421283519:44:11
no two numbers are consecutive
GoldenFrog161819:44:11
no two numbers are consecutive
Hullohihell019:44:11
ones where no two numbers are consecutive
happysunnyshine19:44:11
no consecutive numbers
rrusczyk19:44:15
These are the five-element subsets such that no two numbers are consecutive.
rrusczyk19:44:21
How many of these are there?
Hyperboloid19:45:05
10C5 = 252
BenM19:45:05
10 chose 5
lameneses19:45:05
rrusczyk19:45:15
qwang19:45:32
If we don't want any 5 numbers to be consecutive, consider 5 placemarkers that we place numbers around. for every arrangement of numbers around the placeholders, there's one set.
dgreenb80119:45:32
We draw a bijection: for each possibility, we can take out a number in between each of the selected numbers
BenM19:45:32
because you insert 4 spaces between the numbers and 14-4=10
rrusczyk19:45:44
I'm going to do a quick counting lesson to go through what these answers mean.
rrusczyk19:45:49
There are a number of ways to see this.
rrusczyk19:45:59
We can view the first n integers as n chairs in a row. So, we have 14 chairs in a row, and we must pick 5 chairs such that no two chosen chairs are adjacent. Here's an example:
rrusczyk19:46:03
OXXOXXXOXOXXOX
rrusczyk19:46:07
The O's are the chosen chairs.
tinytim19:46:11
Since no two are consective we can "take out" one number between each of the 5 numbers.
rrusczyk19:46:15
If we take away one un-chosen chair between each successive pair of O's, we have
rrusczyk19:46:19
OXOXXOOXOX
rrusczyk19:46:33
We have 10 chairs now, and 5 of them are chosen. What happens when we reverse this process, and jam an extra X between each successive pair of O's?
spelljack82519:47:12
you get the original
tinytim19:47:13
We get a set that has no two consecutive O's
rrusczyk19:47:15
We get back the original arrangement of 14 chairs:
rrusczyk19:47:20
OXXOXXXOXOXXOX
rrusczyk19:47:25
How does this help us count the number of ways we can choose 5 of the 14 chairs such that no two are adjacent?
tinytim19:47:49
So this corresponds o arranging 5 x's and 5 o's which is 10C5.
spelljack82519:47:49
the number of combinations is equivalent
rrusczyk19:48:02
For any such arrangement, we can take out 4 X's, one from between each successive pair of O's (which we can always do because no two chairs are adjacent!). We then get a row of 5 X's and 5 O's. We can reverse the process. For any row of 5 X's and 5 O's, we can add an X between each successive pair of O's and produce a row with 9 X's and 5 O's such that no two O's are adjacent (since we added an X between each successive pair).
rrusczyk19:48:16
Since each 14-letter string of 9 X's and 5 O's and no O's adjacent can be turned into a single 10-letter string of 5 X's and 5 O's, and vice-versa, we say that we have a 1-to-1 correspondence between the two sets of strings.
chessmaster719:48:23
so there are 10C5 possbilities on ways to be able to removes X's without removing O's, or in other words, having chairs that are not adjacent
rrusczyk19:48:30
Therefore, the number of 5-element subsets of the first 14 integers with no two consecutive integers equals the number of 5-element subsets of the first 10 integers.
rrusczyk19:48:42
So, how do we finish?
Hyperboloid19:48:49
charles.du19:48:50
you just do 2002-252=1750
tinytim19:48:50
And the answer is 14C5-10C5=2002-252=1750=750 (mod 1000)
BenM19:48:50
so the answer is 14C5-10C5
Hyperboloid19:48:54
Subtract the complement form the total.
rrusczyk19:48:59
rrusczyk19:49:22
And that takes care of #6!!
rrusczyk19:49:32
Speaking of !!, it's time for #7!!
rrusczyk19:49:36
rrusczyk19:49:54
Icky notation. Whenever I see that on problem 6-10 on the AIME, my first thought is, "I'll bet this problem is way easier than it looks."
rrusczyk19:50:01
Let's see if I'm right. Where should we start?
all4math19:50:09
what does that where e thing mean
rrusczyk19:50:13
It's a summation.
rrusczyk19:50:33
It means you put in i=1, then i=2, then i=3, all the way up to 2009, and add up all the results you get.
rrusczyk19:50:50
What did you do when you first saw the problem?
rrusczyk19:51:01
Did you immediately start writing general formulas?
Hullohihell019:51:04
panic
rrusczyk19:51:24
Gotta get over that! I used to, too, but then I realized the nasty notation problems are often easiest!
chessmaster719:51:28
calculated the first few n's
federernadal19:51:29
look for a pattern
m1sterzer019:51:29
started trying the first few terms to see if I saw a pattern
BenM19:51:29
write a few terms
happysunnyshine19:51:29
try a few
rrusczyk19:51:33
This is what I usually do.
rrusczyk19:51:41
Let's look at the first few terms, if only to get used to the notation. What is the first term?
tinytim19:51:54
1/2
nechesskid1319:51:54
1/2
rrusczyk19:51:58
rrusczyk19:52:00
Not too interesting. Next term?
BenM19:52:13
3/8
tinytim19:52:13
3/8
mathq19:52:13
3/8
jweisblat1419:52:13
3/8
rrusczyk19:52:16
rrusczyk19:52:17
Next?
rrusczyk19:52:43
Simplify your result!
GoldenFrog161819:52:47
5/16
mathq19:52:47
5/16
jweisblat1419:52:47
5/16
nechesskid1319:52:47
15/48 = 5/16
rrusczyk19:52:50
rrusczyk19:53:06
Next?
geoffreywong19:53:45
35/128
jweisblat1419:53:45
35/128
e71421283519:53:45
35/128
late20s19:53:45
35/128
rrusczyk19:53:47
rrusczyk19:53:52
Are we ready to make any conjectures yet?
charles.du19:54:05
all the numerators are odd, and all the denominators are even
mismatchtea19:54:06
so the top appears to be consecutive odds, while the bottom is 2 raised to the nth power
GoldenFrog161819:54:06
denominator is always a power of 2
GoldenFrog161819:54:16
do you mean i=4 not 7?
rrusczyk19:54:25
Yes, I meant i=4 for that last case.
rrusczyk19:54:43
And i=2, i=3 for the previous 2.
tinytim19:54:48
if the denominator is always a power of 2, then b=1
rrusczyk19:54:51
It sure looks like the denominator will always be a power of 2. Will the next one be a power of 2?
rrusczyk19:55:18
How can we easily see what the next one is?
jweisblat1419:55:20
10 has a five
rrusczyk19:55:28
Yes it does, and what happens to that five?
spelljack82519:55:33
yes, 5|10
charles.du19:55:33
but it cancels
e71421283519:55:33
we multiply the denomonator by 10, and the 5 gets cancelled
rrusczyk19:55:37
Yes. The next term is 9/10 the previous term. The 5 in the 10 cancels with the 5 in the numerator.
rrusczyk19:55:42
Will this continue forever?
GoldenFrog161819:55:54
yes
geoffreywong19:55:54
yes
jweisblat1419:55:54
yes
nechesskid1319:55:54
The numerator will simplify all odd factors in the denominator.
tinytim19:55:54
Yes.
qwang19:56:18
the only way the denominator isn't a power of two is if it has 2*odd somewhere in there. however, the 'odd' will always cancel with one on top.
rrusczyk19:56:28
A true observation and .. . .
tinytim19:56:30
Because this is the AIME we have no need to prove it.:-D
rrusczyk19:56:42
If this were the USAMO, qwang's statement would need to be proved.
rrusczyk19:57:01
It's not enough to say that for every 2n in the denom, there's an n in the numerator. What happens if n is even?
rrusczyk19:57:10
We can get a sense for why it is true like this:
rrusczyk19:57:16
rrusczyk19:57:20
For each odd integer k greater than 1, we have:
rrusczyk19:57:23
k appears in the numerator before 2k appears in the denominator (since the denominator of the term with k in the numerator is just k+1).
rrusczyk19:57:27
3k appears in the numerator before 4k appears in the denominator.
rrusczyk19:57:30
5k appears in the numerator before 6k appears in the denominator
rrusczyk19:57:34
And so on.
rrusczyk19:57:38
This isn't perfectly rigorous, since more factors of k will appear in the coefficients of k in our argument. But then we can apply the same argument to those coefficients to take care of those factors, and so on.
rrusczyk19:58:01
I mention this argument because it is *exactly* the kind of convincing argument some of you will write on the USAMO, thinking you have a proof.
rrusczyk19:58:10
And then you'll get a 0/7 and wonder what happened.
rrusczyk19:58:47
Everything I wrote above is true, but the "and so on" part is not rigorous. We would have to prove that the "and so on" does continue forever.
charles.du19:58:49
wait so what gets you partial credit on USAMO
rrusczyk19:59:03
It's very hard to get partial credit on the USAMO -- ask about it on the message board.
rrusczyk19:59:14
Does anyone have a more rigorous explanation for why the odds always cancel out? (At this point, the observation above is enough to finish the problem, but let's really nail this one down by proving we're right for sure.)
GoldenFrog161820:01:22
2^i*i!
tinytim20:01:23
Start by noting (2i)!!=2^i(i!)... Is that still a typo...?
rrusczyk20:01:47
We have (2i)!! = 2^i * i!
rrusczyk20:02:05
Can we relate (2i)!! and (2i-1)! to something that we are more comfortable with?
rrusczyk20:02:25
Sorry, that should be (2i)!! and (2i-1)!!
spelljack82520:02:27
factorials!
rrusczyk20:02:37
And how can we relate these to factorials?
spelljack82520:03:10
(2i)!! * (2i-1)!! = 2i!
rrusczyk20:03:29
rrusczyk20:03:55
Where have you seen (2m)! and m! together before?
tinytim20:04:20
2mCm!
chessmaster720:04:20
combinations?
rrusczyk20:04:24
rrusczyk20:04:45
rrusczyk20:04:47
How else can we write that?
rrusczyk20:04:56
(Using our !! notation.)
rrusczyk20:05:37
(Also, please write (2m)! rather than 2m!. There's a big difference!)
chundai20:05:39
why is (2i)!!*(2i-1)!!=2i!
rrusczyk20:06:07
The (2i)!! has all the evens and the (2i-1)!! has all the odds. Together, they have all the numbers from 1 to 2i. That's (2i)!
rrusczyk20:06:31
Just above, we saw a way to write (2m)! in terms of !! -- what was that?
happysunnyshine20:07:00
2m!!*(2m-1)!!
rrusczyk20:07:11
rrusczyk20:07:26
OK. Keep going. We saw a way to bring m! into the mix, too. What was that?
e71421283520:08:01
(2^m)(m!) = (2m)!!
rrusczyk20:08:03
We had (2m)!! = 2^m * m!.
rrusczyk20:08:07
So...
GoldenFrog161820:08:08
2^m(2m-1)!!/m!
rrusczyk20:08:13
rrusczyk20:08:17
How does this help us?
rrusczyk20:09:06
What do we know is true about this number?
late20s20:09:08
a integer
rrusczyk20:09:24
This number is an integer because all C(n,r) are integers. Why does that help?
happysunnyshine20:09:26
why is (2^m)(m!) = (2m)!!?
rrusczyk20:10:00
(2m)!! = 2m * (2m-2) * . . . * 1 = 2^m[(m)*(m-1) *(m-2)* . . . *1]
rrusczyk20:10:41
How does the fact that this number is an integer help us? What does it tell us about (2m-1)!! and m!?
geoffreywong20:11:24
they cancel out all odd numbers for m!
charles.du20:11:44
we know m!|2^m(2m-1)!!
rrusczyk20:11:55
Exactly. Because 2^m(2m-1)!! / m! is an integer, all the odd factors of m! cancel with (2m-1)!!.
rrusczyk20:12:16
Going back to (2m-1)!! / (2m)!!, what do we now know?
tinytim20:13:04
Which leaves us with just powers of 2
tinytim20:13:04
that just equals (random stuff)/(2^i)
GoldenFrog161820:13:04
the odd factors cancel
rrusczyk20:13:16
rrusczyk20:13:23
We now know that all the denominators are powers of 2, so all we have to do is find the highest one.
rrusczyk20:13:48
That's the 7/7 proof. Didn't need it for the AIME, but now you should remember that "and so on" won't get you far on the USAMO next month.
rrusczyk20:14:01
rrusczyk20:14:05
This is a problem we know how to handle. How do we do it?
geoffreywong20:14:39
pull out the 2^i first
rrusczyk20:14:47
rrusczyk20:14:50
And how do we do that?
GoldenFrog161820:15:21
[2009/2]+[2009/4]+[2009/8]+...
kevmo31420:15:21
Count those divisible by 2, then 4, then 8, and so on, and add them up.
Hullohihell020:15:21
count 2s then 4s then 8s and so on
spelljack82520:15:27
[2009/2] + [2009/2^2] +...
chessmaster720:15:30
count factors of largest factor of 2 smaller than 2009, then 2nd largest factor, 3rd largest, and so on
rrusczyk20:15:33
rrusczyk20:15:55
So. . .
tinytim20:16:11
add 2009 to that
rrusczyk20:16:20
tinytim20:16:53
Which gives 2^{4010} in the denominator. So a/10=401
chessmaster720:16:53
so a=4010 from the original question
jweisblat1420:16:53
4001*1/10=401
rrusczyk20:16:56
charles.du20:16:59
I just went ahead and found a for this problem to be 401 and realized that b had to be one, or ab/10 would be over 1000 :D
rrusczyk20:17:08
Funny -- that's a bit of a bug in the problem :)
rrusczyk20:17:34
(This would have been a better USAMTS problem than an AIME problem -- you can get the answer without doing the most interesting part of the problem.)
rrusczyk20:17:42
But now we're ready for number 8!
rrusczyk20:17:48
rrusczyk20:17:54
One approach is to set up a big infinite series indexed by the number of rolls it takes each person to roll a 6.
rrusczyk20:18:00
That seems ugly to me.
rrusczyk20:18:11
What's another way to approach the problem?
rrusczyk20:18:48
I see some pretty complicated suggestions!
nechesskid1320:19:02
Geometric series
rrusczyk20:19:18
That will work, but let's see if we can find a simpler approach.
rrusczyk20:19:22
What can happen on the first roll?
m1sterzer020:19:29
recognize that if neither person rolls a 6 on the first roll, you are back to where you started
rrusczyk20:19:35
Very interesting observation!
rrusczyk20:19:38
Let's investigate.
rrusczyk20:19:54
So, what are the things that could happen on the first roll?
charles.du20:19:58
6 or not 6 for either person
tinytim20:20:05
6 or no 6
Hullohihell020:20:05
6 or not a 6
rrusczyk20:20:14
If they both get a 6 right way, they win.
jweisblat1420:20:19
1/36 for both 6
rrusczyk20:20:24
This occurs with probability 1/36.
rrusczyk20:20:33
What about neither get 6?
tinytim20:20:46
25/36
nechesskid1320:20:46
25/36
late20s20:20:46
25/36 for reatarting the game
Hullohihell020:20:46
25/36
charles.du20:20:46
25/36
rrusczyk20:20:48
If they both don't get a 6, they'll have to roll again.
rrusczyk20:20:52
This occurs with probability 25/36.
geoffreywong20:20:56
goes back to original setup
rrusczyk20:21:02
And then we're back where we started.
rrusczyk20:21:06
So the rest of the time, with probability 10/36, exactly one of them will roll a 6.
rrusczyk20:21:09
Then what happens?
nechesskid1320:21:24
The other has to roll a six
Hullohihell020:21:24
the other has to roll
deltaren20:21:24
the other has to roll a 6
rrusczyk20:21:27
They win if the other person rolls a 6 on their next roll.
chessmaster720:21:33
then 10/36*1/6=10/216=5/108 for then to win
rrusczyk20:21:54
This occurs with probability 1/6, so the probability is (10/36)(1/6) that they'll win this way.
rrusczyk20:22:09
How can we use all these observations *to finish the problem*.
tinytim20:22:37
Let x be the answer. x=1/36+10/36*1/6+25/36x
sa31420:22:37
write an equation
GoldenFrog161820:22:37
5/108+1/6+25/36p=p
rrusczyk20:22:43
Exactly.
rrusczyk20:22:49
We let p be the probability they win.
rrusczyk20:23:21
We have p = (win on first roll) + (win on one rolling a 6 first and the other rolling a 6 second) + (win on neither rolling a 6 first).
rrusczyk20:23:25
In other words:
rrusczyk20:23:32
rrusczyk20:23:40
The first term is "win on first roll"
rrusczyk20:23:58
The second term is when one rolls a 6 on the first turn and the other rolls a 6 on the next turn.
rrusczyk20:24:10
Otherwise, with probability 25/36, they get to try again and win with probability p --- that's the third term.
rrusczyk20:24:39
We add up the probability of winning in each case, and we get the overall probability.
rrusczyk20:24:46
So, we have that equation!
rrusczyk20:24:52
Now we just have to solve for p.
chessmaster720:25:25
we get 11p/36=8/108=4/54=2/27, so 72=297p and p=24/99=8/33
tinytim20:25:25
11/36p=8/108 gives p=8/33
rrusczyk20:25:32
Now it's just an algebra problem.
rrusczyk20:25:38
Multiply through by 36 and collect terms:
rrusczyk20:25:43
rrusczyk20:25:46
rrusczyk20:25:48
Thus the answer is 8 + 33 = 041.
mismatchtea20:25:51
wow, nice....just like solving an infinitely continuing fraction
rrusczyk20:26:16
We go through problems like these in our Intermediate Counting book.
m1sterzer020:26:21
not bad --- beats pounding through the geometric series
ThinkFlow20:26:21
So... when the problem can return to a previous state, we can usually do something like this?
rrusczyk20:26:39
Exactly -- we call the strategy we use for problems like this "state diagrams".
asdfjklasdfjkl20:26:40
im buying that!
rrusczyk20:26:43
:)
rrusczyk20:26:50
And now for number 9
rrusczyk20:26:58
spelljack82520:27:25
bijection!
dgreenb80120:27:25
relate the two
rrusczyk20:27:34
How can we relate the two?
Hyperboloid20:27:40
What is a bijection?
tinytim20:27:40
1-1 correspondence
rrusczyk20:27:55
A bijection is a 1-1 correspondence, like we did in an earlier problem.
asdfjklasdfjkl20:27:57
notice that when y=3 or more its the same problem
Wikipedian133720:27:58
In the second equation, if y > 3, there it's the same as the first equation.
ThinkFlow20:28:33
why?
rrusczyk20:28:38
Good question -- why?
dgreenb80120:29:10
For each solution x,y,z in the second equation, there exists a solution x,y+3,z in the first
charles.du20:29:10
because if (x,y,z) solves the second one, (x,y+3,z) solves the first one
chessmaster720:29:12
3*3 (which is y) yields 9, which can be added to 2000 to get 2009. but since y is not fixed, the equations become the same again
rrusczyk20:29:35
We can pair up solutions:
(x,y+3,z) to the first <---> (x,y,z) to the second for y > 0.
tinytim20:29:52
For EVERY soltuion to the second equation, we can add 3 to the y value to get a soltuion to the first eqaution. Thus we count the number of soltuions to the first equation that we CANT get back to the first equation by subtracting 3 from the y value.
rrusczyk20:29:54
So we have a 1-1 correspondence of solutions:
(x,y',z) to the first with y' > 3 <----> (x,y,z) to the second
where y'= y+3.
rrusczyk20:30:00
This pairs every solution of the second equation to a solution of the first equation with y>3, and vice versa.
rrusczyk20:30:09
So what are the "left over" solutions to the first equation?
mathq20:30:22
so we solve for y=1,2,3
ThinkFlow20:30:22
y<=3
BenM20:30:22
y=1,2,3
rrusczyk20:30:36
We have the solutions where y is 1, 2 or 3.
rrusczyk20:30:57
(We have to include the y=3 case because we are interested in *positive* integer solutions, so we can't have y=0 in the second equation.)
charles.du20:31:03
and y cant be 2 because then the whole LHS would be even, and 2009 is odd
funtwo20:31:03
y cant be 2 because of parity
rrusczyk20:31:07
Noting that y must be odd, we see we must have y=1 or y=3.
rrusczyk20:31:15
So, now we have a much simpler problem.
tinytim20:31:26
If y=1 then we must find the number of solutions to 2(x+2z)=2009-3 or x+2z=1003
rrusczyk20:31:49
rrusczyk20:32:22
How do we count the solutions to 4x + 2z = 2006? (We can divide by 2 to get 2x + z = 1003.)
BenM20:32:55
x can range from 1 to 501 and there is a unique z for each x
mathq20:32:55
total 501 solutions
FantasyLover20:32:55
z=1, 3, ..., 1001
charles.du20:33:03
everything from (501,1) to (1,1001) works, so we have 501 solutions
rrusczyk20:33:05
We have z = 1003-2x, so x can be anything from 1 to 501.
rrusczyk20:33:19
And for 4x + 2z = 2000 (otherwise known as 2x + z = 1000)?
tinytim20:33:51
Similarily for 2x+z=1000, x can be anything from 1 to 499.
funtwo20:33:51
x=1-499 because z must be positive
BenM20:33:51
x ranges from 1 to 499
e71421283520:33:51
z=1000 - 2x, so x can be anything from 1 to 499
mathq20:33:51
(1,998) to (499,2), 499 solutions
rrusczyk20:33:53
We have z = 1000 - 2x, so x can be anything from 1 to 499.
rrusczyk20:34:05
So /. . . .
jweisblat1420:34:09
1000
mathq20:34:09
501+499=1000
charles.du20:34:11
our answer is 499+501/1000 = OMG 000
mathq20:34:11
sothe answer is 0
rrusczyk20:34:14
So we have a total of 501 + 499 = 1000 solutions.
tinytim20:34:17
Adding the number of solutions to the two equations gives 1000. THis means that m-n=1000 and the answer is 000!:-o
BenM20:34:27
000 mod 1000
jweisblat1420:34:27
answer = 000
spelljack82520:34:27
499 + 501 = 0 (mod 1000) :-c
rrusczyk20:34:28
The answer is thus 000.
mathq20:34:43
rare to get 0 for the answer...
rrusczyk20:34:58
It happens more than average. It has happened twice.
Smartguy20:35:20
wasn't there one in 2000?
tinytim20:35:20
Once on the 2000 AIME i believe
rrusczyk20:35:24
One more problem, and then I'm going to take a short break.
rrusczyk20:35:29
rrusczyk20:35:52
Not exactly an appealing problem with all those words.
geoffreywong20:35:55
diagram?
e^i_penguin20:35:55
draw a picture
Hullohihell020:35:55
draw a diagram
rrusczyk20:36:01
A lot of words for a pretty simple diagram. Of course, I drew it wrong the first time I saw the problem.
rrusczyk20:36:04
In the interests of not being here all night, here's the correct diagram:
rrusczyk20:36:09
mathq20:36:12
ABC makes an right triangle
rrusczyk20:36:24
We could do this with analytic geometry and/or bash it out with trig, but let's see if we can find a nicer solution without those crutches.
rrusczyk20:36:32
We know that AB = 5, BC = 12, AC = 13, and the angles are marked as in the diagram. What else can we determine?
tinytim20:37:21
Extend DC so it meets line AB at sy E.
charles.du20:37:21
extend CD to AB to get a nice isosceles triangle
wangsacl20:37:21
I prefer to intersect the extension of both AB and CD
rrusczyk20:38:33
Interesting observation -- write me a full solution with that and I'll post it at the end :)
rrusczyk20:38:43
I see many of you suggesting this:
GoldenFrog161820:38:48
angle bisector
Hullohihell020:38:48
well you could use angle bisector theorem possibly
Wikipedian133720:38:48
angle bisector theorem
rrusczyk20:38:58
We have an angle bisector of an angle in triangle ABC.
rrusczyk20:39:02
rrusczyk20:39:10
Applying the Angle Bisector Theorem to angle bisector AF in triangle ABC, we have BF/CF = AB/AC. So, what are BF and CF?
charles.du20:39:50
10/3 and 26/3
chessmaster720:39:56
10/3 = BF and 26/3 = CF
rrusczyk20:40:04
Since AB is 5/18 of AB+AC, we know that BF is 5/18 of BF + FC, which is 12. Therefore, BF = 12*(5/18) = 10/3, and FC = 12 - BF= 26/3.
rrusczyk20:40:18
Now what might we be on the lookout for?
ThinkFlow20:40:33
similar triangles
tinytim20:40:33
Similar Tiangles
chessmaster720:40:38
similar triangles?
rrusczyk20:40:40
We have a right angle. We have equal angles. We should look for similar triangles. Do we have any?
chessmaster720:41:07
not yet...
rrusczyk20:41:11
That's the spirit.
rrusczyk20:41:15
not *yet*
billy31420:41:20
we could draw some auxillary lines
happysunnyshine20:41:21
No, but we can create
ThinkFlow20:41:26
Draw some
rrusczyk20:41:30
How can we make some easily?
rrusczyk20:42:06
(I think there are a lot of ways to finish from here.)
billy31420:42:09
Draw the segment from D parallel to segment BA
ThinkFlow20:42:10
Draw D perpendicular to BC
rrusczyk20:42:13
We draw the altitude from D to BC.
rrusczyk20:42:17
rrusczyk20:42:26
Now what?
tinytim20:42:45
ABF is similar to DHF
chessmaster720:42:45
find DF and FA using similar triangles and we have answer!
funtwo20:42:45
BAF~HDF
ThinkFlow20:42:50
We find the ratio of similarity, and we can find via pythag AF, so we find our answer
rrusczyk20:42:57
We now have a problem we know how to handle.
rrusczyk20:43:02
Let's knock off the details.
rrusczyk20:43:05
We have DHF ~ ABF.
rrusczyk20:43:07
What else?
rrusczyk20:43:15
(Any other similarities?)
chessmaster720:43:28
CHD and CBA
ThinkFlow20:43:28
DHC similar to ABC
funtwo20:43:28
CDH and CAB
rrusczyk20:43:30
We also have DHC ~ ABC.
rrusczyk20:43:50
OK, let's get to work with these. How? What's our first step in setting up equations?
chessmaster720:44:19
we need to find DH?
rrusczyk20:44:26
Sure. Let's call that x.
rrusczyk20:44:38
What else do we have?
mathq20:45:28
CH:CB=x:AB which equals CH:12=x:5
ThinkFlow20:45:28
FH = 2/3x
GoldenFrog161820:45:28
x/5=CH/12
rrusczyk20:45:35
From DHF ~ ABF, we have FH/DH = BF/AB = 2/3, so FH = 2x/3.
rrusczyk20:45:41
From DHC ~ ABC, we have CH/DH = BC/AB = 12/5, so CH = 12x/5.
rrusczyk20:46:07
And what do we do with this?
ThinkFlow20:46:15
FH + HC = 26/3
tinytim20:46:49
so x=65/23
rrusczyk20:46:57
rrusczyk20:47:03
Now, we're set. How do we find AD?
mismatchtea20:47:43
pythagorean's theorem?
ThinkFlow20:47:43
pythag
GoldenFrog161820:47:43
sqrt((AB+HD)^2+(BH)^2)
rrusczyk20:47:52
rrusczyk20:47:57
rrusczyk20:48:03
We could pound this out with the Pythagorean Theorem now. Anyone see an easier way to do it?
tinytim20:48:25
continue using similar traingles
chessmaster720:48:25
similar triangles again? :)
rrusczyk20:48:35
Yep. Similar triangles to the rescue again. DXA ~ FBA.
rrusczyk20:48:45
How does that get us to the answer relatively quickly?
ThinkFlow20:49:12
pythag on ABF
e71421283520:49:19
BA and BF are nice numbers, so we can easily find AF, and use ratios
rrusczyk20:49:26
rrusczyk20:49:46
Now it's just arithmetic.
rrusczyk20:50:25
We could do it this way:
chessmaster720:50:27
do pythagoras to find AF then multiply by AX or AB
ThinkFlow20:50:27
AF = 5\sqrt{13}/3
rrusczyk20:50:31
Or this way:
rrusczyk20:50:35
rrusczyk20:50:59
Here are solutions with the "extend a side" approach:
wangsacl20:51:03
Extend AB and CD, so both of them intersect at E. We get AE=10, CE=13, AC=13. By applying the angle bisector theorem: DE=130/23, DC=169/23. Then, we could compute AD using this formula: AD^2=AC x AE - CD x ED. Then, we get: (let's skip the rigorous part): AD=60\sqrt{13}/23. Then, we get p+q+r=096
wangsacl20:51:03
you could derive that from stewart's theorem
dgreenb80120:51:03
Full solution with extension: Let AB and CD intersect at A'. We have, A'B=5 and A'C=13, by the angle bisector theorem we have CD=169/23 and DA'=130/23. Now Stewart's on triangle ABC finds AD (a little messy but not too bad) is 60sqrt{13}/23.
rrusczyk20:51:25
(You can see why I didn't continue with that approach -- looking for a solution without the heavy machinery of Stewart.)
Wikipedian133720:51:28
I did the problem using coordinates and found it much more straightforward than pure geometry.
rrusczyk20:51:40
There's another way to approach the problem.
chessmaster720:51:42
theres another (more complicated) way to extend CD to meet AB, then inscribe a circle and find the radius to be 10/3 (which is BF) and find AD from finding AF and FD from there.
rrusczyk20:51:45
And another.
ThinkFlow20:51:47
Should I know stewart's theorem?
rrusczyk20:52:02
It's really not that important. But I would try to prove it for fun.
spelljack82520:52:04
trig bashing is quick and straightforward
m1sterzer020:52:04
the trig solution seems pretty elegant as well (perhaps even moreso than the geometry approach)
rrusczyk20:52:12
Beauty is in the eye of the beholder :)
MathAndKnowledge20:52:26
just the derivation, because you can easily derive it when you need a cevian length
rrusczyk20:52:32
True: (about Stewart)
rrusczyk20:52:36
We'll take a 5 minute break and then knock off the last 5 problems.
Hullohihell020:56:53
how much longer is this math jam going to last?
rrusczyk20:57:01
Maybe 75 minutes.
ThinkFlow20:57:05
Just looked at http://en.wikipedia.org/wiki/Stewart's_theorem. Stewart's theorem seems pretty useful to me...
rrusczyk20:57:22
So - so. I think that any math contest problem that requires Stewart is just a bad problem.
rrusczyk20:58:01
On to problem 11!
rrusczyk20:58:06
rrusczyk20:58:18
Where do we start with this?
charles.du20:58:56
|log(m/k)| < log n
geoffreywong20:58:56
log(m/k)
dgreenb80120:58:56
log m-log k=log(m/k)
rrusczyk20:59:13
GoldenFrog161820:59:17
turn the abs value into 2 inequalities
m1sterzer020:59:17
rewrite the equation for positive and negative (log(m) - log(k))
charles.du20:59:30
and then get rid of the absolute value
rrusczyk20:59:41
We have two inequalities to worry about to get rid of the absolute value.
rrusczyk20:59:47
What are the cases we have to worry about?
late20s20:59:51
get rid of the log as well?
rrusczyk20:59:56
We'd love to do that :)
rrusczyk21:00:14
Let's get rid of the absolute value first.
rrusczyk21:00:15
How?
m1sterzer021:00:23
m > k and m < k
rrusczyk21:00:37
If m>=k, then what do we have?
tinytim21:01:11
m/k<n
happysunnyshine21:01:11
m/k< n
rrusczyk21:01:31
happysunnyshine21:02:05
k/m<n
funtwo21:02:05
k/m<n, k<mn
tinytim21:02:12
If k>m, we have m/k>1/n (from log(1/n)=-logn)
Wikipedian133721:02:12
m/k > 1/n
rrusczyk21:02:15
rrusczyk21:02:41
So, we must have both m/k < n and k/m < n. Now what?
funtwo21:03:25
dangit i already forgot how i got m/n<k<mn
funtwo21:03:25
oh i remember it now. rearrange the first inequality to get m/n<k
tinytim21:03:25
so we have m/n<k<mn
wangsacl21:03:25
restrict the value of k
rrusczyk21:03:40
From m/k < n, we have k > m/n, and from k/m < n, we have k < nm, so the values of k that satisfy the inequality range from m/n to mn.
rrusczyk21:03:42
Now what?
mathq21:03:47
use the fact that there are only 50 solutions?
rrusczyk21:03:50
We know that there must be exactly 50 integers k between m/n and mn (exclusive, meaning we can't include m/n or mn). How does that help?
Wikipedian133721:04:55
mn = floor(m/n) + 51
wangsacl21:04:55
floor(m/n)+1<=k<=mn-1, so there are mn-floor(m/n)-1 possible values of k
rrusczyk21:05:10
We can say essentially this without the fancy notation, like this:
rrusczyk21:18:19
rrusczyk21:05:39
(That's often how I avoid floor notation -- just make an inequality instead.)
rrusczyk21:05:58
All that says is "there are 50 integers from m/n to mn, exclusive".
rrusczyk21:06:04
There's nothing fancy there.
Wikipedian133721:06:13
That's why I was stuck on mn = floor(m/n) + 51 during the test and couldn't go any further!
rrusczyk21:06:33
Yeah, notation can really trap you!
rrusczyk21:06:47
Going to inequalities is a good way to get away from the floor notation.
rrusczyk21:06:48
Now what?
tinytim21:06:52
We only need to try n=1,2,...,7 because m>=n
rrusczyk21:07:02
This immediately places some restrictions on n. Since m >= n, if n > 7, then m(n-1/n) is more than 52. So, we can only have n = 2,3,4,5,6, or 7. (Obviously, n=1 won't work!)
tinytim21:07:05
n=1 obviously doesnt work
rrusczyk21:07:09
That doesn't give us too much to test!
rrusczyk21:07:13
What happens for n=7?
rrusczyk21:07:56
If n=7, we have 52 > m(7-1/7) >= 50. Any luck?
tinytim21:08:00
no solution
Wikipedian133721:08:00
nope
funtwo21:08:03
nothing
rrusczyk21:08:06
No solutions here; if m=7, then m(7 - 1/7) is 48, and if m = 8, then the product is 48/7 more, which gives us a number that is greater than 52.
rrusczyk21:08:12
And we just keep cranking down.
rrusczyk21:08:15
If n=6, we have 52 > m(6 - 1/6) >= 50. Any luck?
tinytim21:08:26
nope
mathq21:08:26
no solutions?
nope
funtwo21:08:26
no
rrusczyk21:08:28
Again, no. Here, we see that m(6-1/6) < 50 if m = 8 and m(6-1/6) >= 52 if m=9.
rrusczyk21:08:34
If n=5, we have 52 > m(5 - 1/5) >= 50. Any luck?
mathq21:08:56
no again
chessmaster721:08:56
no
rrusczyk21:09:01
Nope. m = 10 gives us 48 and m = 11 gives us a number greater than 52. No luck.
rrusczyk21:09:05
If n=4, we have 52 > m(4 - 1/4) >= 50. Any luck?
tinytim21:09:11
no
mathq21:09:12
no...
rrusczyk21:09:13
Nope. m = 13 gives us 48 3/4 and m = 14 gives us a number greater than 52. No luck.
spelljack82521:09:16
is there no better way than trying all the remaining cases?
rrusczyk21:09:41
I don't know -- I don't think there's a way that's easier to see than bashing this out :)
chessmaster721:09:43
well trying the cases isn't necessarily what you would call "time consuming"
rrusczyk21:09:46
Exactly :)
rrusczyk21:09:54
If n=4, we have 52 > m(4 - 1/4) >= 50. Any luck?
charles.du21:10:19
we just did that
rrusczyk21:10:21
lol
rrusczyk21:10:27
If n=3, we have 52 > m(3 - 1/3) >= 50. Any luck?
funtwo21:10:38
yes! 3*19=57, 19/3>6
tinytim21:10:39
Yay,m=19
chessmaster721:10:39
m can be 19
GoldenFrog161821:10:40
19
rrusczyk21:10:42
Yes! m = 19 gives us m(3 - 1/3) = 50 2/3. We test that (m,n) = (19,3) satisfies the problem.
rrusczyk21:10:47
late20s21:12:08
7 - 56
charles.du21:12:08
7 through 56
andrewda21:12:08
7to56
spelljack82521:12:08
56>=k>=7
rrusczyk21:12:10
Any k that is more than a third of 19 and less than 3 times 19 satisfies the inequality. That gives us 7, 8, 9, . . . , 56. Indeed, there are 50 such k.
rrusczyk21:12:15
And finally, n = 2, which gives us 52 > m(2 - 1/2) >= 50. Any luck?
tinytim21:12:47
yay again, m=34
wangsacl21:12:47
34
rrusczyk21:12:50
Yes. Here, m=34 is the lucky number, since 34(2-1/2) = 51.
rrusczyk21:12:54
rrusczyk21:12:59
And our answer is ?
tinytim21:13:39
So the sum of all possible mn is 19*3+34*2=125.
GoldenFrog161821:13:39
68+57=125
charles.du21:13:39
68+57=125
wangsacl21:13:39
68+57=125?
rrusczyk21:13:41
The answer to the problem then is 3(19) + 2(34) = 125.
ThinkFlow21:14:44
So we didn't like absolute values or logs so we found a way to get rid of them?
rrusczyk21:14:47
Exactly.
ThinkFlow21:18:55
next problem?
rrusczyk21:18:58
Good idea.
rrusczyk21:19:04
rrusczyk21:19:19
Any ideas where to start?
rrusczyk21:20:03
One way to start with this would be to try a smaller set of integers, like 1 through 5 or 1 through 7. Unfortunately, no patterns jump out when we try this.
rrusczyk21:20:07
We might also try constructing pairs in some smart way, but that runs into trouble pretty quickly. There are all sorts of strategies to take in making the pairs, and it's not clear which is best or why.
tinytim21:20:13
Try to find the upper bound of k?
rrusczyk21:20:21
We have a maximization problem -- we want to find the maximum value of k. Finding a maximum means that we need to show that k <= (some number), and that it is possible for k to equal that number. In other words, we need to build an inequality that involves k.
rrusczyk21:20:40
How might we go after finding an inequality that involves k?
spelljack82521:20:47
sum the sums?
funtwo21:20:47
consider the total sum of all the pairs
rrusczyk21:21:01
Can we bound this sum in any useful way?
math15421:22:39
For k sets, the minimum sum of the numbers in all is 1+2+...+2k, and the maximum sum is 2009+2008+...+(2010-k), and clearly the maximum sum has to be greater than the minimum for k to work.
rrusczyk21:22:55
We can bound the sum of all the numbers in the pairs. If we add all 2k numbers in the k pairs, the smallest the sum can possibly be is 1+2+3+ . . . + 2k, which equals k(2k+1). Letting the sum of the 2k numbers in the pairs be s, we have s >= k(2k+1).
rrusczyk21:23:07
Where does the upper bound math154 identified come from?
funtwo21:23:35
all sums must be distinct and <=2009
happysunnyshine21:23:37
all sums are distinct and less than or equal to 2009
rrusczyk21:23:41
Since each pair of numbers has sum no greater than 2009, and the sums are all distinct, we have s <= 2009 + 2008 + 2007 + . . . + (2010 - k).
rrusczyk21:23:49
Can we write that more simply?
GoldenFrog161821:24:22
2010k-k(k+1)/2
rrusczyk21:24:25
We can write this more simply as s <= 2010k - (1+2+3+. . . +k) = 2010k - k(k+1)/2.
rrusczyk21:24:31
And now?
funtwo21:24:47
minimum must be less than maximum
ThinkFlow21:24:47
write our inequality
tinytim21:24:47
Combine and solve the inequality
rrusczyk21:24:53
rrusczyk21:25:00
And what does this tell us?
tinytim21:25:48
Solving for k gives k<=803
funtwo21:25:48
a regular quadratic inequality, k>0<804
rrusczyk21:25:59
Nothing fancy here. Just a bit of algebra.
rrusczyk21:26:04
rrusczyk21:26:15
rrusczyk21:26:20
Are we finished?
rrusczyk21:26:44
We have a guess. But on the USAMO, we wouldn't nearly be done.
rrusczyk21:26:50
We have to:
tinytim21:26:56
Now we must find 803 pairs that satisfy the conditions...
ThinkFlow21:26:56
no; that's a bound
charles.du21:26:56
need to find a way to use 803 pairs
#H34N121:26:56
Prove that value is achievable?
tinytim21:26:56
we cant just assume that 803 works.
m1sterzer021:26:56
need to show that 803 can be achieved
rrusczyk21:27:02
Not quite finished. We have to show that it is possible to come up with 803 pairs that have different sums. All we have shown is that it is not possible to have more than 803 pairs. (So, at the very least, we have a decent *guess* at the answer.)
rrusczyk21:27:06
Where might we start with building the pairs?
rrusczyk21:27:16
What might your first step be in trying to build 803 pairs?
rrusczyk21:28:09
If you were to write out 803 blank pairs, what numbers might you write as the first in each?
happysunnyshine21:28:55
1,2,3..803
GoldenFrog161821:28:55
1-803
billy31421:28:55
1,2,3,...,803
rrusczyk21:29:03
We can start by trying to build 803 pairs in which a number from 1 to 803 is one of the numbers in each pair. So, the pairs are:
(1, ?)
(2, ?)
(3, ?)
. . .
(803, ?)
rrusczyk21:29:21
What are we pretty sure at least one of these sums will equal?
billy31421:29:43
2009
chessmaster721:29:43
2009?
Bl00d21:29:43
2009
GoldenFrog161821:29:43
2009
tinytim21:29:43
2009?
rrusczyk21:30:08
OK, we start with the extremes. Are we going to make an extreme low sum with 803?
Bl00d21:30:18
no
spelljack82521:30:21
no
rrusczyk21:30:25
Certainly not.
Bl00d21:30:27
so that would probably = 2009
rrusczyk21:30:36
Let's start with the extremes. We won't make a little sum using the 803, since we've already used all the numbers from 1 to 803. So, we'll make a big sum there:
(1, ?)
(2, ?)
(3, ?)
. . .
(803, 1206)
cool4ever21:31:22
figure out the sums
rrusczyk21:31:30
What do we think the other sums will be?
ThinkFlow21:31:45
sums: 2008, 2007, 2006, etc.?
GoldenFrog161821:31:52
2008,2007,2006...
rrusczyk21:31:55
All the way down to what?
chessmaster721:32:10
1207
charles.du21:32:10
1207
rrusczyk21:32:12
No sum can be greater than 2009, so we try to build pairs that will give us the 803 greatest possible sums. That is, the sums 2009, 2008, 2007, . . ., 1207.
rrusczyk21:32:27
So, we made the biggest sum with 803.
rrusczyk21:32:32
Can we make the smallest with 1?
ThinkFlow21:32:40
no
spelljack82521:32:40
no
charles.du21:32:40
no
rrusczyk21:32:48
Nope; we already used 1206.
rrusczyk21:32:56
So, what will we do to make 1207?
chessmaster721:33:07
so we go to 2 with 1205
tinytim21:33:07
2,1205
e71421283521:33:12
2 and 1205?
rrusczyk21:33:13
We can't make 1207 with 1, since we've already used 1206. So, we use 2:
(1, ?)
(2, 1205)
(3, ?)
. . .
(803, 1206)
rrusczyk21:33:16
What next?
tinytim21:34:02
try to make the second largest sum? (2008)
rrusczyk21:34:12
How are we going to make 2008? With 802?
tinytim21:34:31
we cant to 802,1206 so we must to 801,1207
ThinkFlow21:34:31
uses 1206, so no
GoldenFrog161821:34:31
no, 801
funtwo21:34:31
we cant. 801
rrusczyk21:34:34
We take another step, building 2008. We can't do so with 802, since 1206 is taken, so:
(1, ?)
(2, 1205)
(3, ?)
. . .
(801, 1207)
(802, ?)
(803, 1206)
rrusczyk21:34:42
What's next?
m1sterzer021:34:52
back to the small end
tinytim21:34:52
then do the second smallest sum
happysunnyshine21:34:56
1208
e71421283521:34:56
1208?
chessmaster721:34:56
now can we do the second smallest sum
rrusczyk21:35:00
Which is?
tinytim21:35:09
3,1205 doesnt work so 4,1204
chessmaster721:35:10
4 and 1204 = 1208
m1sterzer021:35:10
4 + 1204
e71421283521:35:10
4, 1204
rrusczyk21:35:11
Next, we make 1208. We can't use 3, but we can use 4:
(1, ?)
(2, 1205)
(3, ?)
(4, 1204)
. . .
(801, 1207)
(802, ?)
(803, 1206)
rrusczyk21:35:20
Aha!
tinytim21:35:24
a pattern!
chessmaster721:35:43
since we're going up along even numbers and down along odds, all the sums will work like teeth of a comb fitting together
rrusczyk21:35:47
And now the pattern emerges!
(2,1205)
(4,1204)
(6,1203)
(8,1202)
. . .
(802, 805)
(803,1206)
(801,1207)
(799, 1208)
. . .
(1, 1607)
rrusczyk21:35:59
There is joy in Mudville.
rrusczyk21:36:00
We thereby form the sums 1207, 1208, . . . 1607,1608,1609, . . ., 2009, as desired.
rrusczyk21:36:09
The maximum value of k is therefore 803.
rrusczyk21:36:23
Now we're finished. (There are other ways to form 803 sums -- see if you can find some.)
rrusczyk21:36:44
But for now, we're on to #13
rrusczyk21:36:48
rrusczyk21:37:05
rrusczyk21:37:20
We could go after this with all sorts of trig. But . . .
funtwo21:37:23
this immediately reminds of roots of unity
rrusczyk21:37:42
Regular polygons. Already in a circle! This really makes us think of complex numbers.
rrusczyk21:38:00
How can we relate the problem to complex numbers?
dragon9621:38:24
the real imaginary plane
rrusczyk21:38:41
And how can we view these on the complex plane?
funtwo21:38:54
C1 is the first 14th root of unity, C2 is the second 14th root of unity...
tinytim21:38:54
Let the Center of the semicircle be the origin
charles.du21:38:54
let 0+0i be the midpoint of AB
rrusczyk21:38:58
rrusczyk21:39:14
rrusczyk21:39:19
ThinkFlow21:39:58
But how do we find the lengths of the chords?
rrusczyk21:40:16
Good question. Do we want to stick with the diagram we have up there?
hello12321:40:29
1-w^i
rrusczyk21:40:42
Will this work for the chords at B?
all4math21:41:01
no
GoldenFrog161821:41:04
they are the same for B
rrusczyk21:41:12
The chords have the same lenth, yes.
m1sterzer021:41:32
we can replace the chords from B with chords drawn to the lower half of the circle
rrusczyk21:41:43
Geometrically speaking, we can use this fact to make the diagram prettier:
rrusczyk21:41:48
rrusczyk21:42:39
We want the product of all of these lengths except for the middle one (the diameter), which is not included in the problem.
rrusczyk21:42:51
Now, how can we write that product of lengths in terms of complex numbers?
funtwo21:44:12
the distance between two points is the magnitude of their difference
benzi45521:44:12
abs of product of (2-2w^n) as n ranges from 1 to 13 but does not equal 7
rrusczyk21:44:15
The distance between w and z in the complex plane is |w-z|. So, we can write our desired product as:
rrusczyk21:44:19
rrusczyk21:44:31
all4math21:44:33
It looks cleaner
rrusczyk21:44:39
It looks a lot clearner!
rrusczyk21:44:45
Cleaner, too.
rrusczyk21:44:51
How can we compute this product?
xelalex123103021:44:57
but it helps to add it in
rrusczyk21:45:26
Then what will the product look like -- that is, what product that we know how to handle will it look like?
xelalex123103021:45:56
put that factor back in, and note that it's 1 + z + z^2 + ... + z^13 evaluated at 1
hello12321:45:56
consider the factored for of x^13+x^12+.....+1
rrusczyk21:46:10
Let's see where that comes from:
rrusczyk21:46:10
ThinkFlow21:46:37
it doesn't depend on w?
rrusczyk21:46:57
funtwo21:47:00
roots of x^14=1
xelalex123103021:47:00
it's x^14 - 1!
rrusczyk21:47:08
rrusczyk21:47:21
So, how will we get from this to the product we want:
rrusczyk21:47:34
rrusczyk21:47:51
We want to jam in x = 1, but then we get . . . 0=0.
rrusczyk21:47:58
Hurm. That's no fun. What do we do?
tinytim21:48:16
divide by (x-1) first.
Yongyi78121:48:16
Divide by (x-1)
rrusczyk21:48:25
rrusczyk21:48:29
How does the right-hand side simplify?
Yongyi78121:48:46
1+x+x^2+...+x^13
rrusczyk21:48:48
rrusczyk21:48:54
rrusczyk21:49:08
So, do we have our desired product?
tinytim21:49:20
iremember to divide by 2
math15421:49:20
No, but w^7=-1, so 1-w^7=2 and we can divide this out to get the desired expression.
xelalex123103021:49:20
but then divide by two because 1 - w^7 = 1 - (-1) = 2
rrusczyk21:49:28
rrusczyk21:49:32
rrusczyk21:49:39
rrusczyk21:49:48
And now we're finally ready to find:
tinytim21:50:05
So the answer is 2^12*7=672 (mod 1000)
funtwo21:50:06
7*96=672
rrusczyk21:50:11
rrusczyk21:50:34
Complex numbers are fun.
rrusczyk21:50:44
And now it's time for number 14.
wangsacl21:50:47
Is there any other approaches?
rrusczyk21:50:57
A wall of trig identities can get you there, I'm betting.
spelljack82521:51:04
much nicer than trig bashing XP
rrusczyk21:51:18
Yeah, complex numbers hide a lot of the machinery of trig in very nice ways.
dragon9621:51:24
its interesting how a geometry problem turns out to use the roots of unity
rrusczyk21:51:39
Whenever you see a regular polygon in a hard problem, this is something you should consider.
rrusczyk21:51:45
rrusczyk21:51:59
Where would you naturally start with this problem to get a handle on it?
MathAndKnowledge21:52:11
compute some terms
happysunnyshine21:52:11
to try some
ThinkFlow21:52:11
plug small values in
charles.du21:52:11
generate first few terms
rrusczyk21:52:22
rrusczyk21:52:31
rrusczyk21:52:40
rrusczyk21:52:51
You may be able to see some patterns, but the most significant observation is that each of the terms we computed is rational.
rrusczyk21:53:09
rrusczyk21:53:39
Any suggestions (assuming you don't see the magical trig substitution at this point)?
tinytim21:54:02
Take out the square root?
rrusczyk21:54:17
That would be nice, but squaring this looks ugly.
rrusczyk21:54:38
What's ugly about the expression in the square root?
rrusczyk21:54:46
(That is, what's hard to deal with?)
funtwo21:54:49
4^n
ThinkFlow21:54:49
n in an exponenet
xelalex123103021:54:49
the 4^n
tinytim21:54:49
4^n
rrusczyk21:54:56
Yeah, the 4^n is no fun.
rrusczyk21:55:01
What might we do about that?
xelalex123103021:55:10
we could divide out by it
rrusczyk21:55:19
Let's see what that looks like:
rrusczyk21:55:33
What does the resulting equation look like?
PI-Dimension21:56:22
8/5 a_n+6*2^n/5sqrt(1-thingy)
rrusczyk21:56:36
rrusczyk21:57:05
Hmm. Not beautiful. But not quite as scary. What might we do to make it even less scary?
xelalex123103021:57:15
let b_n = a_n / 2^n
rrusczyk21:57:21
And why would we do that?
PI-Dimension21:57:41
get rid of the denominator
ThinkFlow21:57:41
get rid of n in the exponent
xelalex123103021:57:41
then we could get rid of all the 2^n terms
rrusczyk21:57:42
Our goal here is to make the radical expression something we are less afraid of.
rrusczyk21:57:56
xelal's substitution gives:
rrusczyk21:58:19
rrusczyk21:58:30
Ugh. Now we have a's and b's. What do we do?
chessmaster721:58:57
write everything in terms of b_n?
bbill95521:58:57
convert a's to b's
ThinkFlow21:59:02
express everything in b's. The 2^n disappears as well
facis21:59:02
divide by 2^n and substitute more b's in
rrusczyk21:59:04
We sub in for b for the other a's as well.
rrusczyk21:59:12
rrusczyk21:59:18
rrusczyk21:59:27
This is an equation you can almost take home to mom and dad.
Yongyi78121:59:30
Trig substitution?
funtwo21:59:30
looks like pythagorean identity
rrusczyk21:59:58
Now, the trig substitution becomes a little more apparent. But we don't need it to finish. What might we do now that we have a simpler equation?
benzi45522:00:15
crank it
rrusczyk22:00:34
We can start cranking out terms. We already have the first few:
rrusczyk22:00:38
rrusczyk22:00:51
What happens when we go after the next one?
ThinkFlow22:00:57
difference of squares!
rrusczyk22:01:06
This observation is particularly helpful here.
hello12322:02:20
what?
rrusczyk22:02:34
I mean, using difference of squares makes computing b_4 particularly easy.
rrusczyk22:02:40
What is it?
RoFlLoLcOpT22:03:34
$\frac{24}{25}$
rrusczyk22:03:37
ThinkFlow22:03:56
it repeats???
funtwo22:03:56
epic.
rrusczyk22:04:03
What does this tell us?
Bl00d22:04:05
wow
rrusczyk22:04:07
yeah.
xelalex123103022:04:22
b_10 = 24/25 also
myrealname22:04:28
follow the pattern, you get b_10 = 24/25
rrusczyk22:04:33
It means that the terms b_2, b_3, b_4, ... alternate between 24/25 and 117/125.
rrusczyk22:04:42
Bl00d22:04:44
Could we have just cranked it out from the very beginning?
rrusczyk22:04:59
You'd have to catch the fact that the numerators are going up by factors of 4.
m1sterzer022:05:02
it takes a bit of chutzpah to keep churning after that 117/125
rrusczyk22:05:10
True, but it's a recursion, and the AIME.
rrusczyk22:05:18
But the more natural approach is this:
charles.du22:05:20
let b_n = sin theta
rrusczyk22:05:35
Once you see sqrt(1-b^2), this substitution should come to mind.
rrusczyk22:06:00
(It makes finishing the problem a good bit easier if you're careful.)
rrusczyk22:06:18
(It's also a more powerful general technique that you'll use again and again.
Bl00d22:06:27
Coould we have just calculated a4
rrusczyk22:06:35
Sure, but the a_i don't repeat!
rrusczyk22:06:46
Remember, the b_i are a_i divided by 2^i.
rrusczyk22:07:08
Work out the trig substitution approach -- there's still a little trickery to work through there!
hello12322:07:15
so b_n+1=4/5*sintheta +3/5*costheta how does this help?
rrusczyk22:07:20
How does that help?
xelalex123103022:07:45
sin addition formula
funtwo22:08:02
3-4-5 triangle
rrusczyk22:08:21
There's your hint. I'll let you sort out the details :)
rrusczyk22:08:33
One more problem!
rrusczyk22:08:39
rrusczyk22:08:57
Sigh. All those words.
rrusczyk22:09:02
We start with a diagram.
rrusczyk22:09:05
rrusczyk22:09:24
As with many good geometry problems, there are all kinds of first steps we can take here. There are many extra segments we can add, many angles and lengths we can find, and many angles and lengths we can relate to each other.
rrusczyk22:09:31
Before getting lost in a thicket of these observations, let's focus our efforts. Let's come up with a plan by focusing on what we need to find.
rrusczyk22:09:38
We want to learn about d, which is PQ. What are likely strategies for doing so?
rrusczyk22:09:45
For example, are we likely to be able to hit triangle PQC with the Law of Cosines?
funtwo22:10:25
well angle PCQ is constant
rrusczyk22:10:36
True. A and B are fixed, so <PCQ is fixed.
rrusczyk22:10:50
But why are we scared about law of cosines on PQC?
hello12322:11:07
PC and QC are variing
benzi45522:11:07
that's the only part of PQC that we know
rrusczyk22:11:11
We know that <ACB is fixed, which is promising, but we know very little about PC and QC, so the Law of Cosines doesn't look too promising. The Law of Sines suffers from the same problem.
rrusczyk22:11:29
What's likely to be our general strategy for getting at PQ? What are we likely to go after?
m1sterzer022:12:00
MN - MP - QN?
e71421283522:12:00
MP and QN?
rrusczyk22:12:18
The most obvious remaining strategy is to go after MP and QN, and then subtract from 1.
rrusczyk22:12:34
Are we going to be able to combine them in some magical way, or should we go after them separately?
tinytim22:12:58
separately
dgreenb80122:12:58
separately, then add
ThinkFlow22:13:04
separately
all4math22:13:04
separate
rrusczyk22:13:06
We probably aren't going to be able to get at both of them at once, so let's focus on just one of them:
rrusczyk22:13:09
rrusczyk22:13:26
(In complicated geometry problems, redrawing a simpler diagram with just the pieces you're focusing on will sometimes help a great deal. Here, we know we can ignore AC, since MP does not in any way depend on A or C.)
ThinkFlow22:13:40
should be able to determine based on location of C
rrusczyk22:13:53
That's the goal. But how? What observations can we make?
myrealname22:14:04
cross-chord theorem?
tinytim22:14:04
power of a point
rrusczyk22:14:24
We have (MP)(PN) = (BP)(CP).
rrusczyk22:14:45
It's not clear what we'll do with that.
rrusczyk22:15:00
We'll stick it up there anyway in case it becomes handy.
xelalex123103022:15:02
but PN = 1 - MP
dgreenb80122:15:03
PN=1-MP
rrusczyk22:15:10
We know that MN = 1, so MP = 1 - PN.
rrusczyk22:15:24
OK. We could combine that with the power of a point equation:
tinytim22:15:26
(1-MP)(MP)=(BP)(CP)
rrusczyk22:15:34
Not so obvious what to do with that...
rrusczyk22:15:36
Hmmm.
rrusczyk22:15:59
Stuck. On a geometry problem. What do we wonder when we are stuck on a geometry problem?
ThinkFlow22:16:13
What have we not used?
MathAndKnowledge22:16:18
what haven't we used yet
rrusczyk22:16:28
Exactly -- that's what we ask when we are stuck on a geometry problem.
dgreenb80122:16:32
we havent used diameter
ThinkFlow22:16:32
MB=3/5
m1sterzer022:16:32
BM=3/5
hello12322:16:32
location of B
tinytim22:16:32
MB=3/5
rrusczyk22:16:51
Haven't used the fact that MN is a diameter, and we haven't touched the length of BM.
rrusczyk22:16:56
How can we use these?
hello12322:17:14
BN=4/5
rrusczyk22:17:34
Since MN is a diameter, BMN is a right triangle, and BN = 4/5.
rrusczyk22:17:46
Hmm. What else does that suggest we look at?
ThinkFlow22:18:10
MCN
rrusczyk22:18:16
And what do we know about that?
tinytim22:18:37
also right triangle
e71421283522:18:37
its a right triangle, too.
spelljack82522:18:37
right angle triangle
dgreenb80122:18:37
its right
rrusczyk22:18:43
rrusczyk22:18:58
OK, we now have some right triangles, and we know BN.
rrusczyk22:19:03
Um, now what?
tinytim22:19:32
cyclic quad?
rrusczyk22:19:44
True. Are we excited about breaking out Ptolemy?
tinytim22:19:54
no...
xelalex123103022:19:54
not really
rrusczyk22:20:01
Ptolemy: (MN)(BC) = (BN)(CM) + (BM)(CN)
rrusczyk22:20:04
This doesn't involve MP or PN. No good.
rrusczyk22:20:12
Hurm.
rrusczyk22:20:34
Still stuck. The only useful relationships we have for MP so far are those we have above.
rrusczyk22:20:40
Those with MP and PN.
rrusczyk22:20:47
MP and PN . . .
rrusczyk22:20:50
MP and PN . . .
rrusczyk22:20:56
Tell me about those two.
ThinkFlow22:21:01
Which sum to 1
Yongyi78122:21:01
MP + PN = 1...
rrusczyk22:21:05
True. . .
rrusczyk22:21:14
What else is interesting about those two segments?
late20s22:21:37
the base of two triangles?
rrusczyk22:21:54
And what does that make us think?
tinytim22:22:10
area?
funtwo22:22:10
areas?
Yongyi78122:22:10
Area?
rrusczyk22:22:35
. . . Interesting. And how will we relate these two segments to area?
dgreenb80122:22:51
part of similar triangles?
rrusczyk22:22:57
They are part of similar triangles.
rrusczyk22:23:02
So?
rrusczyk22:23:08
What else are they part of ?
ThinkFlow22:23:11
They are a diameter?
rrusczyk22:23:21
They are part of the same *line*.
rrusczyk22:23:34
This leads me to one of my very favorite sneaky geometry strategies.
tinytim22:23:38
their ratio is equal to the ratio of the areas of the triangles
benzi45522:23:38
MP is to [BMC] as NP is to [BNC]
rrusczyk22:23:41
Whenever I have two important segment lengths along the same line in a tough geometry problem, I consider using area as a tool. We have
MP/PN = [BMP]/[BNP].
rrusczyk22:23:53
Do we know anything about the areas of these triangles that might be helpful?
ThinkFlow22:24:11
They add up to 6/5
rrusczyk22:24:16
True.
rrusczyk22:24:21
Anything else?
tinytim22:24:40
6/25 you mean?
rrusczyk22:24:43
Ya.
rrusczyk22:24:45
(We know the sum PM + PN, too. . . )
rrusczyk22:24:50
What else?
ThinkFlow22:24:59
proportional to MCN
rrusczyk22:25:07
What do you mean?
tinytim22:25:58
[BPC]/[PCN]=[BPM]/[MPC]
spelljack82522:25:59
MP/PN = [BMP]/[BNP] = [MPC]/[NPC]
rrusczyk22:26:02
We similarly have MP/PN = [PMC]/[PCN].
rrusczyk22:26:27
We don't know a whole lot about those two triangles. Hurm.
rrusczyk22:26:44
But these triangle area equalities seem interesting. . .
dgreenb80122:27:12
a/b=c/d means a+b/c+d equals them?
rrusczyk22:27:22
True; and what does that give us here?
dgreenb80122:27:47
[BMC][BNC]
rrusczyk22:27:53
We can combine the two area relationships we just found and note that
MP/PN = [BMC]/[BNC].
rrusczyk22:28:01
Is there anything interesting about these two triangles?
mathq22:28:45
share BC
late20s22:28:45
same base: BC
rrusczyk22:28:47
What else?
BenM22:29:05
related angles
rrusczyk22:29:08
How?
spelljack82522:29:10
BNC + BMC = 180..?
ThinkFlow22:29:10
M is the supplement of N
m1sterzer022:29:13
angle M and angle N are supplementary
rrusczyk22:29:21
Aha! Why is that interesting?
dgreenb80122:29:33
area=(1/2)ab sin C?
benzi45522:29:33
same sine
m1sterzer022:29:37
same sine
rrusczyk22:29:59
Ah, this might be an interesting tree to bark at; what do we find for MP/PN starting from this observation?
dgreenb80122:31:14
MP/PN=(3MC)/(4NC)
tinytim22:31:24
that is (BM)(MC)/(BN)(CN)
xelalex123103022:31:24
MP/PN = (BM)(MC)/(BN)(NC)
rrusczyk22:31:54
rrusczyk22:32:11
Interesting
rrusczyk22:32:14
Why is this *particularly interesting* in this problem?
rrusczyk22:33:23
What I'm getting at here is that we've related MP/PN to MC/NC. MC and NC have *nothing to do with B*.
late20s22:33:49
cuz the other line share the same property
rrusczyk22:33:55
That means we can do essentially the same thing with point A to get an expression for MQ/QN in terms of C, not A or B. In other words, we can relate MP and QN, which is the goal in getting at PQ.
rrusczyk22:34:04
BenM22:35:36
Won't MQ/QN be equal to MC/CN
rrusczyk22:35:45
We do the same thing with Q:
rrusczyk22:35:46
rrusczyk22:36:02
ThinkFlow22:36:14
Because MAN is isoceles, right?
rrusczyk22:36:16
Right.
rrusczyk22:36:43
Now, what are we going to do.
rrusczyk22:36:49
We keep our eye on the ball. We want an expression for PQ that we can use. We have PQ = 1 - MP - QN.
rrusczyk22:37:03
So, what do we have to extract from those two equations up there?
hello12322:37:14
find expressions for PN and QN?
myrealname22:37:35
isolate MP and QN
rrusczyk22:37:37
We need expressions for MP and QN (PN and QN would be fine, too).
rrusczyk22:37:41
And how will we get these?
ThinkFlow22:37:43
Pn = 1-Mp and MQ = 1- QN
rrusczyk22:38:08
And what will we do about the right sides of those ratio equations to make this easier to deal with?
BenM22:38:25
make a new variable?
rrusczyk22:38:31
We can express both MP/PN and MQ/QN in terms of MC/NC. Moreover, we have PN = 1-MP and MQ = 1-QN, so we can express MP and QN in terms of MC/NC. That means we can express PQ in terms of this ratio. Let's give it a try.
spelljack82522:38:34
substitute a = MC/NC
rrusczyk22:38:39
rrusczyk22:39:06
Now we're getting somewhere. We find MP and QN:
rrusczyk22:39:09
ThinkFlow22:39:11
Now we can solve for MP and QN in terms of t, right?
rrusczyk22:39:14
Exactly.
rrusczyk22:39:19
And what do we do with these?
BenM22:39:31
substitute into that expression we had for PQ
ThinkFlow22:39:34
Subtract from 1
rrusczyk22:39:43
rrusczyk22:39:49
What do we do with that?
BenM22:39:56
simplify
mathq22:39:56
simplify
rrusczyk22:40:03
rrusczyk22:40:07
rrusczyk22:40:21
This is promising. It's a quadratic. The AIME-ized form of the answer looks like the root of a quadratic equation. We're on the right track.
rrusczyk22:40:26
But what do we do now?
BenM22:40:47
solve for t
ThinkFlow22:40:49
maximize d
rrusczyk22:40:51
How?
rrusczyk22:40:58
What do we know about t?
late20s22:41:32
oh, t is positive
BenM22:41:37
t is positive
spelljack82522:41:37
t is positive?
rrusczyk22:41:41
Do we know anything else about it?
rrusczyk22:42:18
What is t defined as?
dgreenb80122:42:22
t is a root of the quadratic
rrusczyk22:42:30
It is a root of the quadratic.
mathq22:42:33
MC/NC
tinytim22:42:33
MC/CN
ThinkFlow22:42:33
MC/NC
rrusczyk22:42:41
It is a ratio. This ratio is positive.
rrusczyk22:42:46
It is also . . .
m1sterzer022:42:48
it can range from 0+ --> infinity
rrusczyk22:42:50
real.
rrusczyk22:42:56
Which tells us . . .
dgreenb80122:43:16
discriminant is positive!
MathAndKnowledge22:43:16
discriminant >= 0
rrusczyk22:43:32
The discriminant of the quadratic is nonnegative.
rrusczyk22:43:37
rrusczyk22:43:41
There was the equation we had.
rrusczyk22:44:18
What do we do now?
funtwo22:44:45
move the t over
rrusczyk22:44:50
MathAndKnowledge22:45:17
d^2-14d+1>=0 i think by plugging in the discriminant
tinytim22:45:17
D=d^2-14d+1
funtwo22:45:23
compute the discriminant in terms of d
rrusczyk22:45:29
This quadratic in t must have real solutions. That means that its discriminant must be nonnegative. We're set now.
rrusczyk22:45:33
rrusczyk22:46:08
And how do we finish this?
ThinkFlow22:46:33
draops22:46:33
quadratic formula
aggarwal22:46:33
complete the square
funtwo22:46:33
14-rt192/2=7-4rt3 so 7+4+3=14
rrusczyk22:46:43
Completing the square or the quadratic formula tell us:
rrusczyk22:46:46
rrusczyk22:47:02
What does this tell you about the quadratic d^2 - 14d +1 ?
rrusczyk22:47:43
Remember, we had the inequality d^2 - 14d + 1 >= 0
rrusczyk22:47:58
We just found the roots. How can we finish?
funtwo22:48:00
it cant be more than 1 the diameter and it cant be between 7-4rt3 and 7+4rt3 so the maximum is 7-4rt3
rrusczyk22:48:14
mathq22:48:21
7-4sqrt3 because it's less than 1
rrusczyk22:48:23
rrusczyk22:48:29
This was a hard, hard problem.
