rrusczyk (18:00:07)
Hello and welcome to the 2007 AIME II Math Jam!

rrusczyk (18:00:11)
Before we get started, please note that this 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 discussion organized and on track.

rrusczyk (18:00:24)
This also means that only [b]well-written[/b] comments will be dropped into the classroom, so please take time to write responses that are complete and easy to read.

rrusczyk (18:00:34)
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.

DiscreetFourierTransform (18:00:44)
how do we display math as latex text again?

rrusczyk (18:01:02)
Precede your post with a semicolon.

rrusczyk (18:01:15)
Typing ;$\sqrt{x}$

rrusczyk (18:01:16)
gives

rrusczyk (18:01:22)


rrusczyk (18:01:34)
Let's get started with the problems!

rrusczyk (18:01:40)


rrusczyk (18:01:51)
//s3.amazonaws.com/classroom.artofproblemsolving.com/Classroom/cbe6/images/lx-18515358.gif

rrusczyk (18:01:55)
Where do we start?

DiscreetFourierTransform (18:01:57)
Two cases: zero doesn't appear, or it appears once or twice

conartist (18:02:17)
separate it into cases with no zeroes one zero and two zeroes

ra5249 (18:02:19)
break into cases (casework) i.e. how many zeros

rrusczyk (18:02:26)
There are a couple of approaches we can take. (I recommend tackling counting problems in 2 ways if you have time to and are able to - it's a great way to check your answer.)

rrusczyk (18:02:30)
First, we can do casework. We consider the case in which there are 2 zeros on the plate, and the case in which there is no more than 1 zero on the plate.

rrusczyk (18:02:34)
How many ways can we make a plate with two zeros?

ra5249 (18:02:50)
(5C2)(6P3)

tjhance_2 (18:03:02)
(5C2)6*5*4

rrusczyk (18:03:19)


rrusczyk (18:03:32)
And with no more than 1 zero?

bubble (18:04:01)
7*6*5*4*3

tjhance_2 (18:04:01)
7*6*5*4*3

rrusczyk (18:04:13)


rrusczyk (18:04:19)
So, what is our answer?

jen7 (18:04:29)
3720/10=372

hyang (18:04:57)
372

DiscreetFourierTransform (18:04:57)
The sum of the cases over ten

rrusczyk (18:05:06)


rrusczyk (18:05:31)
Notice that I didn't multiply out both cases and add. A little factoring reduces the chances of making an addition or multiplication error.

rrusczyk (18:05:50)
Does anyone see another way to do the problem (always nice to find more than 1 solution to counting problems!)

rrusczyk (18:06:23)
Suppose we start by assuming the zeroes are different.

rrusczyk (18:06:36)
Then how many plates are there?

Mmew (18:06:47)
8P5

bubble (18:06:50)
8*7*6*5*4

rrusczyk (18:06:57)


rrusczyk (18:07:06)
But alas, the 0's are not different. . .

rrusczyk (18:07:22)
What do we have to do?

rrusczyk (18:07:44)
I see a lot of 'divide by 2'.

rrusczyk (18:07:47)
Let's try it.

rrusczyk (18:07:58)
We divide by 2, and do we get the same answer as above?

DiscreetFourierTransform (18:08:06)
whoops

DiscreetFourierTransform (18:08:08)
nope

not_trig (18:08:12)
60*56=3360

PenguinIntegral (18:08:02)
won't work, because some plates contain 1 or no zeros

bubble (18:08:15)
subtract the number of plates with two 0's from the total

hyang (18:08:40)
subtract the number of times two zeroes appear because they are each counted twice; 8C2*6*5*4

Mmew (18:08:41)
we forgot to take into account the single and no-zero plates

rnwang2 (18:08:46)
you can't just divide by two because not all the license plates will have 2 0's

rrusczyk (18:09:01)
Exactly! We can't just divide by 2.

tjhance_2 (18:09:02)
just subtract the number of ways to make a licence plate with 2 0's

rrusczyk (18:09:14)
Let's do that!

rrusczyk (18:09:23)
We found this amount above:

rrusczyk (18:09:26)


rrusczyk (18:09:38)
Does this come out to be the same as our answer from above?

rrusczyk (18:11:14)
I see a lot of 'Yeses'. And only one 'No'. I suspect you're not multiplying it out!

DiscreetFourierTransform (18:10:54)
no

rrusczyk (18:11:33)
This number doesn't equal our answer from earlier. This is why I recommend doing counting problems twice. The computation we just did is what I did the first time I saw the problem. Then I did the problem the other way, and the answers didn't match. So, I knew I made a mistake somewhere. Where's my mistake? Is it here, or in our other solution?

not_trig (18:11:43)
here

rrusczyk (18:12:04)
Where? What have we overlooked? What other plates did we double count when we did 8*7*6*5*4?

tjhance_2 (18:12:18)
we also have to subtract the plates with only one zero as well!

Mmew (18:12:26)
each 0 was a separate 0 in our calculations of single-zero plates

rrusczyk (18:12:36)
We also double-count all the plates with 1 zero, since we include them once for each zero. How many of these plates are there?

hyang (18:13:46)
5C1*6*5*4*3

rrusczyk (18:13:53)
There are 5 slots to put the zero in, after which we're left with 6 characters (we throw out the second zero), so there are 5*6*5*4*3 plates with 1 zero.

rrusczyk (18:13:57)


rrusczyk (18:14:08)
This is why I like to do counting problems 2 ways. . .

rrusczyk (18:14:12)
On to problem 2:

rrusczyk (18:14:18)


rrusczyk (18:14:25)
//s3.amazonaws.com/classroom.artofproblemsolving.com/Classroom/cbe6/images/lx-136598414.gif

rrusczyk (18:14:31)
Where do we start?

magixter (18:14:31)
We can write this as (a, ax,ay)

not_trig (18:14:34)
let b=am, c=an

DiscreetFourierTransform (18:14:34)
Let b and C = ka and ja

rrusczyk (18:14:43)
Let's turn these words into math so we can get some equations we can work with.

rrusczyk (18:14:48)
We have b = ma for some integer m. Similarly, c = na for some integer n. Putting this into our equation gives a+ am + an = 100. So?

hyang (18:14:40)
divide everything by a

Theunluckyone (18:14:42)
Factor out a

stnenopxe era sgol! (18:14:56)
m + n + 1 = 100/a

rrusczyk (18:15:04)


rrusczyk (18:15:08)
How does this help?

not_trig (18:15:14)
a|100

hyang (18:15:18)
a must be a factor of 100

DiscreetFourierTransform (18:15:22)
We want a to be an integral factor of 100

Arnizzle (18:15:22)
put in the various factors of 100 for a

rrusczyk (18:15:32)
From this equation, we first see that a must be a divisor of 100. From this alone, we could pound through the casework and finish the problem, but is there something more clever we can do?

tjhance_2 (18:16:03)
well if 100/a=b then the number of solutions to m+n=b-2

Arnizzle (18:16:22)
the number of choices for m and n for a given a is 100/a - 2

rrusczyk (18:16:42)
We start with the observation that there are k-1 ordered pairs of positive integer solutions (m,n) to the equation m+n = k when k is a positive integer. So, there are
100/a - 1 - 1 = 100/a - 2 solutions to our equation m + n = 100/a - 1.

rrusczyk (18:16:52)
What do we have to be careful about here?

Arnizzle (18:16:50)
a=1 gives 98 options, a = 2 gives 48, etc

tjhance_2 (18:17:00)
0 is not a positive integer!

DiscreetFourierTransform (18:17:01)
That we're dealing with integers

hyang (18:17:07)
when 100/a is 1

rrusczyk (18:17:18)
If a = 100, then our equation m+n = 100/a - 1 becomes m+n = 0, which has no solutions, not 100/a - 2 = -1 solutions. So, for each equation of the form m+n = 100/a - 1, we have 100/a - 2 solutions, except for when a = 100, where we have 0 solutions instead of -1 solutions. We keep this one special case in mind, and continue.

rrusczyk (18:17:47)
So. . . Rather than list out all the equations, find the number of solutions to each, then add up all those numbers, is there something slicker we can do?

not_trig (18:17:48)
but the sum of 100/a = sum of a (a|100)

rrusczyk (18:18:41)


rrusczyk (18:19:00)
So, when we add all the 100/a terms, we have the sum of the divisors of 100. How do we compute this quickly?

tjhance_2 (18:18:19)
(1+2+4)(1+5+25) will generate the sum of all factors of 100

rrusczyk (18:19:30)


rrusczyk (18:19:42)
So, the sum of the divisors of 100 is (7)(31) = 217.

rrusczyk (18:19:47)
But what else must we remember?

not_trig (18:19:53)
subtract 18, add one

magixter (18:19:57)
So the number will be 217 - 2*9 + 1

hyang (18:20:04)
to subtract the 2's, then add the extra 1 for the exception

rrusczyk (18:20:20)
We have 100/a - 2 solutions for each of our equations. When we add these all up, we have all those -2 terms.

rrusczyk (18:20:31)


rrusczyk (18:20:37)
Or do we?

Theunluckyone (18:20:45)
No, add 1.

not_trig (18:20:47)
except that one exception where 100/a=1

DiscreetFourierTransform (18:20:49)
add the one exception back

rrusczyk (18:20:57)
We always have to be on the lookout for off-by-one mistakes on the AIME. The best place to look for these is the boundary cases. Above, we mentioned that when a = 100, our equation is m + n = 0, which has 0 solutions, not 100/a - 2 = 100/100 - 2 = -1 solutions. So, our total of 217 - 2(9) solutions is 1 solution too low, since it comes from adding in -1 solutions when a = 100.

rrusczyk (18:21:05)


not_trig (18:21:18)
wouldn't brute-forcing prevent off-by-one mistakes here

DiscreetFourierTransform (18:21:20)
that was a nice problem to do with some quick casework

rrusczyk (18:21:39)
Brute-forcing carries its own hazards.

rrusczyk (18:21:48)
But if you have time, doing both is a nice way to check.

rrusczyk (18:21:54)
And we're ready for problem 3!

rrusczyk (18:22:05)


rrusczyk (18:22:17)
//s3.amazonaws.com/classroom.artofproblemsolving.com/Classroom/cbe6/images/lx-141238526.gif

rrusczyk (18:22:22)


rrusczyk (18:22:27)
http://s3.amazonaws.com/classroom.artofproblemsolving.com/Images/Transcripts/9dcdd19f2c2f7b27b3fb9a3a65454807.png

rrusczyk (18:22:33)
There are lots of ways to do this problem. We can build right triangles (the right angles and the fact that we want EF^2 are clues to do that), or we could use coordinates (bleck).

DiscreetFourierTransform (18:22:12)
hahaaha took me forever till i did ptolemys on a cyclic quadrilateral

rrusczyk (18:22:45)
There's yet another way to do it.

rrusczyk (18:23:10)
We could build a right triangle like this:

rrusczyk (18:23:13)


rrusczyk (18:23:26)
We can find EG and FG with some work. But is there a slicker way?

not_trig (18:22:13)
EXTEND THE SIDES OF THE TRIANGLES TO FORM A SQUARE AND WE'RE DONE!!!

stnenopxe era sgol! (18:22:39)
just realign the triangles to form a 17 x 17 square

hyang (18:23:05)
simply extend EB and FC to meet, and it's quite simple from there

tjhance_2 (18:23:06)
extend the legs of the triangles

not_trig (18:23:07)
extend sides of triangles, and we have a 17x17 square, so the diagonal is 17sqrt(2)

rrusczyk (18:23:49)
If we continue with the diagram above, we'll run into:

panjia123 (18:23:34)
horrifying computations though

rrusczyk (18:24:04)
Exactly. So we step back, and think 'outside the box'. And we see:

rrusczyk (18:24:10)
Another way to build right triangles with hypotenuse EF is to extend the sides of the right triangles:

rrusczyk (18:24:14)


rrusczyk (18:24:16)
http://s3.amazonaws.com/classroom.artofproblemsolving.com/Images/Transcripts/6ef08ed98601484a7aecbf581b2d254b.png

rrusczyk (18:24:20)
Now we have something pretty! How do we finish?

DiscreetFourierTransform (18:24:35)
note that the sidelength of the big square is 17

13375P34K43V312 (18:24:38)
the side length is 12+5 so the diagonal is 17rt2

tjhance_2 (18:24:39)
side length of the square is 17 so the diagonal is 17sqrt(2)

rrusczyk (18:24:55)


rrusczyk (18:25:07)
3 down. 12 to go.

rrusczyk (18:25:10)
Here's #4:

rrusczyk (18:25:15)


rrusczyk (18:25:21)
//s3.amazonaws.com/classroom.artofproblemsolving.com/Classroom/cbe6/images/lx-248906158.gif

rrusczyk (18:25:26)
We have two given sets of information and we want to relate them to a third set of information. What can we do to be able to compare or combine these three sets of information?

not_trig (18:25:21)
get it in worker-hours

DiscreetFourierTransform (18:25:34)
first we want everything is worker-hours

rrusczyk (18:25:44)
We make the number of hours and the number of workers in each piece of information the same. Let's rewrite each statement as the amount of gadgets to be built by one worker in one hour. What does 'In one hour, 100 workers can produce 300 widgets and 200 whoosits' become?

not_trig (18:25:54)
1 worker hour: 3 widgets, 2 whoosits

magixter (18:26:30)
1 hour, 1 worker, 3 widgets, 2 whoosits

rrusczyk (18:26:41)
This tells that 1 worker can make 3 widgets and 2 whoosits in an hour.

rrusczyk (18:26:46)
How about 'In two hours, 60 workers can produce 240 widgets and 300 whoosits'?

magixter (18:26:56)
1 hour, 1 worker, 2 widgets, 2.5 whoosits

Someone (18:26:58)
2hr: 1 : 4: 5

ra5249 (18:27:05)
2 hr, 1 worker, 4 widgets, 5 whoosits

stnenopxe era sgol! (18:27:07)
1 worker hour 2 widgets 2.5 whoosits

rrusczyk (18:27:21)
This tells us that in two hours, one worker makes 4 widgets and 5 whoosits. So, in one hour, one worker makes 2 widgets and 2.5 whoosits.

rrusczyk (18:27:27)
How can we rewrite 'In three hours, 50 workers can produce 150 widgets and m whoosits'?

magixter (18:27:41)
1 hour, 1 worker, 1 widgets, m/150 whoosits

Arnizzle (18:27:58)
1 hour, 1 worker, 1 widget, m/150 whoosits

Theunluckyone (18:27:59)
1 hour,1 worker, 1 widget, m/150 whoosits

rrusczyk (18:28:06)
This tells us that in three hours, one worker makes 3 widgets and m/50 whoosits. So, in one hour, one worker makes 1 widget and m/150 whoosits.

rrusczyk (18:28:11)


rrusczyk (18:28:15)
How does this help us finish the problem?

panjia123 (18:28:24)
arithmetic sequence

not_trig (18:28:26)
arithmetic progression

Arnizzle (18:28:37)
arithmetic progression!

not_trig (18:28:42)
so m/150=3 => m=450

hadasah (18:28:46)
time it takes for a worker to make one whoosit is the time it takes for a worker to make two widgets

jen7 (18:28:55)
m/150=3

rrusczyk (18:29:06)
The first two rows tell us that decreasing the number of widgets by 1 increases the number of whoosits by 0.5. So, when we go down from 2 widgets to 1 widget, the number of whoosits goes from 2.5 up to 3. So, we have m/150 = 3, which tells us that m = 450.

rrusczyk (18:29:35)
A lot of you also built equations to represent the information in the problem; this works pretty quickly, too.

rrusczyk (18:29:42)
On to #5.

rrusczyk (18:29:47)


rrusczyk (18:29:51)
//s3.amazonaws.com/classroom.artofproblemsolving.com/Classroom/cbe6/images/lx-224647519.gif

rrusczyk (18:29:56)
Notice anything interesting about the coefficients?

not_trig (18:30:04)
9*223=2007

DiscreetFourierTransform (18:30:07)
The coefficients are factors of 2007

Theunluckyone (18:30:14)
9 times 223 is 2007

rrusczyk (18:30:32)
We have 9*223 = 2007. That seems important. At the very least, we immediately know that our line connects (223,0) and (0,9). At this point, we could see a gut-it-out casework approach.

rrusczyk (18:30:36)
We could look at each row of squares. Because the line doesn't go above y=9 in the first quadrant, we only have 9 rows to consider. Also, there are clearly no full squares in the top row (those squares between y=8 and y=9), so we only have 8 rows to consider. Then, we have a bunch of arithmetic to find the number of squares in each row. . .

rrusczyk (18:30:42)
Ick.

rrusczyk (18:30:45)
What might we do instead?

conartist (18:29:55)
picks theorem!!!

13375P34K43V312 (18:30:49)
pick's theorem

rrusczyk (18:31:07)
That'll definitely work - I think it's discussed on the message board.

rrusczyk (18:31:22)
But what if you don't know Pick's Theorem (and to those that do, let's see you prove it!)

Arnizzle (18:31:14)
count the number of squares the line passes through

redcomet46 (18:31:20)
use the mathcounts method! for two relatively prime numbers m and n, the number of grids a diagonal goes through in an m*n grid is m+n-1

rrusczyk (18:32:05)
What will we do if we can count all the squares the line passes through? How does this help?

magixter (18:32:21)
Then, make a rectangle with 3 of its vertices, (0,9) (0,0) (223,0)

rrusczyk (18:32:46)
We could look at the whole rectangle bounded by (0,0), (223,0), (223,9), and (0,9). We think to do this because it's easy to count the number of whole squares in this box - there are 9*223 = 2007. Then what do we need to do?

tjhance_2 (18:32:39)
consider the the 9x223 rectangle... find the area, subtract the number of squares the line passes through, and then divide by 2

not_trig (18:32:57)
subtract, divide by 2

rrusczyk (18:33:13)
Once we figure out how many squares the line passes through, we can deduct this from 2007, then divide by 2, since half the remaining squares will be above the line and half below.

rrusczyk (18:33:20)
How can we count the number of squares that the line passes through?

Arnizzle (18:32:14)
You know that it passes through 8 vertical lines and 222 horizontal ones

rrusczyk (18:34:21)
Counting the number of squares that the segment from (223,0) to (0,9) passes through is the same problem as counting the number squares the segment from (0,0) to (223,9) passes through. This is a pretty familiar problem!

rrusczyk (18:34:56)
So, how many squares do we pass through going from (0,0) to (223,9)?

13375P34K43V312 (18:35:05)
231

DiscreetFourierTransform (18:35:31)
231

magixter (18:35:32)
231

rrusczyk (18:35:38)
For each vertical line from x = 1 to x = 222, when we cross the line, we enter a new square. That gives us 222 squares. Similarly, crossing each horizontal line from y = 1 to y = 8 gives us a square, for 8 more. We also have the square we start in, for 1 more square. Since 223 and 9 have no common divisors, we never go through a corner until we get to (223,9), so we aren't overcounting. So, we have 222+8+1 = 231 squares total.

rrusczyk (18:35:47)
So, what is our final answer?

magixter (18:32:51)
Subtract (9*223) - 231. Then divide by 2 to get 1776/2 = 888

not_trig (18:36:05)
(2007-231)/2=1876/2=888

DiscreetFourierTransform (18:36:06)
(2007 - 231)/2

rrusczyk (18:36:20)
The line passes through 231 of the 2007 squares in our rectangle, so there are 2007-231 = 1776 full squares in the rectangle that the line doesn't hit. Half of these are below the line, so our answer is 1776/2 = 888.

rrusczyk (18:36:36)
I'll now turn the room over to DPatrick for the next 4 problems.

DPatrick (18:36:42)


DPatrick (18:36:46)
//s3.amazonaws.com/classroom.artofproblemsolving.com/Classroom/cbe6/images/lx-218024607.gif

DPatrick (18:36:54)
(Let's abbreviate ""parity-monotonic"" to p-m so we don't have to keep typing it out.)

DPatrick (18:37:13)
So, to restate the condition in English, every digit that comes after an odd digit must be higher, and every digit that comes after an even digit must be lower.

DPatrick (18:37:30)
How can we proceed?

tjhance_2 (18:37:34)
you can't use 0 or 9

DPatrick (18:37:49)
One observation is that if 0 or 9 is a digit, it must be the last digit, since nothing can come after a 0 or a 9.

bubble (18:37:34)
i used brute force but it toke a long time

DiscreetFourierTransform (18:37:46)
Casework maybe?

DPatrick (18:38:17)
One can certainly brute force it (since these are only 4-digit numbers).

DPatrick (18:38:43)
But we might think about recursion, since we can somewhat easily create a smaller version of the same problem.

magixter (18:38:39)
Start working backwards

DPatrick (18:39:15)
Right...if we have a 4-digit p-m number, we can chop off the front digit and get a 3-digit p-m number. So we can try to build them up from smaller such p-m numbers.

hyang (18:38:57)
start with the two last digits, find the pattern, essentially like recursion

not_trig (18:39:08)
start with 2-digit

DPatrick (18:39:34)
Why not start with 1-digit?

DPatrick (18:39:44)
How many 1-digit p-m numbers are there?

DiscreetFourierTransform (18:39:45)
Because every one digit number is p-m

not_trig (18:39:49)
0-9 all work... so 10

hadasah (18:39:51)
10

DPatrick (18:40:15)
Right, they all work (we'll include 0 as a ""1-digit"" number since we'll want to build off it), so we have 10.

DPatrick (18:40:30)
Now, the key step: in how many ways can we add a digit to a 1-digit p-m number to get a 2-digit p-m number?

not_trig (18:40:38)
4

DiscreetFourierTransform (18:41:01)
append a digit to the left, or you can append one to the right

DPatrick (18:41:32)
A little experimentation will show that given a p-m number, there are always exactly 4 digits that we can add in front of it to get another p-m number that's one digit longer.

DPatrick (18:41:40)


DPatrick (18:42:03)
So what's the recursion?

panjia123 (18:42:15)
*4

tjhance_2 (18:42:20)


DPatrick (18:42:33)


not_trig (18:41:55)
so it's 10*4*4*4 = 640

hyang (18:42:21)
4*4*4*10

bubble (18:42:28)
so10*4^3=640

DPatrick (18:42:51)


DPatrick (18:42:57)


not_trig (18:42:45)
but isn't a_n the digit?

DPatrick (18:43:19)
You're right -- I chose my notation very poorly. :(

DPatrick (18:43:52)
I should have used f_n for the recursion (or anything different from a_n).

DPatrick (18:43:53)
Oh well.

DPatrick (18:44:02)
Let's move on to #7.

DPatrick (18:44:08)


DPatrick (18:44:12)
//s3.amazonaws.com/classroom.artofproblemsolving.com/Classroom/cbe6/images/lx-159740958.gif

DPatrick (18:44:37)
How can we rewrite some of the given data in a more useful form?

not_trig (18:44:52)


Someone (18:45:12)
well all n_i must be between two consecutive cubes

DPatrick (18:45:50)


DiscreetFourierTransform (18:45:48)


DPatrick (18:46:11)


DPatrick (18:46:31)


DiscreetFourierTransform (18:46:42)
expand the RHS

DPatrick (18:47:09)
Sure, we can expand that out, and let's divide by k too while we're at it.

DPatrick (18:47:18)


DPatrick (18:47:32)
How many i's must there be?

samath (18:47:36)
70

DiscreetFourierTransform (18:47:37)
70

DPatrick (18:47:57)
Right, the problem told us 70, but how many in terms of k (from our inequality above)?

Xaero_2 (18:48:25)
3k+4

DiscreetFourierTransform (18:48:34)
3k + 4 values

DPatrick (18:48:41)
Right.

DPatrick (18:48:53)


DPatrick (18:49:08)
There are 3k+4 integers between k^2 and k^2 + 3k + 3 (inclusive).

magixter (18:48:42)
k=22

samath (18:48:58)


DiscreetFourierTransform (18:49:05)
so 3k + 4 = 70

DPatrick (18:49:25)
Right. We know that 3k+4 = 70, so we get k=22.

DPatrick (18:49:29)
And how do we finish?

magixter (18:49:40)
There fore, (23^3 -1)/22 is the answer

not_trig (18:49:51)
so max(a_i) = k^2+3k+3 = 553

conartist (18:49:52)
plug in k=22 for k^2 + 3k + 3

DPatrick (18:50:21)
To finish the problem, note that we want a_70, the largest value of a, which is k^2 + 3k + 3.

DPatrick (18:50:28)


DPatrick (18:50:54)
Next is the halfway problem, #8:

DPatrick (18:50:59)


DPatrick (18:51:04)
//s3.amazonaws.com/classroom.artofproblemsolving.com/Classroom/cbe6/images/lx-174819774.gif

DPatrick (18:51:13)
I had to read this twice, really carefully, before I understood what was being asked.

DPatrick (18:51:42)
I also had to draw myself a quick sketch to wrap my head around the problem:

DPatrick (18:51:50)


DPatrick (18:51:51)
http://s3.amazonaws.com/classroom.artofproblemsolving.com/Images/Transcripts/53bd679e92b73373b1f7b1189510cdd9.png

Arnizzle (18:52:11)
where does it say that the lines extend from one side of the paper to the opposite?

Arnizzle (18:52:22)
It just says they're parallel to the edges of the paper

DPatrick (18:52:59)
It actually doesn't. I worried about this in real-time when I was solving it, and ultimately decided to ignore this issue.

bubble (18:52:27)
dose the edge of the paper count as a line segment?

DPatrick (18:53:21)
No.

not_trig (18:51:34)
# of rectangles = (a-1)(b-1) if there are a of length 4 and b of length 5

DPatrick (18:54:21)
Right: the number of basic rectangles is the product of the one less than the numbers of lines in each direction.

DPatrick (18:54:47)
For example, in my sketch, I drew 9 lines in each direction, and there are 8*8 = 64 basic rectangles.

DPatrick (18:55:31)
But I found that the calculations are a little simpler if we assign variables so that we have a+1 horizontal lines and b+1 vertical lines.

DPatrick (18:55:40)
This way we get ab rectangles.

DPatrick (18:55:54)
And what does the ""total length 2007"" condition give us?

tjhance_2 (18:56:09)
4(a+1)+5(b+1)=2007 or 4a+5b=1998

Arnizzle (18:56:21)
4(a+1) + 5(b+1) = 2007

not_trig (18:56:27)
4(a-1)+5(b-1)=2007

DPatrick (18:56:35)
4(a+1) + 5(b+1) = 2007, which is 4a+5b = 1998.

DPatrick (18:56:44)
So we need to maximize ab, given that a and b are integers satisfying 4a+5b = 1998.

DPatrick (18:56:54)
How can we do that?

ra5249 (18:56:57)
am-gm

magixter (18:57:08)
The maximum value should be... proportional, to the other side, right?

bubble (18:57:08)
a=b?

ra5249 (18:57:13)
a = b

tjhance_2 (18:57:24)
AM-GM? (a+b)/2 >= sqrt(ab)

DPatrick (18:58:21)
There are some ""intuitive"" or fancy ways (like AM-GM) to do it, but I just did it the lowest-tech way, which is also pretty simple.

hyang (18:57:24)
b=(1998-4a)/5, plug back into equation and find max

DPatrick (18:58:46)
Sure, that's simple and it works!

DPatrick (18:58:51)


DPatrick (18:58:59)
So we need to maximize 1998a - 4a^2.

DPatrick (18:59:17)
The graph of this is a downward-opening parabola with vertex at a = 1998/8 = 249.75

DPatrick (18:59:41)
So we just need to check the two closest integral values of a on either side of 249.75.

hyang (18:59:43)
find the closest integer below and above it and check to see which one is higher

DPatrick (18:59:58)
Yep..what are the values of a we need to check?

p4fn2w (19:00:07)
249, 250?

not_trig (19:00:12)
a=250, a=249... 250 works

guyinPA (19:00:14)
249,250

Theunluckyone (19:00:21)
249 and 250

DPatrick (19:00:49)
Well...remember a and b have to be integers. Going back to 4a+5b=1998, what do we know about a?

DPatrick (19:01:09)
a=249 and a=250 don't make b an integer.

not_trig (19:01:16)
4a=3 mod 5

not_trig (19:01:23)
so a=2 mod 5

DPatrick (19:01:42)
Right. 4a has to equal 1998 (mod 5), so a must be 2 mod 5.

DPatrick (19:01:49)
So the values we need to check are (a,b) = (247,202) and (a,b) = (252,198).

DPatrick (19:02:22)
Now, no calculators! Don't multiply 247*202 and 252*198 the long way!

DPatrick (19:02:31)
247*202 = (250-3)(200+2) = (250)(200) + 500 - 600 - 6 = 50000 - 106.

252*198 = (250+2)(200-2) = (250)(200) - 500 + 400 - 4 = 50000 - 104.

tjhance_2 (19:02:27)
252 is closer to 249.75

DPatrick (19:03:09)
That's true: we already know it'll be 252, since it's closer to the vertex of the parabola.

DPatrick (19:03:19)
And checking both points confirms it.

DPatrick (19:03:40)
So N is 50000-104.

DiscreetFourierTransform (19:03:28)
and the last three digits are 896

not_trig (19:03:46)
so the last 3 digits are 896

DPatrick (19:04:01)


DPatrick (19:04:23)


DPatrick (19:04:26)
//s3.amazonaws.com/classroom.artofproblemsolving.com/Classroom/cbe6/images/lx-95478158.gif

DPatrick (19:04:40)
Obviously, we'll start by sketching a picture.

DPatrick (19:04:47)


DPatrick (19:04:48)
http://s3.amazonaws.com/classroom.artofproblemsolving.com/Images/Transcripts/bafbe518f0e8274e2cb8eed677b6a435.png

DPatrick (19:04:53)
I've filled in all the outside lengths. Let's forget about the circles for just a moment.

DPatrick (19:04:59)
What other lengths do we know?

gighiuhui (19:05:08)
(BE=105)

DiscreetFourierTransform (19:05:12)
EB and DF

sleepsta (19:05:13)
EB, DF

redcomet46 (19:05:17)
BE=105 by 3-4-5 rt triangles

sleepsta (19:05:21)
3-4-5 triangle

DPatrick (19:05:34)
ABE and CDF are 3-4-5 triangles! So BE = DF = 105.

DPatrick (19:05:47)
Now let's add the circles and draw in the radii for the left circle.

DPatrick (19:05:52)


DPatrick (19:05:53)
http://s3.amazonaws.com/classroom.artofproblemsolving.com/Images/Transcripts/bcd972731ca30b17935cec303187eab9.png

DPatrick (19:06:04)
How can we find PQ?

sleepsta (19:06:16)
fine EF and subract EP

redcomet46 (19:06:19)
Get EF and subtract EP and QF (which are equal)

sleepsta (19:06:23)
EF-2EP

DPatrick (19:06:39)
OK, then how do we get EF?

not_trig (19:06:33)
find EP

samath (19:06:50)
tangents to a circle

DPatrick (19:07:01)
Yes, we can chase the lengths around the circle.

DPatrick (19:07:08)
Suppose EP = EX = x.

DPatrick (19:07:33)
Then what length do we know?

p4fn2w (19:07:48)
BE = 105 + x

DPatrick (19:08:31)
Not exactly...BE = 105 and EX = x, so we know...?

jen7 (19:08:49)
BX=105-x

DPatrick (19:08:57)
Right.

DPatrick (19:09:06)
So what else has length 105-x?

DPatrick (19:09:16)
lemme pop up the picture again:

DPatrick (19:09:21)


sleepsta (19:08:58)
BX=BY

redcomet46 (19:09:14)
BY

jen7 (19:09:14)
BY

DPatrick (19:09:53)
Right. BX = BY since they're both tangents from B to the left circle. So BY = BX = 105-x.

sleepsta (19:09:49)
YF=PF=364-(105-X)

DPatrick (19:10:21)
Yep...we keep working our way around the left circle.

DPatrick (19:10:35)
BF = 364 and BY = 105-x, so YF is their difference, which is 259+x.

DPatrick (19:10:40)
So PF = 259+x too.

gighiuhui (19:10:48)
Then FQ=x, hence PQ=259 tricky tricky

DPatrick (19:11:03)
Bingo!

DPatrick (19:11:10)
FQ = x too (by the symmetry of the diagram).

DPatrick (19:11:15)


DPatrick (19:11:34)
All we had to do was chase equal tangent lengths around the circle, and we're done!

DPatrick (19:11:42)
Back to rrusczyk for #10.

rrusczyk (19:11:50)


rrusczyk (19:11:57)
//s3.amazonaws.com/classroom.artofproblemsolving.com/Classroom/cbe6/images/lx-144444286.gif

rrusczyk (19:12:03)
There are quite a few ways to do this problem, some nicer than others. You can look on the message boards for some of the other ways. We'll focus on one of the nicer approaches here.

rrusczyk (19:12:15)
We'll start with the easy step. How many elements are in P?

sleepsta (19:12:08)
oh for this problem is empty set counted?

rrusczyk (19:12:41)
Yes -> the empty set is a set.

gighiuhui (19:12:26)
64=2^6

worthawholebean (19:12:31)
2^6

jen7 (19:12:49)
2^6

rrusczyk (19:12:58)
Since S has 6 elements, it has 2^6 = 64 subsets. Therefore, there are 64 elements in P. So, there are 64^2 = (2^6)^2 = 2^12 ways to choose A and B.

rrusczyk (19:13:06)
Now we have to count the number of ways that B is in either A or S - A.

rrusczyk (19:13:14)
Let's start with the first case: B is in A.

rrusczyk (19:13:23)
In how many ways can we pick two subsets such that B is in A?

tjhance_2 (19:13:40)
if B has n elements there are 2^(6-n) choices for A

bubble (19:13:53)
subcases for the# of elements in b

rrusczyk (19:14:10)
There are several approaches here. We could do grimy casework based on the number of elements in B or on the number of elements in A (I confess, I did the latter, then came up with such a nice answer via the binomial theorem that I knew there had to be a cleaner way to do it).

rrusczyk (19:14:27)
But . . . is there a nicer way to count the number of ways we can pick two subsets such that B is in A?

rrusczyk (19:14:46)
One of my favorite approaches to counting is to try to construct a single example of what we are going to count. Thinking about different ways to do so often leads to a nice solution. Here, we could do the obvious thing: pick A or pick B, then use that to generate the other set. That gives us the two casework approaches above.

rrusczyk (19:15:07)
What if, instead of focusing on A or B, we focus on each element? Take the first element; if B is contained in A, then what are our options for this element?

guyinPA (19:15:35)
it is in a not b , a and b or neither

tjhance_2 (19:15:45)
not in A or B, only in A, or in both

rrusczyk (19:16:04)
We have 3 choices: the element could be in both A and B, it could be in neither, or it could be in A and not B.

rrusczyk (19:16:24)
So. . . How many pairs of sets A and B are there such that B is wholly contained in A?

rrusczyk (19:17:30)
We have three choices for the first element: in both A and B, in neither A nor B, or in A but not B.

rrusczyk (19:17:38)
Is there anything special about the first element?

not_trig (19:17:48)
no

thememan (19:17:49)
i dont think so

worthawholebean (19:17:52)
Nothing special

rrusczyk (19:18:09)
Exactly, so how many pairs of sets are there such that B is wholly in A?

guyinPA (19:17:31)
3^6

tjhance_2 (19:17:33)
3^6

hyang (19:18:45)
3^6

rrusczyk (19:18:53)
There's nothing special about the first element. We have 3 choices for each element when constructing a pair such that B is wholly contained in A, so we have 3^6 ways to form a pair of sets, A and B, such B is wholly contained in A.

rrusczyk (19:19:02)
What about B being in S - A?

worthawholebean (19:19:08)
same thing

tjhance_2 (19:19:22)
3^6 ways for that as well

guyinPA (19:19:22)
it is the same possibility

rrusczyk (19:19:30)
If B is in S - A, then no element of B is in A

rrusczyk (19:19:34)
Again, we have 3 choices for each element: in B but not in A, in A but not in B, or in neither set. So, there 3^6 pairs of sets, A and B, such that B is in S - A.

rrusczyk (19:19:38)
(Note, we could also have found a 1-1 correspondence between the pairs with B in A and the pairs with B in S - A. Specifically, for each pair with B in A, consider A' = S - A. Then, B is in S - A'.)

rrusczyk (19:19:44)
Does this mean there are 2*3^6 pairs of sets A and B such that B is in S - A?

tjhance_2 (19:19:50)
but we overcounted where B is the empty set

rrusczyk (19:20:18)
We have to be careful about overcounting! We have counted the cases where B is the empty set in both 'B is in A' and 'B is in S-A', so we must subtract these once. How many such pairs of sets are there?

Bictor717 (19:20:58)
64

samath (19:21:17)
2^6

rrusczyk (19:21:27)
There are 2^6 ways we can make set A, so there are 2^6 pairs of sets, A and B, in which B is the empty set. So, our total number of acceptable pairs of sets is 2*3^6 - 2^6.

rrusczyk (19:21:44)
Now we're ready to find our probability. What is it?

guyinPA (19:22:05)
(2*3^6-2^6)/2^12

rrusczyk (19:22:54)


worthawholebean (19:22:56)
(2*3^6-2^6)/(2^12)=679/(2^11)

hyang (19:22:58)
(2*3^6-2^6)/2^12

samath (19:23:03)
(3^6-2^5)/2^11=697/2^11, so m+n+r=697+2+11=710

rrusczyk (19:23:21)
You can check out the message board for some of the brute-force solutions.

rrusczyk (19:23:38)
One of them leads to the Binomial expansion of (2+1)^6, which is what led me to this solution.

worthawholebean (19:23:33)
What's the best way to make sure you haven't overcounted?

rrusczyk (19:23:57)
Whenever you do cases, you must think about whether or not the cases are exclusive.

rrusczyk (19:24:08)
One main thing is to think about extremes and special cases.

rrusczyk (19:24:24)
(Null set here, double zero plates in the second solution to #1)

rrusczyk (19:24:37)
And now, over to nsato for problems 11-13.

nsato (19:24:55)


nsato (19:24:58)
//s3.amazonaws.com/classroom.artofproblemsolving.com/Classroom/cbe6/images/lx-130300974.gif

nsato (19:25:15)
What shall we do first?

hyang (19:25:17)
draw a diagram

ra5249 (19:25:22)
diagram

sleepsta (19:25:24)
picutre

nsato (19:25:51)
First, we shall draw a nice diagram.

nsato (19:25:57)


nsato (19:25:59)
http://s3.amazonaws.com/classroom.artofproblemsolving.com/Images/Transcripts/14435126167c3505d25eabacc186f261.png

nsato (19:26:08)
We have taken a cross-section as the larger tube rolls over the smaller tube. Point O_1 represents the center of the small tube, and points O_2 and O_3 represent the center of the larger tube, at the start and end of the roll, respectively. Points A, B, C, D, and E are points of tangency.

nsato (19:26:20)
Since the larger tube completes a revolution, it would probably help to compute the angle between O_1 O_2 and O_1 O_3.

nsato (19:26:37)
Let's start with what we know in the diagram. We have two circles centered at O_1 and O_2, and their common external tangent AB. How can we compute the length of AB?

sleepsta (19:27:02)
draw line from O1 perpendicular to radius of O2

nsato (19:27:21)
Let P be the projection of O_1 onto AO_2.

nsato (19:27:27)


nsato (19:27:29)
http://s3.amazonaws.com/classroom.artofproblemsolving.com/Images/Transcripts/f79a78bc68d92e6b6b0086185f766101.png

nsato (19:27:43)
This gives us triangle O_1 P O_2 to work with. Note that angle O_1 P O_2 is right. What are the dimensions of triangle O_1 P O_2?

not_trig (19:27:43)
well, O_1O_2=72+24=96; O_2P=72-24=48

Someone (19:27:58)
x,48,96

nsato (19:28:11)
We see that

nsato (19:28:15)


nsato (19:28:18)
and

nsato (19:28:22)


Someone (19:27:10)
well you know it has two right angles and you know 3 side lengths on the trap,. so set up pythag

hyang (19:27:13)
use pythagorean

nsato (19:28:45)
Therefore, by Pythagoras,

nsato (19:28:54)


bubble (19:28:50)
30-60-90 triangle

sleepsta (19:28:58)
not only is right triangle its 30-60-90

nsato (19:29:21)
You're right, that would make this part faster.

nsato (19:29:54)
So we see that angle PO_1 O_2 is 30 degrees.

nsato (19:30:01)
So what is the angle between O_1 O_2 and O_1 O_3?

Theunluckyone (19:30:10)
120

worthawholebean (19:30:11)
120?

not_trig (19:30:15)
120

nsato (19:30:31)
This angle is 120 degrees.

nsato (19:30:38)
Now, the larger tube rolls over the smaller tube without slipping, which means the roll takes up the same amount of arc length on the surface of each tube.

nsato (19:30:46)
What is the arc length DE?

sleepsta (19:31:07)
1/3*2pi * r=16pi

bubble (19:31:21)
120 is 1/3 of circomfernce or 16pi

tjhance_2 (19:31:27)
(1/3)*2*24pi=16pi

nsato (19:31:52)
120 degrees is 2 pi/3 in radians, so the arc length is

nsato (19:31:57)


nsato (19:32:02)
So what is the corresponding angle in the larger tube, for this arc length?

Theunluckyone (19:32:14)
40

guyinPA (19:32:26)
40

worthawholebean (19:32:40)
144?/16?*360=40?

nsato (19:32:58)


nsato (19:33:16)
What is AC?.

sleepsta (19:29:45)
AC=96rt(3), so find out how much of circumference was lost in this roll

Theunluckyone (19:33:46)
96root3

nsato (19:34:03)
We know that AC = 96 * sqrt(3).

nsato (19:34:22)
So we must compute the total angle the roll ""costs"", when the larger tube rolls over the smaller tube, as compare to the full revolution.

nsato (19:34:29)
When the roll starts, the larger tube touches the flat surface at A. What is angle AO_2 D?

nsato (19:34:36)


nsato (19:34:38)
http://s3.amazonaws.com/classroom.artofproblemsolving.com/Images/Transcripts/baf78decb6d075293b3c43c43f0364ef.png

not_trig (19:34:43)
60

Bictor717 (19:34:47)
pi/3

worthawholebean (19:34:56)
60?

nsato (19:35:03)
It is not hard to see that angle AO_2 D is 60 degrees, or pi/3.

nsato (19:35:11)
Therefore, by the time the roll over the smaller tube finishes, point A is at an angle of pi/3 + pi/3 + 2pi/9 = 8pi/9 from point C, measured along the arc length.

sleepsta (19:34:15)
60+40+60=160 degrees is used up

nsato (19:35:27)
This means there is still 2pi - 8pi/9 = 10pi/9 left in the complete revolution. What is the length of this arc length?

bubble (19:35:54)
80pi

worthawholebean (19:35:59)
10?/9*72=80?

sleepsta (19:36:15)
144pi-64pi=80pi

nsato (19:36:21)


nsato (19:36:24)
So what is the distance the larger tube covers?

guyinPA (19:36:33)
total dist is 80pi+96*squrt3

sleepsta (19:36:43)
80pi+96rt(3)

worthawholebean (19:36:43)
$80?+96\sqrt{3}$

nsato (19:36:55)


sleepsta (19:36:59)
80+96+3=179

nsato (19:37:10)


nsato (19:37:26)


nsato (19:37:32)
//s3.amazonaws.com/classroom.artofproblemsolving.com/Classroom/cbe6/images/lx-169710878.gif

nsato (19:37:43)


nsato (19:37:54)
What is the first sum in the problem?

worthawholebean (19:38:15)
a+a+b+a+2b+...+a+7b

worthawholebean (19:38:33)
a+a+b+a+2b+...+a+7b=8a+28=308

nsato (19:38:44)


nsato (19:39:03)
Dividing both sides by 4, we get 2a + 7b = 77.

nsato (19:39:18)
The second sum in the problem is

nsato (19:39:26)


nsato (19:39:48)
It's tempting to try to sum S using the formula for a geometric sequence, but it will be easier (for now) to just leave it in this form.

nsato (19:39:52)
What do we know about S?

nsato (19:40:49)
We know that

nsato (19:40:55)


Bictor717 (19:40:48)
S is between 3^56 and 3^57

nsato (19:41:05)
Equivalently,

nsato (19:41:09)


nsato (19:41:20)
So, we need to squeeze S between two powers of 3.

nsato (19:41:25)
Looking at the expression for S, what power of 3 is S greater than?

worthawholebean (19:40:32)
S>3^(a+7b)

guyinPA (19:41:48)
3^a+7b

nsato (19:41:57)
Clearly,

nsato (19:42:01)


nsato (19:42:11)
Now if we could show that S is less than 3^{a + 7b + 1}, then we would be done.

nsato (19:42:18)
Note that

nsato (19:42:22)


nsato (19:42:38)
There are several ways of proving this bound. One way is to fill in every power of 3 up to 3^{7b}:

nsato (19:42:47)


nsato (19:42:54)
What is this last sum equal to?

not_trig (19:43:28)
this sum = (3^(7b+1)-1)/2

nsato (19:43:43)
From the formula for a geometric series,

nsato (19:43:46)


nsato (19:43:55)
This proves that the bound is true.

nsato (19:44:03)
We conclude that

nsato (19:44:12)


tjhance_2 (19:40:16)
3^(a+7b)<S<3^(a+7b+1)

not_trig (19:41:43)


nsato (19:44:25)
But

nsato (19:44:31)


not_trig (19:44:26)
so a+7b=56?

nsato (19:44:56)
Hence, a + 7b = 56, so a = 56 - 7b.

nsato (19:45:07)
Substituting into the above equation, we get 2(56 - 7b) + 7b = 77.

nsato (19:45:15)
Solving, we get b = 5, so a = 56 - 7*5 = 21.

nsato (19:45:36)


samath (19:45:42)
91

nsato (19:45:59)


nsato (19:46:16)


nsato (19:46:28)
//s3.amazonaws.com/classroom.artofproblemsolving.com/Classroom/cbe6/images/lx-164312735.gif

nsato (19:46:35)


nsato (19:46:37)
http://s3.amazonaws.com/classroom.artofproblemsolving.com/Images/Transcripts/2f2f7f6d80933d3a6f5d0f74185042a9.png

nsato (19:46:42)
To make things easier, let's consider a simpler case. Suppose that we had a triangular array with 4 squares at the bottom, and the values in them were a, b, c, d. What number would be in the square at the top?

worthawholebean (19:46:57)
a+3b+3c+d

not_trig (19:47:03)
a+3b+3c+d

tjhance_2 (19:47:08)
a+3b+3c+d

nsato (19:47:21)
The entries in the rows would be:

nsato (19:47:23)


nsato (19:47:33)
So the number at the top is a + 3b + 3c + d. Does this remind us of anything?

ra5249_2 (19:47:36)
looks like pascal's triangle! =)

worthawholebean (19:47:37)
Pascal's triangle

not_trig (19:47:39)
binomial coefficients

tjhance_2 (19:47:45)
Triangle of Pascal

guyinPA (19:47:54)
pascal triangle

nsato (19:48:00)
It looks like the coefficients in Pascal's triangle. This shouldn't be too surprising, as we have a triangular array that is constructed in a similar way.

nsato (19:48:06)
It is not hard to prove that we always obtain the coefficients in Pascal's triangle. This can be proven either using induction or a block-walking argument, and we leave the details to the reader.

nsato (19:48:21)
So if the numbers in the bottom row are x_1, x_2, ..., x_{11}, what is the number in the top square?

not_trig (19:46:56)
we see binomial coefficients: for k rows, the top square is the sum of the binomial coefficients, in order, of (a+b)^(k-1)

nsato (19:48:50)
The number at the top would be

nsato (19:48:53)


nsato (19:48:59)
What do we want to do with this number?

not_trig (19:49:02)


tjhance_2 (19:49:05)
mod 3

bubble (19:49:14)
find that # mod 3

worthawholebean (19:49:16)
Modulo 3 it is congruent to 0

nsato (19:49:26)
We want to see when it is divisible by 3, so we take the coefficients modulo 3.

nsato (19:49:33)
What do we get?

worthawholebean (19:49:44)
x_1+x_2+x_10+x_11

tjhance_2 (19:49:50)
1, 1, 0, 0, 0, 0, 0, 0 , 0, 1, 1

nsato (19:50:13)
We can either compute them by hand, or count the number of factors of 3 in each binomial coefficient. Either way, the expression reduces to

nsato (19:50:18)


not_trig (19:50:13)
so it is equivalent to x_1+x_2+x_10+x_11

nsato (19:50:27)
When is this divisible by 3?

worthawholebean (19:50:44)
When three are 1 or none are 1

tjhance_2 (19:50:52)
if three of x_1, x_2, x_10, and x_11 are 0, or if they are all 0

bubble (19:50:57)
when 0 or 3 of them are 1

not_trig (19:50:42)
when three are 1 mod 3 or all are 0 mod 3

nsato (19:51:17)
Since each x_i is 0 or 1, the sum must be either 0 or 3. There is only one way that the sum can be 0 (each of x_1, x_2, x_{10}, x_{11} is 0), and there are four ways the sum can be 3 (one of x_1, x_2, x_{10}, x_{11} is 0 and the other three are 1), for a total of five ways for these four variables.

nsato (19:51:33)
That leaves 7 variables. What about them?

bubble (19:52:04)
they can be anything

not_trig (19:51:40)
2^7 ways

worthawholebean (19:51:44)
2^7 ways for the other 7; they don't matter

redcomet46_2 (19:51:59)
they can either be 1 or 0 so there are 2^7 ways for them

not_trig (19:52:07)
2^7 ways: 0 or 1 for each

nsato (19:52:30)
Since they do not appear in this expression, each of the remaining 7 variables can be 0 or 1.

guyinPA (19:51:42)
2^7*5

nsato (19:52:42)
Therefore, the total number of initial distributions for which the number in the top square is divisible by 3 is

nsato (19:52:44)


nsato (19:53:00)
Now, the lovely and talented Valentin Vornicu will take up the last two problems.

Valentin Vornicu (19:53:26)
Hi all. Thanks Naoki :)

Valentin Vornicu (19:53:37)
Problem 14

Valentin Vornicu (19:53:48)


Valentin Vornicu (19:54:09)
How can we start thinking on this problem?

calc rulz (19:54:25)
Plug in values for x.

worthawholebean (19:54:36)
Plug some stuff in

Valentin Vornicu (19:54:55)
That's an idea. Or ... we might start with looking at some of the coefficients of f. For example, what is the constant term of f?

calc rulz (19:55:05)
1

p4fn2w (19:55:06)
1?

worthawholebean (19:55:06)
1

ra5249_2 (19:55:10)
we know the constant term is 1

Valentin Vornicu (19:55:35)
Since f(0)=1, the constant term is 1 given to us directly in the problem. What about the leading coefficient?

tjhance_2 (19:55:20)
1

Bictor717 (19:55:20)
1

rnwang2 (19:55:33)
1

Valentin Vornicu (19:55:51)


Valentin Vornicu (19:56:07)
What?s next?

worthawholebean (19:56:43)
Search for the middle coefficients.

Valentin Vornicu (19:56:51)


Valentin Vornicu (19:57:07)


Valentin Vornicu (19:57:43)
However, this is just a trick, and we didn't actually solve the problem (we didn't find all solutions for f). If this were an USAMO #2 or #4, we wouldn't have gotten much credit (if any!) on the work up to now.

Valentin Vornicu (19:58:06)
What else can we think about when we look at (*) besides coefficients of f?

worthawholebean (19:58:19)
Roots

rnwang2 (19:58:22)
roots

Valentin Vornicu (19:58:36)
We can think about f's roots. The relation (*) gives us a connection points between some of the roots of f. Let's start with possible real roots of f. If x_0 is a real root of f, what other roots can be derived from it?

worthawholebean (19:58:33)
If x or 2x^2 is a root then 2x^3+x is

Valentin Vornicu (19:58:49)


worthawholebean (19:59:21)
Greater if x_0 is positive, less than otherwise

Valentin Vornicu (19:59:43)


Valentin Vornicu (20:00:04)


worthawholebean (20:00:24)
Same as x_0 conpared to x_1

not_trig (20:00:30)
same as x_1 compared to x_0

Valentin Vornicu (20:01:04)


calc rulz (20:01:02)
How did you get that +1?

Valentin Vornicu (20:01:27)
Oh, small typo. It's supposed to be x_1 :)

calc rulz (19:59:46)
Well there are finitely many roots so eventually it occilates

Valentin Vornicu (20:01:52)


not_trig (20:01:59)
0

calc rulz (20:02:01)
0

Valentin Vornicu (20:02:10)


Valentin Vornicu (20:02:36)


Valentin Vornicu (20:03:05)


Valentin Vornicu (20:04:03)


Valentin Vornicu (20:05:37)


not_trig (20:06:04)
... infinite descent again?

calc rulz (20:06:17)
We keep going an find infinitely many roots so it's not greater than 1

Valentin Vornicu (20:06:27)


Valentin Vornicu (20:06:48)


not_trig (20:07:33)
no?

Valentin Vornicu (20:07:51)


calc rulz (20:07:36)
I'm thinking we do a similar thing and the absolute values go down, and with a similar arguement, we have infinitely many roots and it can't

Valentin Vornicu (20:08:20)
That will not work in this case, so we have to use Vieta's.

Valentin Vornicu (20:08:31)
Can we now determine which are the roots of f?

guyinPA (20:08:40)
yes

Valentin Vornicu (20:09:16)


calc rulz (20:09:46)
2z^3+z has absolute value 1

Valentin Vornicu (20:09:56)


Valentin Vornicu (20:10:46)


worthawholebean (20:11:59)
When the angles are the same for the two numbers.

Valentin Vornicu (20:12:11)


Valentin Vornicu (20:12:51)
What can we do with this information about f's roots?

rnwang2 (20:13:15)
(x-i)(x+i) is a factor

Valentin Vornicu (20:13:22)


calc rulz (20:14:07)
well k=n-k because roots must come in conjugate pairs

Bictor717 (20:14:10)
It's n/2

Valentin Vornicu (20:15:02)


Valentin Vornicu (20:15:11)
What now?

not_trig (20:15:33)
k=1 doesn't work; k=2 does

Valentin Vornicu (20:15:47)


Valentin Vornicu (20:16:16)


Valentin Vornicu (20:16:43)


Valentin Vornicu (20:17:11)
Now of course, all these tricks are not solving the problem, so if this problem was an USAMO #2 or #4 (which it actually looks more like) we wouldn't have gotten too many steps into the solution using them, but we might have gotten an idea of how to solve the problem (or at least what to expect as a solution).

Valentin Vornicu (20:17:54)
It's our general opinion here at AoPS that this problem was ""wasted"" on the AIME, because from a hard problem it was transformed in a guess around problem which many easily solved.

Valentin Vornicu (20:18:07)
Problem 15

Valentin Vornicu (20:18:14)


p4fn2w (20:18:54)
first step is diagram?

Valentin Vornicu (20:19:04)


Valentin Vornicu (20:19:21)


Valentin Vornicu (20:19:24)
http://s3.amazonaws.com/classroom.artofproblemsolving.com/Images/Transcripts/03123648f2df5fcabcb331578fe5ec70.png

Valentin Vornicu (20:19:32)
Now what?

Valentin Vornicu (20:20:18)
We could start computing angles and lengths but it will be very tedious and we might not solve it in a useful time-frame. So we start gathering data about our 4 new points. What is the distance between O and O_A (in terms of x)?

Valentin Vornicu (20:21:08)
Again for those who havent' read my previous paragraph, we denoted with x the radius of the 4 circles.

worthawholebean (20:20:30)
2x

Bictor717 (20:20:37)
2x

not_trig (20:20:49)
2x

p4fn2w (20:20:52)
2x

Valentin Vornicu (20:21:22)
Because the circles are tangent, the distance is 2x. Same for OO_B and OO_C. What does that say about O?

p4fn2w (20:21:43)
it is the center of another circle?

not_trig (20:21:45)
circumcenter of triangle O_A O_B O_C

Valentin Vornicu (20:21:56)


not_trig (20:22:05)
it's similar to the original

Valentin Vornicu (20:22:19)


Valentin Vornicu (20:22:36)


Valentin Vornicu (20:22:37)
http://s3.amazonaws.com/classroom.artofproblemsolving.com/Images/Transcripts/3166a680474e887f8d179ecdd793a846.png

Valentin Vornicu (20:23:01)
What can we see from the diagram?

not_trig (20:23:19)
O_BO_C = PQ, and O_BO_C || BC

Valentin Vornicu (20:23:28)
Why?

not_trig (20:23:36)
rectangle

Valentin Vornicu (20:23:47)


not_trig (20:24:07)
they share an incenter?

Valentin Vornicu (20:24:38)


Valentin Vornicu (20:25:27)


Valentin Vornicu (20:25:42)
Hmm, the LaTeX doesn't get parsed for some reason.

Valentin Vornicu (20:26:22)
So, the answer is Yes, they share an incenter. Furthermore we notice that since AO_A, BO_B and CO_C meet in I, the triangles ABC and O_AO_BO_C are more than similar: they are homothetic.

Valentin Vornicu (20:26:38)


Valentin Vornicu (20:27:00)
The homothety is centered in I, and is of ratio k. How can we determine k?

Valentin Vornicu (20:27:35)


samath (20:23:36)
O_BO_B is parallel to BC

ra5249_2 (20:23:46)
parallelogram

not_trig (20:25:20)
find O_BO_C / BC

PI-Dimension_2 (20:25:53)
33 people and one person talking O.o

p4fn2w (20:26:45)
ratio is (OB)/(O O_B)?

not_trig (20:27:21)
find O_BO_C/BC

Valentin Vornicu (20:30:19)
Ok, sorry about that - my Java computer shut down on its own.

Valentin Vornicu (20:30:23)
So where were we ...

Valentin Vornicu (20:30:28)


Valentin Vornicu (20:30:52)


Valentin Vornicu (20:30:59)


not_trig (20:30:52)
similar triangles?

Valentin Vornicu (20:31:07)
http://s3.amazonaws.com/classroom.artofproblemsolving.com/Images/Transcripts/3bab342d082604c7ae46c9a198b01d80.png

Valentin Vornicu (20:31:12)
How much is ID?

Valentin Vornicu (20:31:56)


not_trig (20:31:59)
ID = 84/(13+14+15)*2

not_trig (20:32:15)
so ID = 84/21 = 4

Valentin Vornicu (20:32:23)


Valentin Vornicu (20:33:15)


not_trig (20:33:32)
84=13*14*15/4R

Valentin Vornicu (20:34:44)


Valentin Vornicu (20:35:11)
Well, this concludes this year's AIME MathJams series.