rrusczyk (Apr 7, 2004 7:04:38 PM)
1. A chord of a circle is perpendicular to a radius at the midpoint of the radius. The ratio of the area of the larger of the two regions into which the chord divides the circle to the smaller can be expressed in the form [a*pi + b*sqrt(c)]/[d*pi - e*sqrt(f)], where a, b, c, d, e, and f are positive integers, a and e are relatively prime, and neither c nor f is divisible by the square of any prime. Find the remainder when the product a*b*c*d*e*f is divided by 1000.

rrusczyk (Apr 7, 2004 7:04:44 PM)
//s3.amazonaws.com/classroom.artofproblemsolving.com/Classes/AIME/Images/2004aimeB1que.gif

rrusczyk (Apr 7, 2004 7:05:04 PM)
Basically we're looking for the area on the left of CD versus the area on the right.

rrusczyk (Apr 7, 2004 7:05:08 PM)
Where do we start?

interesting_move (Apr 7, 2004 7:05:29 PM)
Assign an arbitrary value to the radius of the circle.

rrusczyk (Apr 7, 2004 7:05:39 PM)
We don't have any lengths; we're looking for a ratio. Thus, we can just let AB = 2. (We pick 2 rather than 1 since we know we have to bisect AB.)

hypercube (Apr 7, 2004 7:05:47 PM)
and assign 2 as the radius

justdudxit (Apr 7, 2004 7:05:49 PM)
figure out the central angle

Guest (Apr 7, 2004 7:06:01 PM)
When we draw it out, where the chord meets the circle, we draw radius to that point and we get a 30,60,90

justdudxit (Apr 7, 2004 7:06:04 PM)
the angle is 120

Rep123max (Apr 7, 2004 7:06:12 PM)
This will form two triangle each with a hypotenuse of r, and leg of r/2, meaning that the other leg is r rt3/2 which is a 30-60-90 triangle

rrusczyk (Apr 7, 2004 7:06:31 PM)
We know that AMD is a right triangle, and that AM = AD/2, so it is a 30-60-90 triangle and thus angle CAD = 120 degrees. Hence, sector DAC is 1/3 of the circle, or 4pi/3.

rrusczyk (Apr 7, 2004 7:06:47 PM)
Why does this help? What do we do next?

random%0 (Apr 7, 2004 7:07:12 PM)
find the area of the triangle created by the two radii and the chord

justdudxit (Apr 7, 2004 7:07:16 PM)
subtract out the triangle to find the area of the segment

no_one_2000 (Apr 7, 2004 7:07:24 PM)
We subtract out triangle ADC to get the arc sector

rrusczyk (Apr 7, 2004 7:07:38 PM)
What is the area of triangle ADC?

random%0 (Apr 7, 2004 7:07:58 PM)
altitude to the chord is 1, the chord is 2root3

interesting_move (Apr 7, 2004 7:08:03 PM)
2(1/2)(1)(sqrt(3))

Hexahedron (Apr 7, 2004 7:08:06 PM)
Area ADC=sqrt3

random%0 (Apr 7, 2004 7:08:09 PM)
area is root3

rrusczyk (Apr 7, 2004 7:08:14 PM)
AM = 1, DC = 2sqrt(3), so the area of ADC = (AM)(DC)/2 = sqrt(3); hence the area to the right of CD is 4pi/3 - sqrt(3).

rrusczyk (Apr 7, 2004 7:08:25 PM)
What about the area to the left of CD?

rrusczyk (Apr 7, 2004 7:08:43 PM)
(Explain where you get your answer)

timhlu (Apr 7, 2004 7:08:48 PM)
4pi - the area to the right

no_one_2000 (Apr 7, 2004 7:08:50 PM)
The area of the circle minus 4pi/3 - sqrt(3)

MarkSmith888 (Apr 7, 2004 7:08:53 PM)
4pi minus area of ADC

Hexahedron (Apr 7, 2004 7:09:09 PM)
4pi-4pi/3+sqrt 3 because total area is 4pi

rrusczyk (Apr 7, 2004 7:09:13 PM)
The area to the left of CD is 4pi - (area to the right of CD) = 8pi/3 + sqrt(3). We put these two pieces together to get our ratio:

rrusczyk (Apr 7, 2004 7:09:17 PM)
(8pi/3 + sqrt(3)) / (4pi/3 - sqrt(3)) = (8pi + 3sqrt(3)) / (4pi - 3sqrt(3))

rrusczyk (Apr 7, 2004 7:09:21 PM)
When we go back and answer the question, we get 592.

rrusczyk (Apr 7, 2004 7:10:15 PM)
2. A jar has 10 red candies and 10 blue candies. Terry picks two candies at random, then Mary picks two of the remaining candies at random. Given that the probability that they get the same color combination, irrespective of order, is m/n, where m and n are relatively prime positive integers, find m + n.

rrusczyk (Apr 7, 2004 7:10:19 PM)
(This is #2)

rrusczyk (Apr 7, 2004 7:10:40 PM)
There are a lot of ways to take care of this one. What cases can we consider?

codeblue87 (Apr 7, 2004 7:11:01 PM)
either both red or both blue, and red or blue

whitesnowflakes (Apr 7, 2004 7:11:03 PM)
bb, br, rr

rachel (Apr 7, 2004 7:11:05 PM)
The possibilities for getting the same combination of colors are RR, BB, and all combos of Terry getting 1R+1B and Mary also

random%0 (Apr 7, 2004 7:11:09 PM)
they both pick the same color or they both pick one of each

rrusczyk (Apr 7, 2004 7:11:11 PM)
We can consider the cases where they both get the 2 of the same color (and the same color each) or where the both get 1 of each.

rrusczyk (Apr 7, 2004 7:11:16 PM)
What is the probability they both get 2 of the same color?

rrusczyk (Apr 7, 2004 7:11:24 PM)
(Give a full explanation)

random%0 (Apr 7, 2004 7:12:35 PM)
(9*8*7)/(19*18*17) for the same color possibility

whitesnowflakes (Apr 7, 2004 7:12:38 PM)
10x9x8x7x2/(20x19x18x17), because there are two colors, 10 total. also, it starts out as 20 marbles, but each time one is taken off

rachel (Apr 7, 2004 7:12:48 PM)
10/20 * 9/19 * 8/18 * 7/17 all *2 for RR or BB

rrusczyk (Apr 7, 2004 7:12:58 PM)
There are 4 candies chosen total out of the 20, and if they are all the same, then we have both people getting the same combo. There are 2C(10,4) ways we can pull out 4 candies of the same color, so the probability each gets 2 of the same color (and each has the same color) is: 2C(10,4)/C(20,4), since there are C(20,4) ways we can choose the 4 candies that the kids will receive.

rrusczyk (Apr 7, 2004 7:13:13 PM)
What is the probability they each get one of each color?

rrusczyk (Apr 7, 2004 7:15:10 PM)
I see a lot of totally different approaches to this half.

rrusczyk (Apr 7, 2004 7:15:25 PM)
Let's walk through the one that looks the most like our first approach.

rrusczyk (Apr 7, 2004 7:15:44 PM)
How many ways can we choose 2 candies of each color to be the 4 we give out?

rrusczyk (Apr 7, 2004 7:15:59 PM)
(Disregard dividing them up among Terry and Mary for now)

jelyman (Apr 7, 2004 7:16:12 PM)
10C2 * 10C2

MithsApprentice (Apr 7, 2004 7:16:16 PM)
C(10,2)^2

mathclass (Apr 7, 2004 7:16:18 PM)
C(10,2)*C(10,2)

rrusczyk (Apr 7, 2004 7:16:37 PM)
Right. There are C(10,2) ways to choose the 2 of each color.

rrusczyk (Apr 7, 2004 7:17:04 PM)
What portion of the ways we apportion these 4 candies between the two student will result in each getting one of each color?

rrusczyk (Apr 7, 2004 7:18:53 PM)
Call the candies BBRR, how many ways can we pick 2 to give to Mary?

jelyman (Apr 7, 2004 7:19:13 PM)
4C2

MithsApprentice (Apr 7, 2004 7:19:24 PM)
C(4,2)

mathclass (Apr 7, 2004 7:19:25 PM)
4C2

rrusczyk (Apr 7, 2004 7:19:40 PM)
OK. How many result in each person gets 1 of each?

jelyman (Apr 7, 2004 7:19:44 PM)
2C1 * 2C1 gives one of each though

vtskier765 (Apr 7, 2004 7:19:46 PM)
RB RB, RB BR, BR BR, or BR RB --> there are 4 ways to choose the candies so that each person gets 1 of each color

rrusczyk (Apr 7, 2004 7:19:55 PM)
Right, so our portion is:

rachel (Apr 7, 2004 7:19:59 PM)
2/3

rrusczyk (Apr 7, 2004 7:20:13 PM)
Hence, the probability they each get one of each color is:

rrusczyk (Apr 7, 2004 7:20:16 PM)
(2/3)[C(10,2) * C(10,2)) / (C(20,4))]

rrusczyk (Apr 7, 2004 7:20:25 PM)
A quick way to get here is :

beta (Apr 7, 2004 7:20:29 PM)
the probability that one person pick one of each color is 10/19, the probability the other person pick one of each is (9/17) total is 10(9)/19(17)

rrusczyk (Apr 7, 2004 7:20:48 PM)
So, what do we have to do to get our answer?

jelyman (Apr 7, 2004 7:21:06 PM)
add

Hexahedron (Apr 7, 2004 7:21:08 PM)
add the probabilities

mathclass (Apr 7, 2004 7:21:15 PM)
add the two different probabilities, the rr/bb one and rb

rrusczyk (Apr 7, 2004 7:21:20 PM)
We add 'em up and what do we get?

whitesnowflakes (Apr 7, 2004 7:21:45 PM)
118/323

Hexahedron (Apr 7, 2004 7:21:51 PM)
118/323

rrusczyk (Apr 7, 2004 7:21:54 PM)
2C(10,4)/C(20,4) + (2/3)[C(10,2) * C(10,2)) / (C(20,4))] = 118/323.

rrusczyk (Apr 7, 2004 7:21:58 PM)
Note: There are plenty of other ways to work through the casework that are essentially equivalent to this one.

rrusczyk (Apr 7, 2004 7:22:17 PM)
This is a problem I would do 2 or 3 different ways if I were taking the test for real to make sure I didn't make a careless counting error.

MCrawford (Apr 7, 2004 7:22:43 PM)
3. A solid rectangular block is formed by gluing together N congruent 1-cm cubes face to face. When the block is viewed so that three of its faces are visible, exactly 231 of the 1-cm cubes cannot be seen. Find the smallest possible value of N.

MCrawford (Apr 7, 2004 7:22:50 PM)
//s3.amazonaws.com/classroom.artofproblemsolving.com/Classes/AIME/Images/2004aimeB3Nblock.gif

MCrawford (Apr 7, 2004 7:23:02 PM)
First, how do we make this word problem into a math problem?

Fierytycoon (Apr 7, 2004 7:23:36 PM)
let x,y,z be the sides of the block

justdudxit (Apr 7, 2004 7:23:43 PM)
Let the dimensions be a b c. (a-1)(b-1)(c-1) = 231 = 3*7*11

probability1.01 (Apr 7, 2004 7:23:56 PM)
Well there's sort of a 1-cube layer around the 231 blocks

MCrawford (Apr 7, 2004 7:24:00 PM)
We need some equations to work with. What we know is that 231 of the 1-cm cubes cannot be seen. If we call the number of blocks along each side a, b, and c then we can also expression the number of unseen small cubes as (a - 1)(b - 1)(c - 1) which gives us the equation (a - 1)(b - 1)(c - 1) = 231. Now that we have an equation, what can we do with it?

mathclass (Apr 7, 2004 7:24:19 PM)
factor 231

MithsApprentice (Apr 7, 2004 7:24:25 PM)
we can find factors of 231, add 1 to each, and multiply

xirtamax (Apr 7, 2004 7:24:29 PM)
231 = 3 * 7 * 11

MCrawford (Apr 7, 2004 7:24:39 PM)
It's important to keep an eye on our goal. We are trying to minimize N = abc.

MCrawford (Apr 7, 2004 7:25:03 PM)
There is more than one way to choose a - 1, b - 1, and c - 1 to have a product of 231.

random%0 (Apr 7, 2004 7:25:43 PM)
pretty easy to see that grouping the factors, like 21*11*1, and then 22*12*2, will have more visible blocks, for a higher N

MCrawford (Apr 7, 2004 7:25:57 PM)
While this is true, we can make our argument more rigorous.

justdudxit (Apr 7, 2004 7:26:07 PM)
but we want the way to minimize the product, so a b c have to be as close together as possible

Fountainhead (Apr 7, 2004 7:26:09 PM)
pick the three dimensions that are closest to a cube

MCrawford (Apr 7, 2004 7:26:12 PM)
Why?

justdudxit (Apr 7, 2004 7:26:25 PM)
AM-GM

xirtamax (Apr 7, 2004 7:26:28 PM)
calculus

MCrawford (Apr 7, 2004 7:26:39 PM)
We are dealing with discreet quantities here.

MCrawford (Apr 7, 2004 7:26:54 PM)
We can't just AM-GM it or apply calculus.

MCrawford (Apr 7, 2004 7:27:13 PM)
What information can we apply?

probability1.01 (Apr 7, 2004 7:27:51 PM)
(a+1)(b+1)(c+1) = abc + ab + bc + ac + a + b + c + 1 = 231 + ab + bc + ac + a + b + c + 1, and if we use a factor of 1, there must be an additional 231 term. However, we already see that for 3, 7, and 11 it is less than 231 + 231 + 1

MCrawford (Apr 7, 2004 7:28:08 PM)
Very nice!

MCrawford (Apr 7, 2004 7:28:15 PM)
I did something slightly different.

MCrawford (Apr 7, 2004 7:28:31 PM)
We are trying to minimize abc

MCrawford (Apr 7, 2004 7:29:02 PM)
This is the same as trying to minimize abc/231 and multiply that by 231.

MCrawford (Apr 7, 2004 7:29:11 PM)
This means that we are trying to minimize abc/(a - 1)(b - 1)(c - 1) = [a/(a - 1)][b/(b - 1)][c/(c - 1)].

MCrawford (Apr 7, 2004 7:29:25 PM)
a/(a - 1) = 1 + 1/(a - 1).

MCrawford (Apr 7, 2004 7:29:41 PM)
We want these quantities to be as small as possible when we take the product.

MCrawford (Apr 7, 2004 7:30:22 PM)
If we spread out the product of (a - 1), (b - 1), and (c - 1) then we get smaller factors to multiply by 231.

MithsApprentice (Apr 7, 2004 7:30:31 PM)
(3+1)(7+1)(11+1)=4*8*12=384

MCrawford (Apr 7, 2004 7:30:42 PM)
384 is our final answer.

MCrawford (Apr 7, 2004 7:30:45 PM)
Any questions?

MarkSmith888 (Apr 7, 2004 7:30:57 PM)
But then, wouldn't you have overcounted some of the cubes around the edges, the ones that are shared by more than one face?

MCrawford (Apr 7, 2004 7:31:01 PM)
No.

MCrawford (Apr 7, 2004 7:31:30 PM)
(a - 1)(b - 1)(c - 1) is a great way to count those not seen because those not seen form a block of dimensions a - 1, b - 1, and c - 1.

MCrawford (Apr 7, 2004 7:31:49 PM)
4. How many positive integers less than 10,000 have at most two different digits?

MCrawford (Apr 7, 2004 7:31:56 PM)
How can we go about counting the possibilities?

no_one_2000 (Apr 7, 2004 7:32:31 PM)
I'd start by individually considering groups of numbers based on the number of digits they have; numbers with 1 digit, 2 digits, 3 digits, and 4 digits.

justdudxit (Apr 7, 2004 7:32:41 PM)
organize by the number of digits

MCrawford (Apr 7, 2004 7:32:51 PM)
There are several ways we could go about the casework. I personally think it's easiest to first count the number of integers with just 1 digit and then count those with 2 distinct digits. How many that contain only 1 digit?

MCrawford (Apr 7, 2004 7:33:21 PM)
By 1 digit I mean 1 distinct digit, no matter how many total digits the number has.

mathclass (Apr 7, 2004 7:33:26 PM)
9*4

peaceout (Apr 7, 2004 7:33:28 PM)
9+9+9+9=36

MCrawford (Apr 7, 2004 7:33:40 PM)
We have 9 choices for the 1 digit and each of these can make 1, 2, 3, or 4 digit numbers, so we have 36 total positive integers less than 10000 with 1 distinct digit. How can we set up our count of those integers with 2 distinct digits?

random%0 (Apr 7, 2004 7:34:20 PM)
obviously not 1-digit integers, so 2, 3, and 4

MCrawford (Apr 7, 2004 7:34:29 PM)
In how many ways can we choose the two digits?

probability1.01 (Apr 7, 2004 7:34:38 PM)
C(9, 2) first

jelyman (Apr 7, 2004 7:34:41 PM)
9C2

MCrawford (Apr 7, 2004 7:34:48 PM)
Why?

dgf (Apr 7, 2004 7:34:58 PM)
later, we have to account for those with 0

MCrawford (Apr 7, 2004 7:35:06 PM)
Ah, so we have not accounted for those with 0.

MCrawford (Apr 7, 2004 7:35:17 PM)
We have also divided by 2 when we do not need to.

MCrawford (Apr 7, 2004 7:35:33 PM)
The first digit that appears is a distinct idea from the second digit.

MCrawford (Apr 7, 2004 7:35:58 PM)
The first digit can't be 0. Once we have that digit chosen, we have any possibility for the 2nd digit. How many possibilities does this give us?

interesting_move (Apr 7, 2004 7:36:12 PM)
There are 90 two digit numbers. We eliminate the 9 of them that have 2 of the same digits to get 81.

timhlu (Apr 7, 2004 7:36:14 PM)
9*9=81

MCrawford (Apr 7, 2004 7:36:31 PM)
We can call the first digit that occurs d and the second digit that occurs e.

MCrawford (Apr 7, 2004 7:36:37 PM)
The first digit can't be 0, so there are 9 choices for d. This leaves 9 choices for e. We have 81 ways to select the two digits. How many arrangements can we make for those digits once chosen?

mathclass (Apr 7, 2004 7:36:57 PM)
there are varying amounts for 4,3,2 digits numbers

MCrawford (Apr 7, 2004 7:37:14 PM)
We only now need the arrangements such as de or dded.

MCrawford (Apr 7, 2004 7:37:18 PM)
How many total arrangements?

no_one_2000 (Apr 7, 2004 7:38:11 PM)
de, dde, ded, dee, ddde, dded, ddee, dedd, dede, deed, deee

wheezy81 (Apr 7, 2004 7:38:27 PM)
what about ed???

MCrawford (Apr 7, 2004 7:38:34 PM)
We defined d to be the first digit.

MCrawford (Apr 7, 2004 7:38:44 PM)
This is how we got around casework involving 0.

dgf (Apr 7, 2004 7:38:55 PM)
for 3 digits: 3, since we have 4 choices for the last 2, except ddd. for 4 digits, 7 by the same reasoning, so 11 total

MCrawford (Apr 7, 2004 7:39:01 PM)
So, what's our final answer?

interesting_move (Apr 7, 2004 7:39:17 PM)
81*11=891.

MCrawford (Apr 7, 2004 7:39:20 PM)
plus 36...

skapoor (Apr 7, 2004 7:39:24 PM)
927

random%0 (Apr 7, 2004 7:39:27 PM)
36+81*11

MCrawford (Apr 7, 2004 7:39:32 PM)
Now we simply list the ways that we can make numbers with only digits d and e where d comes first: de, dde, ded, dee, ddde, dded, dedd, ddee, dede, deed, deee. There are 11 such possibilities, so there are 11(81) = 891 positive integers less than 10000 with exactly 2 distinct digits. This gives us a total of 36 + 891 = 927 integers less than 10000 with at most 2 different digits.

MCrawford (Apr 7, 2004 7:40:17 PM)
I know some of you did the casework differently, but I think it's important to think about ways that we can organize our casework to keep us from having to view 0 cases differently.

Fierytycoon (Apr 7, 2004 7:40:31 PM)
erg, I did a different kind of casework on the exam: examining 1-digit numbers, 2-digit numbers, etc... However...it turned out very messy and I missed a case and thus got the problem wrong.

MCrawford (Apr 7, 2004 7:40:34 PM)
5. In order to complete a large job, 1000 workers were hired, just enough to complete the job on schedule. All the workers stayed on the job while the first quarter of the work was done, so the first quarter of the work was completed on schedule. Then 100 workers were laid off, so the second quarter of the work was completed behind schedule. Then an additional 100 workers were laid off, so the third quarter of the work was completed still further behind schedule. Given that all workers work at the same rate, what is the minimum number of additional workers, beyond the 800 workers still on the job at the end of the third quarter, that must be hired after three-quarters of the work has been completed so that the entire project can be completed on schedule or before?

MCrawford (Apr 7, 2004 7:40:42 PM)
//s3.amazonaws.com/classroom.artofproblemsolving.com/Classes/AIME/Images/2004aimeB5mismanagement.gif

MCrawford (Apr 7, 2004 7:40:54 PM)
Here we have another word problem that we need to translate into the language of mathematics. What kinds of equations can we make out of the information given?

justdudxit (Apr 7, 2004 7:40:57 PM)
quarter=amount of work, not time

MCrawford (Apr 7, 2004 7:41:18 PM)
I think this confused a lot of students. I have seen very many wrong answers based on this interpretation.

MCrawford (Apr 7, 2004 7:41:35 PM)
It is important to read each problem carefully and be very suspicious if the problem looks "too easy".

probability1.01 (Apr 7, 2004 7:41:54 PM)
They took 1+10/9+10/8 quarters to do 3 quarters' work, right?

peaceout (Apr 7, 2004 7:41:59 PM)
so 1000 workers do 1/4 work, 900 do 9/10*1/4 work, 800 do 8/10*1/4 of work

MCrawford (Apr 7, 2004 7:42:11 PM)
We can call t_1 the number of days it took to finish the first quarter of the work, t_2 the number of days it took to finish the second quarter of the work, and t_3 the number of days it took to finish the third quarter of the work. We can call n the number of worker days it takes to finish each quarter of the job. What can we express in terms of t_1, t_2, t_3, and n?

MithsApprentice (Apr 7, 2004 7:43:20 PM)
t_1=n, t_2=10n/9, t_3=5n/4, t_4=23n/36

MCrawford (Apr 7, 2004 7:43:29 PM)
We are given that 1000t_1 = n. Next we are given that 900t_2 = n. Then we are given that 800t_3 = n.

MCrawford (Apr 7, 2004 7:43:42 PM)
We would like to know how much time remains for the work to be completed on schedule.

MCrawford (Apr 7, 2004 7:43:54 PM)
The total amount of time scheduled was 4t_1. The total amount of time that has passed is t_1 + t_2 + t_3. This leaves 4t_1 - (t_1 + t_2 + t_3) = 3t_1 - t_2 - t_3 left to complete the job.

MCrawford (Apr 7, 2004 7:44:08 PM)
We can simplify the amount of time remaining through the equations we established relating each t_1, t_2, and t_3 to n. Equation each of the left hand sides (that are each equal to n) we see that t_2 = 10t_1/9 and t_3 = 5t_1/4. This means that the total amount of time remaining is (3 - 10/9 - 5/4)t_1 = 23t_1/36. How do we use this quantity of time?

Hexahedron (Apr 7, 2004 7:44:40 PM)
4-1-10/9-10/8=23/36 so number of workers on last quarter is 36/23*1000=1566 then subtract 800 so ANS is 766

MithsApprentice (Apr 7, 2004 7:44:43 PM)
We see that we have 23/36 of the "scheduled" time, so we need 36/23 of the 1000 workers.

probability1.01 (Apr 7, 2004 7:44:48 PM)
That just means you need 36/23 of the workforce of t_1

MCrawford (Apr 7, 2004 7:44:55 PM)
We set up a fourth work equation: (23t_1/36)w = n, where w is the total number of workers needed. From this we see that w = (36/23)n/t_1.

MCrawford (Apr 7, 2004 7:45:03 PM)
Our first work equation told us that 1000t_1 = n, so n/t_1 = 1000. We now know that we need a total of w = (36/23)n/t_1 = 36000/23 workers to complete the job on time.

MCrawford (Apr 7, 2004 7:45:11 PM)
We need a total of at least 36000/23 - 800 = 17600/23 additional workers. Of course, we don't hire fractional workers, so we will have to round this quantity up to our final answer.

MCrawford (Apr 7, 2004 7:45:23 PM)
17600/23 = 765 5/23, so we need 766 additional workers.

MCrawford (Apr 7, 2004 7:45:36 PM)
6. Three clever monkeys divide a pile of bananas. The first monkey takes some bananas from the pile, keeps three-fourths of them, and divides the rest equally between the other two. The second monkey takes some bananas from the pile, keeps one-fourth of them, and divides the rest equally between the other two. The third monkey takes the remaining bananas from the pile, keeps one-twelfth of them, and divides the rest equally between the other two. Given that each monkey receives a whole number of bananas whenever the bananas are divided, and the numbers of bananas the first, second, and third monkeys have at the end of the process are in the ratio 3:2:1, what is the least possible total for the number of bananas?

MCrawford (Apr 7, 2004 7:45:41 PM)
//s3.amazonaws.com/classroom.artofproblemsolving.com/Classes/AIME/Images/2004aimeB6MonkeyButlers.gif

MCrawford (Apr 7, 2004 7:46:07 PM)
If you like word problems, I'm sure you love this AIME. Now, what do we need to do to mathematize this problem?

probability1.01 (Apr 7, 2004 7:46:18 PM)
express the quantities taken as x, y, and z, respectively

random%0 (Apr 7, 2004 7:46:36 PM)
call the number of bananas each monkey takes from the pile A, B, C

MCrawford (Apr 7, 2004 7:46:49 PM)
We can create equations for the number of bananas divided up each time while noting that the numbers must be integers.

probability1.01 (Apr 7, 2004 7:46:56 PM)
use fractional parts of x, y, and z to express what monkeys took

random%0 (Apr 7, 2004 7:47:04 PM)
A and B must both be multiples of 8, and C must be a multiple of 24

MCrawford (Apr 7, 2004 7:47:16 PM)
I used this last idea to create slightly different equations.

random%0 (Apr 7, 2004 7:47:22 PM)
easier to do the problem without fractions, so N=8A+8B+24C

MCrawford (Apr 7, 2004 7:47:29 PM)
The first monkey keeps 3/4 of some amount and gives 1/8 of that amount to each other monkey. The common denominator of all these fractions is 8. Comparing the numerators we get 6x bananas to the first monkey, x to each of the others.

MCrawford (Apr 7, 2004 7:47:40 PM)
The second monkey keeps 1/4 of some amount and gives 3/8 of that amount to each other monkey. The common denominator of all these fractions is again 8. Comparing the numerators we get 3y bananas to the first monkey, 2y to the second, and 3y to the third.

MCrawford (Apr 7, 2004 7:47:49 PM)
The third monkey keeps 1/12 of some amount and gives 11/24 of that amount to each other monkey. The common denominator of all these fractions is 24. Comparing the numerators we get 11z bananas to the first monkey, 11z to the second, and 2z to the third.

no_one_2000 (Apr 7, 2004 7:47:51 PM)
Just multiply the fractions out so you have whole numbers

MCrawford (Apr 7, 2004 7:48:18 PM)
The problem with that is that we would then have divisibility considerations to work through at the end.

MCrawford (Apr 7, 2004 7:48:28 PM)
We can cast aside all doubts if we start with integers.

MithsApprentice (Apr 7, 2004 7:48:41 PM)
First monkey = 6x+3y+11z, Second= x + 2y + 11z, Third= x + 3y + 2z

MCrawford (Apr 7, 2004 7:48:52 PM)
Noting that the ratio of bananas is 3:2:1, we can say that the first monkey has 3n bananas, the second has 2n, and the third has n. This gives us the system of equations 6x + 3y + 11z = 3n, x + 2y + 11z = 2n, x + 3y + 2z = n.

MCrawford (Apr 7, 2004 7:49:17 PM)
Now we have a system of 3 linear equations in 4 variables. Is this a problem?

xirtamax (Apr 7, 2004 7:49:34 PM)
no

jelyman (Apr 7, 2004 7:49:37 PM)
nah

lculus (Apr 7, 2004 7:49:40 PM)
no, it is diophantine

interesting_move (Apr 7, 2004 7:49:44 PM)
No, we just have to minimize n.

MCrawford (Apr 7, 2004 7:49:53 PM)
We can solve for (x, y, z) as if n were a constant and we get (11n/68, 13n/68, 9n/68) as our solution set. Clearly n must be a multiple of 68 for x, y, and z to be integers. What does this give us as a final answer?

jelyman (Apr 7, 2004 7:50:35 PM)
408

xirtamax (Apr 7, 2004 7:50:39 PM)
408

MCrawford (Apr 7, 2004 7:50:42 PM)
The total number of bananas is 3n + 2n + n = 6n which is smallest when n = 68, thus 408 is the answer.

rrusczyk (Apr 7, 2004 7:50:58 PM)
7. ABCD is a rectangular sheet of paper that has been folded so that corner B is matched with point B' on edge AD. The crease is EF, where E is on AB and F is on CD. The dimensions AE = 8, BE = 17, and CF = 3 are given. The perimeter of rectangle ABCD is m/n, where m and n are relatively prime positive integers. Find m + n.

rrusczyk (Apr 7, 2004 7:51:02 PM)
//s3.amazonaws.com/classroom.artofproblemsolving.com/Classes/AIME/Images/2004aimeB7fol.gif

rrusczyk (Apr 7, 2004 7:51:09 PM)
Where should we start?

whitesnowflakes (Apr 7, 2004 7:51:13 PM)
you use similar triangles

justdudxit (Apr 7, 2004 7:51:15 PM)
find similar triangles

Fierytycoon (Apr 7, 2004 7:51:23 PM)
paper folding always involves similar triangles

rrusczyk (Apr 7, 2004 7:51:33 PM)
We have lots of right triangles, which produce a mess of similar triangles. Are there any points we should name or lines to add?

hypercube (Apr 7, 2004 7:52:06 PM)
the small triangle at the top

rrusczyk (Apr 7, 2004 7:52:18 PM)
We draw the covered edge and label the intersection of that edge with the folds:

rrusczyk (Apr 7, 2004 7:52:21 PM)
//s3.amazonaws.com/classroom.artofproblemsolving.com/Classes/AIME/Images/2004aimeB7fand.gif

rrusczyk (Apr 7, 2004 7:52:33 PM)
What similarities do we have?

dgf (Apr 7, 2004 7:53:20 PM)
C'FX ~ DB'X ~ AEB'

rrusczyk (Apr 7, 2004 7:53:32 PM)
We have AB'E ~ DXB' ~ C'XF.

rrusczyk (Apr 7, 2004 7:53:38 PM)
Do we know anything else?

jelyman (Apr 7, 2004 7:54:02 PM)
we should take advatnage of that BE = 17 and from that DF = 22 (this is by reflections maintaining distance, etc with lines)

dgf (Apr 7, 2004 7:54:04 PM)
AB' is 15

justdudxit (Apr 7, 2004 7:54:09 PM)
we know C'F = 3

dgf (Apr 7, 2004 7:54:11 PM)
C'F is 3

peaceout (Apr 7, 2004 7:54:13 PM)
sorry ab' is 15 by the pythagorean theorem

rrusczyk (Apr 7, 2004 7:54:23 PM)
From Pythagoras, we know that AB' = 15 (right triangle AB'E), and from reflection, we know that BE = 17 and C'F = 3. So what's all we need?

lculus (Apr 7, 2004 7:54:52 PM)
B'D

justdudxit (Apr 7, 2004 7:54:57 PM)
DB'

rrusczyk (Apr 7, 2004 7:55:04 PM)
All we need is DB' and we're done. How do we get it?

dgf (Apr 7, 2004 7:55:22 PM)
we need to find FX, then we'll know DX, then we can find B'D

justdudxit (Apr 7, 2004 7:55:54 PM)
similarity

interesting_move (Apr 7, 2004 7:55:57 PM)
solve using proportions.

rrusczyk (Apr 7, 2004 7:56:02 PM)
OK What is XF?

Scotsten86 (Apr 7, 2004 7:56:25 PM)
51/8

pi-girl (Apr 7, 2004 7:56:27 PM)
51/8

MithsApprentice (Apr 7, 2004 7:56:30 PM)
51/8

rrusczyk (Apr 7, 2004 7:56:38 PM)
XF = (17/8)(CF') = 51/8, so

rrusczyk (Apr 7, 2004 7:56:43 PM)
DX = DC - XF - FC = 22 - 51/8 = 125/8.

rrusczyk (Apr 7, 2004 7:56:46 PM)
What is DB'?

pi-girl (Apr 7, 2004 7:57:25 PM)
25/3

dgf (Apr 7, 2004 7:57:28 PM)
8/15 * 125/8 = 25/3

rrusczyk (Apr 7, 2004 7:57:36 PM)
DB' = (8/15) DX = 125/15 = 25/3.

rrusczyk (Apr 7, 2004 7:57:45 PM)
Hence, what is our perimeter?

probability1.01 (Apr 7, 2004 7:58:14 PM)
290/3

probability1.01 (Apr 7, 2004 7:58:17 PM)
293 for m + n

dgf (Apr 7, 2004 7:58:19 PM)
30 + 50 + 50/3 = 290/3, so 293

justdudxit (Apr 7, 2004 7:58:21 PM)
2(25/3 + 15 + 25)= 290/3

rrusczyk (Apr 7, 2004 7:58:23 PM)
Hence, our perimeter is 2(15+25/3+25) = 2(145/3) = 290/3.

rrusczyk (Apr 7, 2004 7:58:40 PM)
I think a few of you took considerably different paths - please share your solutions on the board.

rrusczyk (Apr 7, 2004 7:58:53 PM)
I think many of you used some Pythagoras relationships, like this:

jelyman (Apr 7, 2004 7:58:55 PM)
Connect BF and B'F and B'E. BE = 17 = B'E, so AB' = 15. DF = 22, so DF^2 + B'D^2 = B'F^2 = BF^2 = BC^2 + CF^2 = (15 + B'D)^2 + 9 = 22^2 + B'D^2...

rrusczyk (Apr 7, 2004 7:59:11 PM)
To get to a solution (these will often get you home in paper folding problems).

Note: Later in class, MPS-Vras noted a cool solution employing cyclic quadrilateral B'DC'F. See if you can find it!

MCrawford (Apr 7, 2004 7:59:36 PM)
8 How many positive integer divisors of 2004^2004 are divisible by exactly 2004 positive integers?

MCrawford (Apr 7, 2004 7:59:44 PM)
First, how do we count the total number of positive divisors of a positive integer?

timhlu (Apr 7, 2004 8:00:07 PM)
prime factor, add 1 to exponents, multiply

xirtamax (Apr 7, 2004 8:00:18 PM)
(e1 +1 )(e2 +1 )...

MCrawford (Apr 7, 2004 8:00:19 PM)
Let's take the case of 2004^2004. First, we take the prime factorization: 2^4008*3^2004*167^2004.

MCrawford (Apr 7, 2004 8:00:29 PM)
Now, we note that any divisor of this number must be in the form 2^a*3^b*167*c where a is no more than 4008, b no more than 2004, and c no more than 2004. Every number in this form is a divisor so we have choices 0-4008 for a, 0-2004 for b, and 0-2004 for c. The total number of divisors is thus (4008 + 1)(2004 + 1)(2004 + 1).

MCrawford (Apr 7, 2004 8:00:53 PM)
Given this method for adding 1 to each exponent in the prime factorization and taking the product, how can we count the divisors of 2004^2004 with 2004 divisors?

interesting_move (Apr 7, 2004 8:01:16 PM)
find the prime factorization of 2004.

timhlu (Apr 7, 2004 8:01:41 PM)
(a+1)(b+1)(c+1)=2004

dgf (Apr 7, 2004 8:01:48 PM)
2^a*3^b*167^c has 2004 factors if (a+1)(b+1)(c+1) = 2004

probability1.01 (Apr 7, 2004 8:01:52 PM)
(a+1)(b+1)(c+1) must be 2004, and 2004 has a limited number of factors

MCrawford (Apr 7, 2004 8:01:54 PM)
There are 3 prime factors: 2, 3, and 167. If we call the exponents to some divisor a, b, and c, we want to count up those where (a + 1)(b + 1)(c + 1) = 2004. How can we take this count?

probability1.01 (Apr 7, 2004 8:03:42 PM)
maybe 1*1*2*2*3*167 = 2004 and you need to partition that into 3 groups (e.g., 1*1*2, 2*3, 167)

MCrawford (Apr 7, 2004 8:03:56 PM)
(a + 1)(b + 1)(c + 1) = 2*2*3*167. We can divide the count up into a bit of casework. We can begin by counting up possibilities where the smallest of a + 1, b + 1, and c + 1 is 1. How many are there?

jelyman (Apr 7, 2004 8:04:27 PM)
4!/2!

MCrawford (Apr 7, 2004 8:04:36 PM)
If the smaller of a + 1, b + 1, and c + 1 is 1, then the product of the other two is 2004. 2004 has 12 positive divisors, so there are 6 ways we can order a + 1, b + 1, and c + 1 from least to greatest: 1, 1, 2004; 1, 2, 1002; 1, 3, 668; 1, 4, 501; 1, 6, 334; 1, 12, 167. In how many ways can we choose a, b, and c from these possibilities?

justdudxit (Apr 7, 2004 8:05:12 PM)
5*6 + 3 = 33

lculus (Apr 7, 2004 8:05:14 PM)
33

MCrawford (Apr 7, 2004 8:05:25 PM)
Why 33?

interesting_move (Apr 7, 2004 8:05:43 PM)
because 1, 1, and 2004 only has 3 possibilities.

justdudxit (Apr 7, 2004 8:05:52 PM)
there are 6 orders for the bottom 5, and only 3 for the top. So that's 33

MCrawford (Apr 7, 2004 8:05:54 PM)
Here is the wrinkle in this problem: There are 3! = 6 ways to order each of these sets of numbers except for the first. There are only 3 ways to order 1, 1, and 2004. This gives us a total of 33 possibilities where the smallest of a + 1, b + 1, and c + 1 is 1.

MCrawford (Apr 7, 2004 8:06:08 PM)
Now, how many possibilities are there when the smallest of a + 1, b + 1, and c + 1 is 2?

Scotsten86 (Apr 7, 2004 8:06:47 PM)
find number of factors of 1002

wheezy81 (Apr 7, 2004 8:07:18 PM)
8

MCrawford (Apr 7, 2004 8:07:32 PM)
If the smallest of a + 1, b + 1, and c + 1 is 2, then the product of the other two is 1002. 1002 has 8 positive divisors, but we throw out the divisor pair 1, 1002 because the smallest of a + 1, b + 1, and c + 1 must be 2. So, there are 3 arrangements left: 2, 2, 501; 2, 3, 334; 2, 6, 167. In how many ways can we choose a, b, and c from these possibilities?

interesting_move (Apr 7, 2004 8:07:53 PM)
6*2+3=15.

mathclass (Apr 7, 2004 8:08:01 PM)
2*6 +3=15

MCrawford (Apr 7, 2004 8:08:05 PM)
Again we face the fact that the first of these possibilities has only 3 distinct ordering, so we have a total of 3 + 6 + 6 = 15 possibilities where the smallest of a + 1, b + 1, and c + 1 is 2.

MCrawford (Apr 7, 2004 8:08:18 PM)
Now, how many possibilities are there when the smallest of a + 1, b + 1, and c + 1 is 3?

justdudxit (Apr 7, 2004 8:08:50 PM)
1

lculus (Apr 7, 2004 8:08:53 PM)
3,4,167

Scotsten86 (Apr 7, 2004 8:09:02 PM)
2004/3 has 6 factors

MCrawford (Apr 7, 2004 8:09:04 PM)
If the smallest of a + 1, b + 1, and c + 1 is 3, then the product of the other two is 668. Since both numbers in the divisor pairs of 668 must be at least 3, we have but one choice: 3, 4, 167. This possibility has 6 orderings.

interesting_move (Apr 7, 2004 8:09:14 PM)
Looking at the factors of 668, we have (4, 167), so it's 3!=6.

MCrawford (Apr 7, 2004 8:09:19 PM)
Now, how many possibilities are there when the smallest of a + 1, b + 1, and c + 1 is 4?

interesting_move (Apr 7, 2004 8:09:48 PM)
None.

justdudxit (Apr 7, 2004 8:09:50 PM)
there are none

unknown (Apr 7, 2004 8:09:54 PM)
0 because you would need a 3

MCrawford (Apr 7, 2004 8:10:01 PM)
Since 2004 = 2*2*3*167, the largest of a + 1, b + 1, and c + 1 must be at least 167, so the product of the smaller two is no more than 12. This means that the smallest of a + 1, b + 1, and c + 1 is at most 3, so we are done counting. What is our final answer?

interesting_move (Apr 7, 2004 8:10:12 PM)
33+15+6=54.

justdudxit (Apr 7, 2004 8:10:14 PM)
54

MCrawford (Apr 7, 2004 8:10:20 PM)
33 + 15 + 6 = 54 positive integer divisors of 2004^2004 with exactly 2004 positive divisors.

MCrawford (Apr 7, 2004 8:11:08 PM)
Be careful with your casework and the way you count the arrangements. It is very important to set up a system for casework at the beginning (like choosing to go by the smallest of a + 1, b + 1, and c + 1...1, 2, 3, 4 (no more)).

MCrawford (Apr 7, 2004 8:11:19 PM)
9. A sequence of positive integers with a_1 = 1 and a_9 + a_10 = 646 is formed so that the first three terms are in geometric progression, the second, third, and fourth terms are in arithmetic progression, and, in general, for all n >= 1, the terms a_(2n-1), a_(2n), a_(2n+1) are in geometric progression, and the terms a_(2n), a_(2n+1), and a_(2n+2) are in arithmetic progression. Let a_n be the greatest term in this sequence that is less than 1000. Find n + a_n.

MCrawford (Apr 7, 2004 8:11:24 PM)
//s3.amazonaws.com/classroom.artofproblemsolving.com/Classes/AIME/Images/2004aimeB9Alternating.gif

MCrawford (Apr 7, 2004 8:11:35 PM)
I like this problem.

MCrawford (Apr 7, 2004 8:11:43 PM)
First, before we work on this problem, let's play around with one such sequence without the a_9 + a_10 requirement. Let a_2 = 2. What are the first few terms of this sequence?

justdudxit (Apr 7, 2004 8:12:23 PM)
1,2,4,6,9,12,16 ,20

Mr.Ocax (Apr 7, 2004 8:12:25 PM)
1,2,4,6,9,12,16

MithsApprentice (Apr 7, 2004 8:12:27 PM)
1,2,4,6,9,12,16,20,25...

MCrawford (Apr 7, 2004 8:12:33 PM)
1, 2, 4, 6, 9, 12, 16, 20, 25, 30, 36,… Wow, that's rather nice! Will it always turn out so nice?

jelyman (Apr 7, 2004 8:12:42 PM)
actually yes

MCrawford (Apr 7, 2004 8:12:48 PM)
We try letting a_2 = 3 and we get 1, 3, 9, 15, 25, 35, 49, 63, 81,… Hey, this looks nice as well! This is so much fun I'll try one more!

MCrawford (Apr 7, 2004 8:12:57 PM)
We let a_2 = 4 and we get 1, 4, 16, 28, 49, 70, 100, 130, 169,…

probability1.01 (Apr 7, 2004 8:13:01 PM)
then you begin to see a pattern

MCrawford (Apr 7, 2004 8:13:10 PM)
So, what is nice about these sequences?

Scotsten86 (Apr 7, 2004 8:13:19 PM)
lots of squares

no_one_2000 (Apr 7, 2004 8:13:32 PM)
Every other number is in a sequence of its own

MCrawford (Apr 7, 2004 8:13:39 PM)
The odd terms of each sequence are perfect squares. What about the other terms?

lculus (Apr 7, 2004 8:13:54 PM)
the ones in between the squares are the geometric means of those squares

MCrawford (Apr 7, 2004 8:14:04 PM)
The even terms of each sequence are the geometric means of those squares, so they are the product of the square roots of the perfect squares.

MCrawford (Apr 7, 2004 8:14:35 PM)
Now, can we describe these sequences even more precisely?

probability1.01 (Apr 7, 2004 8:15:03 PM)
Why not let a_2 = x?

MCrawford (Apr 7, 2004 8:15:15 PM)
And if we do, what does our sequence look like?

dgf (Apr 7, 2004 8:16:20 PM)
a3 = x^2, a5 = (2x-1)^2, a7 = (3x-2)^2

MCrawford (Apr 7, 2004 8:16:58 PM)
And since the terms in between are the geometric means of those, we now have a very nice way to construct our sequence in terms of x.

MCrawford (Apr 7, 2004 8:17:24 PM)
What can we do with this nice way?

probability1.01 (Apr 7, 2004 8:17:34 PM)
1, x, x^2, (2x-1)x, (2x-1)^2, (2x-1)(3x-2), etc.

dgf (Apr 7, 2004 8:17:38 PM)
a9 = (4x-3)^2 a11 = (5x_4)^2, a10 = (4x-3)(5x-4)

justdudxit (Apr 7, 2004 8:17:56 PM)
so we find x

Scotsten86 (Apr 7, 2004 8:17:58 PM)
multiply them and solve for x

probability1.01 (Apr 7, 2004 8:18:01 PM)
first add a_9 and a_10, which must equal 646

MCrawford (Apr 7, 2004 8:18:06 PM)
What is our equation?

MithsApprentice (Apr 7, 2004 8:18:28 PM)
646 = (4x-3)(9x-7)

MCrawford (Apr 7, 2004 8:18:35 PM)
So, what is x?

MithsApprentice (Apr 7, 2004 8:18:50 PM)
x=5

jelyman (Apr 7, 2004 8:18:52 PM)
5

MCrawford (Apr 7, 2004 8:19:06 PM)
5 is the only solution that is a positive integer.

MCrawford (Apr 7, 2004 8:19:16 PM)
Now that we have x = 5, how do we finish the problem?

justdudxit (Apr 7, 2004 8:19:33 PM)
start generating terms

probability1.01 (Apr 7, 2004 8:19:51 PM)
Then, given x=5, we find the largest number below 1000, and since the terms' products have a factor that is x-1 = 4 greater than the previous, we try stuff like 29*33

MCrawford (Apr 7, 2004 8:20:11 PM)
What is n and a_n just before the terms exceed 1000?

MithsApprentice (Apr 7, 2004 8:20:21 PM)
We see that f_16=957

MithsApprentice (Apr 7, 2004 8:20:37 PM)
So, we have 973 as our answer.

3cnfsat (Apr 7, 2004 8:20:45 PM)
And... 29 * 33 works. The x^2 terms only get to 29^2, but the 29*33 term is bigger than all those and the k^2's. So f_16 = 957, and 973 is the answer.

MCrawford (Apr 7, 2004 8:21:03 PM)
What was the most important feature to our solution?

MCrawford (Apr 7, 2004 8:21:14 PM)
What guided us to the answer?

interesting_move (Apr 7, 2004 8:21:25 PM)
discovering the pattern.

3cnfsat (Apr 7, 2004 8:21:27 PM)
Finding a pattern for the terms

MCrawford (Apr 7, 2004 8:21:32 PM)
Even before that...

Scotsten86 (Apr 7, 2004 8:21:35 PM)
experimentation

justdudxit (Apr 7, 2004 8:21:37 PM)
trying simple cases

MCrawford (Apr 7, 2004 8:21:53 PM)
We toyed around with possible sequences. We played. We had fun!

MCrawford (Apr 7, 2004 8:22:08 PM)
And voila! A pattern jumped out and smacked us on the forehead!

jelyman (Apr 7, 2004 8:22:16 PM)
hehe... or we can just apply 10 mins of algebra (MY TECHNIQUE!!!)

MCrawford (Apr 7, 2004 8:22:28 PM)
That's okay, I worked it that way too the first time around ;)

MCrawford (Apr 7, 2004 8:22:42 PM)
10. Let S be the set of integers between 1 and 2^40 whose binary expansions have exactly two 1's. If a number is chosen at random from S, the probability that it is divisible by 9 is p/q, where p and q are relatively prime positive integers. Find p + q.

MCrawford (Apr 7, 2004 8:22:48 PM)
//s3.amazonaws.com/classroom.artofproblemsolving.com/Classes/AIME/Images/2004aimeB10Binary9.gif

MCrawford (Apr 7, 2004 8:23:01 PM)
What kinds of integers are we looking for (whether or not they are divisible by 9)?

dgf (Apr 7, 2004 8:23:32 PM)
2^a + 2^b

no_one_2000 (Apr 7, 2004 8:23:35 PM)
2^x+2^y

MCrawford (Apr 7, 2004 8:23:53 PM)
We are looking for integers in the form 2^n + 2^m where m, n < 40 and n and m are distinct. How many such integers are there?

MithsApprentice (Apr 7, 2004 8:24:18 PM)
C(40,2)

dgf (Apr 7, 2004 8:24:20 PM)
40C2

3cnfsat (Apr 7, 2004 8:24:30 PM)
ncr(40,2)

MCrawford (Apr 7, 2004 8:24:32 PM)
There are C(40, 2) = 780 ways to pick 2 distinct exponents from the 40 possibilities 0 - 39. How can we tell which of these yield 2^n + 2^m which is a multiple of 9?

justdudxit (Apr 7, 2004 8:25:14 PM)
take the residue of each place value mod 9, and find combos that work

MCrawford (Apr 7, 2004 8:25:29 PM)
We could do this in a more organized way.

dgf (Apr 7, 2004 8:25:36 PM)
2^n(1 + 2^m-n) = 9x

MCrawford (Apr 7, 2004 8:25:50 PM)
Without loss of generality we can assume n > m. We want 2^n + 2^m :=: 0 (mod 9). Since 2 and 9 are relatively prime, we can divide both sides by 2^m, thus 2^(n-m) + 1 :=: 0 (mod 9). Now what?

interesting_move (Apr 7, 2004 8:26:11 PM)
subtract 1 from both sides.

Pork_Chop8 (Apr 7, 2004 8:26:14 PM)
n - m = 3 mod 6

MCrawford (Apr 7, 2004 8:26:28 PM)
We note that 2^3 = 8 :=: -1 (mod 9). We also note that 2^6 is the first (positive) power of 2 that is :=: 1 (mod 9). What does this mean?

jelyman (Apr 7, 2004 8:27:05 PM)
every number has a period 6 mod 9 (euler's generalization)

MCrawford (Apr 7, 2004 8:27:17 PM)
We now see that n - m must be 3 more than a multiple of 6. How can we count the total number of times when n - m is 3 more than a multiple of 6?

probability1.01 (Apr 7, 2004 8:28:14 PM)
for 3, there are (3,0) to (39, 36) = 37 choices

MCrawford (Apr 7, 2004 8:28:28 PM)
This is the beginning of one form of casework we could employ. Any others?

MCrawford (Apr 7, 2004 8:29:18 PM)
There are a number of ways we can break down the cases and get a summation. Overall the summation looks like SUM[i = 0 to 39] [[(i +3)/6]] where [[x]] represents the greatest integer less than or equal to x. What is this sum?

3cnfsat (Apr 7, 2004 8:30:06 PM)
Ok, for 0 <= k <= 39, there are 7 choices for a k congruent to each of 0,1,2,3 mod 6 and 6 choices for k congruent to 4 or 5 mod 6. That means there are 2 (7^2 + 7*6 + 7 * 6) pairs in all.

Pork_Chop8 (Apr 7, 2004 8:30:20 PM)
39 and 0 are only for greatest difference, 39 and 6, 38 and 5, ..., 33 and 0 and for next greatest difference so as each mod decreases, the number of ways increases by 6, there are 7 differences(39 thru 3) so the sum is 1 + 7 + 13 + .. .+ 37

probability1.01 (Apr 7, 2004 8:30:33 PM)
133, right?

MCrawford (Apr 7, 2004 8:30:35 PM)
The sum is 3 0's + 6 1's + 6 2's + 6 3's + 6 4's + 6 5's + 6 6's + 1 7. 3(0) + 6(1 + 2 + 3 + 4 + 5 + 6) + 7 = 133. What is our final answer?

justdudxit (Apr 7, 2004 8:30:39 PM)
913

MCrawford (Apr 7, 2004 8:30:45 PM)
133/780 does not reduce so the answer is 133 + 780 = 913.

rrusczyk (Apr 7, 2004 8:31:16 PM)
11. A right circular cone has a base with radius 600 and height 200sqrt(7). A fly starts at a point on the surface of the cone whose distance from the vertex of the cone is 125, and crawls along the surface of the cone to a point on the exact opposite side of the cone whose distance from the vertex is 375sqrt(2). Find the least distance that the fly could have crawled.

rrusczyk (Apr 7, 2004 8:31:23 PM)
Having seen a few of these types of problems (on the AMC-10 and the first AIME this year), what do we think of doing?

probability1.01 (Apr 7, 2004 8:31:39 PM)
unraveling the cone gives 3/4 of a circle of radius sqrt(600^2+(200sqrt(7))^2) = 800. Then one can find the length of a direct line between the two points fairly easily.

3cnfsat (Apr 7, 2004 8:31:42 PM)
unroll the cone!

rand()%0 (Apr 7, 2004 8:31:44 PM)
flattening out the cone to a circle segment

rrusczyk (Apr 7, 2004 8:31:49 PM)
We think of unwinding our cone:

rrusczyk (Apr 7, 2004 8:31:53 PM)
//s3.amazonaws.com/classroom.artofproblemsolving.com/Classes/AIME/Images/2004aimeB11cc.gif

rrusczyk (Apr 7, 2004 8:31:57 PM)
We know VA = slant height = 800 (we can use a right triangle from our original cone to see that the slant height is 800).

rrusczyk (Apr 7, 2004 8:32:01 PM)
What else do we know?

probability1.01 (Apr 7, 2004 8:32:36 PM)
the circumference of the base is 1200 pi

rrusczyk (Apr 7, 2004 8:32:43 PM)
What does this tell us?

3cnfsat (Apr 7, 2004 8:33:00 PM)
We have 3/4 of a circle.

rrusczyk (Apr 7, 2004 8:33:07 PM)
We know that the arc is 270 degrees, since the circumference of the base of the cone is 1200pi, and the circumference of the full circle V would be 1600pi.

probability1.01 (Apr 7, 2004 8:33:22 PM)
the cone unrolls to have only 1200 pi of the total 1600 pi circumference

rrusczyk (Apr 7, 2004 8:33:25 PM)
What else do we need in our diagram?

probability1.01 (Apr 7, 2004 8:33:44 PM)
the points

rrusczyk (Apr 7, 2004 8:33:46 PM)
We need the fly's start and end point. Where are they?

3cnfsat (Apr 7, 2004 8:34:09 PM)
"diametrically opposite" means 3/8 of a circle away

rrusczyk (Apr 7, 2004 8:34:25 PM)
Indeed. Where should we put our points in this diagram?

Joshchoi (Apr 7, 2004 8:34:57 PM)
us an AV segment as 0 degrees

probability1.01 (Apr 7, 2004 8:35:01 PM)
let one point be at the edge of the circle segment and the other at the middle (they were directly opposite)

rrusczyk (Apr 7, 2004 8:35:08 PM)
We can put one of these on one of the AV's.

rrusczyk (Apr 7, 2004 8:35:15 PM)
The other is on the segment connecting V to midpoint of arc AA (since it is on the opposite side of the cone):

rrusczyk (Apr 7, 2004 8:35:19 PM)
//s3.amazonaws.com/classroom.artofproblemsolving.com/Classes/AIME/Images/2004aimeB11loc.gif

rrusczyk (Apr 7, 2004 8:35:26 PM)
We are given VB =125 and VC = 375 sqrt(2). How do we get BC?

Pork_Chop8 (Apr 7, 2004 8:36:08 PM)
law of cosines

rrusczyk (Apr 7, 2004 8:36:14 PM)
What is angle CVB?

pi^2 (Apr 7, 2004 8:36:31 PM)
135

justdudxit (Apr 7, 2004 8:36:44 PM)
How you do you know that the path is straight when you unfold it

rrusczyk (Apr 7, 2004 8:36:48 PM)
How?

rrusczyk (Apr 7, 2004 8:36:57 PM)
(i.e. how do we know?)

probability1.01 (Apr 7, 2004 8:37:31 PM)
because the fly crawls on the surface, so the line is the most direct route

pi^2 (Apr 7, 2004 8:37:32 PM)
the problem asks for the shortest distance so the shortest distance between two points in a line segment

rrusczyk (Apr 7, 2004 8:37:37 PM)
We want the shortest path, and the shortest path between 2 points is a staight line.

justdudxit (Apr 7, 2004 8:37:56 PM)
when its on the surface, its a semi- ellipse right

rrusczyk (Apr 7, 2004 8:38:19 PM)
We don't necessarily know that. We do know that when we unfold, we have to have a straight line.

rrusczyk (Apr 7, 2004 8:38:33 PM)
We know that angle CVB = 135, so we can use the law of cosines:

rrusczyk (Apr 7, 2004 8:38:42 PM)
BC^2 = VB^2 + VC^2 - 2(VB)(VC) cos(CVB).

rrusczyk (Apr 7, 2004 8:38:53 PM)
Taking out the factor of 125, we have:

rrusczyk (Apr 7, 2004 8:39:05 PM)
(BC/125)^2 = 1 + 18 - 2(1)(3sqrt(2))(-sqrt(2)/2) = 19 + 6 = 25.

Pork_Chop8 (Apr 7, 2004 8:39:11 PM)
= 625

rrusczyk (Apr 7, 2004 8:39:13 PM)
Hence, BC = 625.

rrusczyk (Apr 7, 2004 8:39:31 PM)
A couple of interesting comments for you all to chew on. See if you can use the former to get to a solution:

rand()%0 (Apr 7, 2004 8:39:34 PM)
you can do distance formula without law of cosines, because VA is exactly diagonal, which means that 375sqrt2 divides nicely into a distance 375 horizontally and vertically from V

rand()%0 (Apr 7, 2004 8:39:36 PM)
It is interesting to note that the path actually travels closer to the vertex before going farther away

rrusczyk (Apr 7, 2004 8:40:03 PM)
12. Let ABCD be an isosceles trapezoid, whose dimensions are AB = 6, BC = 5 = DA, and CD = 4. Draw circles of radius 3 centered at A and B, and circles of radius 2 centered at C and D. A circle contained within the trapezoid is tangent to all four of these circles. Its radius is [-k + m*sqrt(n)]/p, where k, m, n, and p are positive integers, n is not divisible by the square of any prime, and k and p are relatively prime. Find k + m + n + p.

rrusczyk (Apr 7, 2004 8:40:10 PM)
//s3.amazonaws.com/classroom.artofproblemsolving.com/Classes/AIME/Images/2004aimeB12trap.gif

rrusczyk (Apr 7, 2004 8:40:24 PM)
Pretty scary. What should we add so we can approach this problem?

3cnfsat (Apr 7, 2004 8:40:58 PM)
Radii

rrusczyk (Apr 7, 2004 8:41:03 PM)
We'll need the center of the circle. We call our radius r, we know then that it's 2+r from C and D and 3+r from A and B, so we connect it to those points. We also go ahead and draw our altitude through the center, since that will give us right triangle to Pythagorize.

rrusczyk (Apr 7, 2004 8:41:07 PM)
//s3.amazonaws.com/classroom.artofproblemsolving.com/Classes/AIME/Images/2004aimeB12pty.gif

rrusczyk (Apr 7, 2004 8:41:23 PM)
Now what?

rand()%0 (Apr 7, 2004 8:41:30 PM)
the altitude is easy

rrusczyk (Apr 7, 2004 8:41:34 PM)
What is the altitude?

no_one_2000 (Apr 7, 2004 8:41:58 PM)
sqrt(24)

rand()%0 (Apr 7, 2004 8:42:01 PM)
sqrt24

3cnfsat (Apr 7, 2004 8:42:03 PM)
sqrt(24)

rrusczyk (Apr 7, 2004 8:42:06 PM)
The altitude is 2sqrt(6) (we can see this by dropping an altitude from D to form a right triangle with hypotenuse 5 and leg 1).

rrusczyk (Apr 7, 2004 8:42:22 PM)
What else can we do? We want r.

rrusczyk (Apr 7, 2004 8:43:41 PM)
We have right triangles, right?

rrusczyk (Apr 7, 2004 8:44:27 PM)
We have right triangles, so what might we use?

Pork_Chop8 (Apr 7, 2004 8:44:41 PM)
pythagorean theorem

wheezy81 (Apr 7, 2004 8:44:44 PM)
[ythagorean therom...

rrusczyk (Apr 7, 2004 8:44:55 PM)
Thank you. What do we get from triangle EDY?

Pork_Chop8 (Apr 7, 2004 8:46:11 PM)
(r + 2)^2 = 2^2 + (EY)^2

rrusczyk (Apr 7, 2004 8:46:34 PM)
EY^2 + DY^2 = DE^2, or EY^2 + 4 = (2+r)^2.

rrusczyk (Apr 7, 2004 8:46:40 PM)
What about EAX?

Mr.Ocax (Apr 7, 2004 8:47:35 PM)
3+r, 3, EX

Pork_Chop8 (Apr 7, 2004 8:47:38 PM)
(r + 3)^2 = 3^2 +(YX - EY)^2

justdudxit (Apr 7, 2004 8:47:42 PM)
EX^2 + 9 = (3+ r)^2

rrusczyk (Apr 7, 2004 8:47:45 PM)
AX^2 + EX^2 = AE^2, or EX^2 + 9 = (3+r)^2.

rrusczyk (Apr 7, 2004 8:47:57 PM)
Let y = EY, x = EX. Do we know anything about x and/or y?

Pork_Chop8 (Apr 7, 2004 8:48:21 PM)
x + y = sqrt24

Mr.Ocax (Apr 7, 2004 8:48:23 PM)
x+y=sqrt24

rrusczyk (Apr 7, 2004 8:48:26 PM)
We know that x + y = height of the trapezoid, which equals 2sqrt(6) (we can see this by dropping an altitude from D to form a right triangle with hypotenuse 5 and leg 1).

rrusczyk (Apr 7, 2004 8:48:31 PM)
Thus, we have 3 equations:

rrusczyk (Apr 7, 2004 8:48:35 PM)
y^2 + 4 = (2+r)^2 x^2 + 9 = (3+r)^2 x + y = 2sqrt(6)

rrusczyk (Apr 7, 2004 8:48:39 PM)
Any suggestions how to solve this system?

Pork_Chop8 (Apr 7, 2004 8:49:53 PM)
x^2 - y^2 = 2r

rrusczyk (Apr 7, 2004 8:50:01 PM)
Seeing that x+y, we think to subtract the first equation from the second so as to use difference of squares (and eliminate r^2):

rrusczyk (Apr 7, 2004 8:50:06 PM)
(x^2-y^2) + 5 = (3+r)^2 - (2+r)^2 = 5 +2r.

Pork_Chop8 (Apr 7, 2004 8:50:12 PM)
(x + y)(x - y) = 2r

Pork_Chop8 (Apr 7, 2004 8:50:15 PM)
(sqrt24)(x - y) = 2r

rrusczyk (Apr 7, 2004 8:50:21 PM)
Hence, (x-y)(x+y) = 2r, or

rrusczyk (Apr 7, 2004 8:50:30 PM)
r = (x-y)*sqrt(6)

rrusczyk (Apr 7, 2004 8:50:35 PM)
Now what?

Pork_Chop8 (Apr 7, 2004 8:51:51 PM)
add x-y to x + y and get 2x = sqrt24 + r/(sqrt6)

rrusczyk (Apr 7, 2004 8:51:59 PM)
We want r, so if we could find x or y in terms of r, we'd be done (since we could substitute into one of our equations above).

rrusczyk (Apr 7, 2004 8:52:03 PM)
We have x + y = 2sqrt(6), so we can find x - y in terms of r and add the equations:

rrusczyk (Apr 7, 2004 8:52:08 PM)
x - y = r/sqrt(6), so 2x = 2sqrt(6) + r/sqrt(6). Hence, x = sqrt(6) + r/[2sqrt(6)].

rrusczyk (Apr 7, 2004 8:52:17 PM)
Now:

wheezy81 (Apr 7, 2004 8:52:20 PM)
substitution

rrusczyk (Apr 7, 2004 8:52:37 PM)
From above, we have

rrusczyk (Apr 7, 2004 8:52:50 PM)
(sqrt(6) + r/[2sqrt(6)])^2 + 9 = (3+r)^2

rrusczyk (Apr 7, 2004 8:53:01 PM)
After we work through some algebra, what do we get?

Pork_Chop8 (Apr 7, 2004 8:53:54 PM)
23r^2 + 120r - 144 = 0

rrusczyk (Apr 7, 2004 8:53:59 PM)
Expanding, we have:

rrusczyk (Apr 7, 2004 8:54:03 PM)
6 + r + r^2/24 = 6r + r^2, or

rrusczyk (Apr 7, 2004 8:54:06 PM)
23r^2 + 120r - 144 = 0.

MCrawford (Apr 7, 2004 8:54:08 PM)
Here is a solution 3cnfsat came up with:

rrusczyk (Apr 7, 2004 8:54:15 PM)
Solve for r:

rrusczyk (Apr 7, 2004 8:54:20 PM)
r = (-120 +/- sqrt(120^2 + 4(23)(144))) / 2(23)

rrusczyk (Apr 7, 2004 8:54:34 PM)
How do we simplify that nasty radical?

Pork_Chop8 (Apr 7, 2004 8:55:00 PM)
factor our 24^2

pi^2 (Apr 7, 2004 8:55:06 PM)
factor out as much as possible, which ends up being 2^6*3^2

rrusczyk (Apr 7, 2004 8:55:12 PM)
So we have to simplify that radical:

rrusczyk (Apr 7, 2004 8:55:16 PM)
Sqrt(120^2 + 4(23)(144)) = 12sqrt(10^2 + 4(23)) = 24sqrt(5^2 + 23) = 4*24sqrt(3).

rrusczyk (Apr 7, 2004 8:55:27 PM)
Hence, our r is (-60 + 48sqrt(3)) / 23 (where we have taken a 2 out of the top and bottom of our quadratic expression, and clearly we want the positive root.

rrusczyk (Apr 7, 2004 8:55:36 PM)
Any questions about that?

rand()%0 (Apr 7, 2004 8:56:00 PM)
60+48+3+23=134

rrusczyk (Apr 7, 2004 8:56:02 PM)
Right.

rrusczyk (Apr 7, 2004 8:56:19 PM)
Here's how 3cn did it:

MCrawford (Apr 7, 2004 8:56:21 PM)
Here is a solution 3cnfsat came up with: Let the radius be x. sqrt(x^2 + 4x) + sqrt(x^2 + 6x) = 2sqrt(6) x^2 + 4x + x^2 + 6x + 2sqrt(x^4 + 10x^3 + 24x^2) = 24 (x^2 + 5x - 12)^2 = x^4 + 10x^3 + 24x^2 23x^2 + 120x - 144 = 0.

rrusczyk (Apr 7, 2004 8:57:24 PM)
(This is basically the same as our approach, but they just solved the equations in a different way - see if you can see why)

rrusczyk (Apr 7, 2004 8:57:31 PM)
13. Let ABCDE be a convex pentagon with AB || CE, BC || AD, AC || DE, < ABC = 120 degrees, AB = 3, BC = 5, and DE = 15. Given that the ratio between the area of triangle ABC and the area of triangle EBD is m/n, where m and n are relatively prime positive integers, find m + n.

rrusczyk (Apr 7, 2004 8:57:37 PM)
//s3.amazonaws.com/classroom.artofproblemsolving.com/Classes/AIME/Images/2004aimeB13pen.gif

rrusczyk (Apr 7, 2004 8:57:44 PM)
OK, that pentagon clearly isn't enough. What lines should we add?

MithsApprentice (Apr 7, 2004 8:58:41 PM)
how bout some of those parallels?

rand()%0 (Apr 7, 2004 8:58:47 PM)
AD, CE, AC

rand()%0 (Apr 7, 2004 8:58:50 PM)
parallels

rrusczyk (Apr 7, 2004 8:58:53 PM)
We should add the lines we know are parallel:

rrusczyk (Apr 7, 2004 8:59:03 PM)
(FYI, this a good example of a problem in which thinking about how to construct the diagram (forgetting the side lengths for a moment), makes solving the problem much easier.)

rrusczyk (Apr 7, 2004 8:59:12 PM)
//s3.amazonaws.com/classroom.artofproblemsolving.com/Classes/AIME/Images/2004aimeB13diags.gif

rrusczyk (Apr 7, 2004 8:59:17 PM)
In building this, what do we notice?

rand()%0 (Apr 7, 2004 8:59:51 PM)
DXE=120

3cnfsat (Apr 7, 2004 8:59:53 PM)
We have three similar triangles

rrusczyk (Apr 7, 2004 9:00:00 PM)
What triangles are similar?

wheezy81 (Apr 7, 2004 9:01:00 PM)
acx~exd

justdudxit (Apr 7, 2004 9:01:07 PM)
ABC~ACX~ XED

rrusczyk (Apr 7, 2004 9:01:11 PM)
We have EDX ~ ACX ~ CAB.

rrusczyk (Apr 7, 2004 9:01:21 PM)
What else?

justdudxit (Apr 7, 2004 9:01:24 PM)
AX = BC, AB = XC

rrusczyk (Apr 7, 2004 9:01:26 PM)
Why?

3cnfsat (Apr 7, 2004 9:01:45 PM)
parallel sides give us ABCX = parallelogram

rand()%0 (Apr 7, 2004 9:01:48 PM)
parallogram

MithsApprentice (Apr 7, 2004 9:01:51 PM)
we have parallelogram ABCX

rrusczyk (Apr 7, 2004 9:01:53 PM)
We notice that AXCB is a parallelogram. This may be useful.

rand()%0 (Apr 7, 2004 9:01:59 PM)
we can find AC by law of cosines,

rrusczyk (Apr 7, 2004 9:02:03 PM)
What do we get?

3cnfsat (Apr 7, 2004 9:02:12 PM)
AC = 7

rand()%0 (Apr 7, 2004 9:02:15 PM)
AC=7

rrusczyk (Apr 7, 2004 9:02:16 PM)
AC^2 = 9 + 25 - 2(3)(5)(-1/2) = 34 + 15 = 49, so AC = 7.

rrusczyk (Apr 7, 2004 9:02:25 PM)
All right, we have a lot of information now.

rrusczyk (Apr 7, 2004 9:02:30 PM)
We wish to find the ratio [ABC]/[EBD], where [ABC] is the area of ABC.

rrusczyk (Apr 7, 2004 9:02:35 PM)
How are we going to find this ratio?

MPS-vras (Apr 7, 2004 9:03:40 PM)
use heights, three pieces for height of EBD

3cnfsat (Apr 7, 2004 9:03:43 PM)
compare altitudes

probability1.01 (Apr 7, 2004 9:03:49 PM)
Altitude of ABC/ Altitude of EBD * Base of ABC/Base of EBD

rrusczyk (Apr 7, 2004 9:04:04 PM)
We can find [ABC], but [EBD] looks pretty hard.

rrusczyk (Apr 7, 2004 9:04:10 PM)
Since ED || AC, we can find the ratio of areas by finding the ratio AC/ED and the ratio of the altitudes to these sides (we can always find a ratio of areas this way; we think to use this approach here since we have similarities which may help us greatly).

rrusczyk (Apr 7, 2004 9:04:22 PM)
How do we get the ratio of altitudes?

3cnfsat (Apr 7, 2004 9:05:05 PM)
Let h be the altitude from b of ABC. Then we get (h+h+ 15/7 h) as EBD's altitude by similar triangles.

probability1.01 (Apr 7, 2004 9:05:07 PM)
for the three triangles, it's 7:7:15, so it's 7: 29 (the total)

rrusczyk (Apr 7, 2004 9:05:12 PM)
AC/ED = 7/15.

rrusczyk (Apr 7, 2004 9:05:20 PM)
We know that the altitude from B to AC equals that from X to AC, and that from X to ED is 15/7 the distance from X to AC (since XAC ~ XDE). Hence, the altitude from B to ED is 1+1+15/7 = 29/7 of the altitude from B to AC.

rrusczyk (Apr 7, 2004 9:05:25 PM)
So, what's our answer?

probability1.01 (Apr 7, 2004 9:06:09 PM)
49/435

rrusczyk (Apr 7, 2004 9:06:12 PM)
(ratio of bases)*(ratio of altitudes) = (7/15)(7/29) = 49/435

rrusczyk (Apr 7, 2004 9:06:18 PM)
So our answer is 484.

MCrawford (Apr 7, 2004 9:06:43 PM)
14. Consider a string of n 7's, 7 7 7 7 . . . 7 7, into which + signs are inserted to produce an arithmetic expression. For example, 7 + 77 + 777 + 7 + 7 = 875 could be obtained from eight 7's in this way. For how many values of n is it possible to insert + signs so that the resulting expression has value 7000?

MCrawford (Apr 7, 2004 9:06:49 PM)
//s3.amazonaws.com/classroom.artofproblemsolving.com/Classes/AIME/Images/2004aimeB14Summing7.gif

MCrawford (Apr 7, 2004 9:07:19 PM)
First, I bet a lot of students worked this problem and thought "wow, this is easy for a 14". We shall see...

MCrawford (Apr 7, 2004 9:07:26 PM)
How might we approach this problem?

Pork_Chop8 (Apr 7, 2004 9:07:31 PM)
factor out 7 and get sum of 1, 11, 111, etc to equal 1000

rand()%0 (Apr 7, 2004 9:07:34 PM)
reduce the problem down to 1000 and 1s, divide everything by 7

MCrawford (Apr 7, 2004 9:07:41 PM)
Before we do anything particularly mathematical, we should notice that the number 7 is not special in this problem in any way. We could just as easily take strings of n 1's, add + signs in the same places and the sum should come out to 1000 (if it came out to 7000 with 7's). Now we have given ourselves a slightly easier problem to work with.

MCrawford (Apr 7, 2004 9:07:55 PM)
Now, how can we take the information at hand and mold it into mathematical statements with which we can work?

Pork_Chop8 (Apr 7, 2004 9:08:52 PM)
multiply by 9 because 9, 99, 999, 9999 can be expressesed as 10^n -1

MCrawford (Apr 7, 2004 9:08:52 PM)
Very interesting approach! I can see how this could make the problem a little easier, but I'll walk down my slightly slower path for now.

justdudxit (Apr 7, 2004 9:09:09 PM)
find all solutions to 111x + 11y + z = 1000

rand()%0 (Apr 7, 2004 9:09:14 PM)
we can't use 1111, it's too big, so we only use 3 numbers, 1, 11, and 111.

MCrawford (Apr 7, 2004 9:09:23 PM)
Do we have only one equation to work with?

MCrawford (Apr 7, 2004 9:10:34 PM)
Can we relate x, y, and z to anything else?

justdudxit (Apr 7, 2004 9:11:27 PM)
3x + 2y +z = n

probability1.01 (Apr 7, 2004 9:11:36 PM)
3x+2y+z = n

MCrawford (Apr 7, 2004 9:11:39 PM)
We can call the number of 111's in a string a, the number of 11's in a string b, and the number of 1's in a string c. Since the sum must be 1000, we know that a string with sum 1000 will have only 1's, 11's, and 111's.

MCrawford (Apr 7, 2004 9:11:45 PM)
Since we can count the number of 1's in the string by counting the number of 1's in 1's, 11's, and 111's, we can now express n in terms of a, b, and c: 3a + 2b + c = n.

MCrawford (Apr 7, 2004 9:11:51 PM)
We can also express the sum (for the cases in which we are interested) in terms of a, b, and c: 111a + 11b + c = 1000.

MCrawford (Apr 7, 2004 9:11:57 PM)
How can we use the equations we have conjured?

Pork_Chop8 (Apr 7, 2004 9:12:22 PM)
1000 - n must be divisible by 9

MCrawford (Apr 7, 2004 9:12:31 PM)
It's never a bad idea to eliminate a variable from a system of equations just to see if it makes the equations easier to work with (it almost always does). Here we can take the difference of our two equations to get rid of c: 108a + 9b = 1000 - n.

MCrawford (Apr 7, 2004 9:12:42 PM)
At a first glance this equation might not look all that interesting, but then we notice that the left hand side is a multiple of 9.

MCrawford (Apr 7, 2004 9:12:50 PM)
We now know that 1000 - n must be a multiple of 9.

MCrawford (Apr 7, 2004 9:13:02 PM)
We could also have arrived at this fact by considering digit sums.

Pork_Chop8 (Apr 7, 2004 9:13:26 PM)
n = 1 mod 9????

MCrawford (Apr 7, 2004 9:13:28 PM)
The sum of the digits of any string is n, so n :=: 1000 (mod 9).

rand()%0 (Apr 7, 2004 9:13:46 PM)
max value of n is obviously 1000

MCrawford (Apr 7, 2004 9:13:56 PM)
We can place bounds on n by considering the largest and smallest number of 1's that we can use to make 1000. Obviously n is maximal when there is simply a string of 1000 1's added together. When is n minimal?

rand()%0 (Apr 7, 2004 9:14:15 PM)
when we use 9 111s and the leftover 1--28

MCrawford (Apr 7, 2004 9:14:24 PM)
The quickest way to sum to 1000 is using large numbers for as much of the sum as we can: 9(111) + 1 = 1000. Here we use 9 111's and a 1. This is a total of 28 1's in the string.

MCrawford (Apr 7, 2004 9:14:33 PM)
Do we have enough information to solve the problem?

rand()%0 (Apr 7, 2004 9:15:01 PM)
as long as we can show that every number (=1mod9) between 28 and 1000 can be achieved

MCrawford (Apr 7, 2004 9:15:12 PM)
We know that 1000 - n must be a multiple of 9, so n is 1 more than a multiple of 9. We know that n is at least 28 and at most 1000. If every number in the form 9k + 1 (3 <= k <= 111), then we are done. Does every such number yield a string of 1's that we can manipulate with + signs into a sum of 1000?

probability1.01 (Apr 7, 2004 9:15:16 PM)
which is not true

probability1.01 (Apr 7, 2004 9:15:21 PM)
for example, 37 can not

MCrawford (Apr 7, 2004 9:15:30 PM)
In order to determine if every k from 3 to 111 yields an n = 9k + 1 that works, we must examine the ways that we can add to k while maintaining the sum. In what ways can we do this?

pi-girl (Apr 7, 2004 9:17:11 PM)
look at possible numbers of 111's, and for each of these, possible numbers of 11's

MCrawford (Apr 7, 2004 9:17:38 PM)
How can we break up a 111 into smaller pieces so as to increase the number of 1's by the smallest amount?

3cnfsat (Apr 7, 2004 9:17:50 PM)
11 = 11 * 1 gains us 9, 111 = 10 * 11 +1 gains us 18, 111 = 111* 1 gains us 108

MCrawford (Apr 7, 2004 9:18:01 PM)
We can break 111 up into 10 11's and a 1. This takes 3 1's and replaces them by 21 1's. This is a jump of 18 1's.

MCrawford (Apr 7, 2004 9:18:11 PM)
We can break an 11 up into 11 1's. This takes 2 1's and replaces them by 11 1's. This is a jump of 9 1's.

MCrawford (Apr 7, 2004 9:18:26 PM)
These are all ways we have to break up and reconstruct the chains of 1's and any other way is simply a combination of these processes. Now, how can we count the number of k from 3 to 111 that give us n = 9k + 1 that works?

probability1.01 (Apr 7, 2004 9:18:55 PM)
start at the extreme

MCrawford (Apr 7, 2004 9:19:11 PM)
Let's start at k = 3. What do we do from there?

probability1.01 (Apr 7, 2004 9:20:01 PM)
k=3 works, so maybe check k=4

MCrawford (Apr 7, 2004 9:20:07 PM)
Sure, but how do we check?

Pork_Chop8 (Apr 7, 2004 9:20:51 PM)
replace an 11 with 11 1's

MCrawford (Apr 7, 2004 9:20:55 PM)
What 11?

rand()%0 (Apr 7, 2004 9:21:02 PM)
using only 8 111s, and the maximum number of 11s, the minimum value of n is 46

MCrawford (Apr 7, 2004 9:21:10 PM)
We start where k = 3, so n = 28. We use these 28 1's by adding 9 111's and a 1. When we break one of the 111's up into 10 11's and a 1, we add 18 1's. This is the least number we can add, so n = 46 is the next possible n. This means k = 4 did not yield a solution. This is the major wrinkle in this problem - we couldn't guarantee that n could always jump by 9.

MCrawford (Apr 7, 2004 9:21:29 PM)
Now, are there any other k that we must remove from our list?

rand()%0 (Apr 7, 2004 9:21:35 PM)
all of the other cases should overlap

MCrawford (Apr 7, 2004 9:21:42 PM)
How do we know?

MCrawford (Apr 7, 2004 9:23:18 PM)
We can break up an 11 into 1's an make n jump by 9 (k by 1). How do we use this fact to show that all k from 5 to 101 yield n that work?

probability1.01 (Apr 7, 2004 9:23:32 PM)
because k=5 works, and when we have to lose another 111, we should have enough 11's to do the job (a very non-rigorous idea)

MCrawford (Apr 7, 2004 9:23:43 PM)
Note that we only need to skip a k when we need to break up a 111.

MCrawford (Apr 7, 2004 9:23:56 PM)
We only need to break up a 111 when there is no 11 in any sum for that n. If we could break an 11 up, then we could add 9 to n and still get a sum of 1000.

MCrawford (Apr 7, 2004 9:24:09 PM)
If we have broken up a 111 and there are no 11's, then there are at least 112 1's. These 1's save us from have to skip another k because even as we break up another 111, we can also "recompose" another 11 from 1's. This means n jumps by 18, but falls back by 9. In this way we can keep increasing n by 9 (k by 1) until n = 1000 (k = 111). Our final answer is thus 111 - 2 - 1 = 108.

MCrawford (Apr 7, 2004 9:24:35 PM)
Before we go on to the last problem I would like to point out something I have noticed with the AIME.

MCrawford (Apr 7, 2004 9:25:00 PM)
Years ago the AIME involved finding an elegant approach and cracking the problem open. Most casework was straight forward.

MCrawford (Apr 7, 2004 9:25:19 PM)
These days there seem to be more algorithmic problems that require you to see little wrinkles in the solutions.

MCrawford (Apr 7, 2004 9:25:25 PM)
15 on the first AIME was like that.

MCrawford (Apr 7, 2004 9:25:30 PM)
As was this 14.

MCrawford (Apr 7, 2004 9:25:48 PM)
Be aware and solve the problems like they were Olympiad problems.

MCrawford (Apr 7, 2004 9:26:06 PM)
I didn't notice the wrinkle on 14 until I was writing this script 2 hours ago.

MCrawford (Apr 7, 2004 9:26:32 PM)
Walking through the math is extremely important -- even when you basically know how the problem works -- you sometimes find a bump in the road.

MCrawford (Apr 7, 2004 9:26:39 PM)
15. A long thin strip of paper is 1024 units in length, 1 unit in width, and is divided into 1024 unit squares. The paper is folded in half repeatedly. For the first fold, the right end of the paper is folded over to coincide with and lie on top of the left end. The result is a 512 by 1 strip of double thickness. Next, the right end of this strip is folded over to coincide with and lie on top of the left end, resulting in a 256 by 1 strip of quadruple thickness. This process is repeated 8 more times. After the last fold, the strip has become a stack of 1024 unit squares. How many of these squares lie below the square that was originally the 942nd square counting from the left?

MCrawford (Apr 7, 2004 9:26:45 PM)
//s3.amazonaws.com/classroom.artofproblemsolving.com/Classes/AIME/Images/2004aimeB15PaperFolding.gif

MCrawford (Apr 7, 2004 9:26:56 PM)
First, we all know the AIME committee screwed up with this problem.

MCrawford (Apr 7, 2004 9:27:17 PM)
Yes, the AIME committee botched this one pretty badly. We all know that it's impossible to fold a sheet of paper more than 7 times. Try it!

MCrawford (Apr 7, 2004 9:27:28 PM)
Now, what kind of problem does this look like?

justdudxit (Apr 7, 2004 9:28:03 PM)
a working backwards problem

MCrawford (Apr 7, 2004 9:28:15 PM)
You can work it that way, but it's not necessary.

timhlu (Apr 7, 2004 9:28:34 PM)
recursive?

MCrawford (Apr 7, 2004 9:28:51 PM)
Well, sort of, but it's not easy to define that way.

MithsApprentice (Apr 7, 2004 9:28:55 PM)
a 1-step-at-a-time problem

MCrawford (Apr 7, 2004 9:29:16 PM)
I mean before all that -- how are we looking at the units?

MPS-vras (Apr 7, 2004 9:29:46 PM)
binary

MCrawford (Apr 7, 2004 9:29:53 PM)
If it quacks like a binary number problem . . . How can we use binary number to aide us?

rand()%0 (Apr 7, 2004 9:30:50 PM)
do you mean binary numbers as 1s and 0s or just powers of two? because I used base 10 the whole time

MithsApprentice (Apr 7, 2004 9:30:55 PM)
hmm...are we looking at sums of powers of 2?

MCrawford (Apr 7, 2004 9:31:20 PM)
How does the binary representation of each number relate to how they paper is folded?

hypercube (Apr 7, 2004 9:31:52 PM)
there is a pattern....

MCrawford (Apr 7, 2004 9:31:56 PM)
What is it?

3cnfsat (Apr 7, 2004 9:32:06 PM)
If the 2^9 digit is 0, the number x stays where it is - otherwise you change 1s to 0s and 0s to 1s.

MCrawford (Apr 7, 2004 9:32:11 PM)
At a first glance it might appear that letting each unit represent itself with its binary representation would make the problem easiest. What's wrong with this approach?

MCrawford (Apr 7, 2004 9:33:29 PM)
The problem is that the last unit would be the only unit represented by an 11 digit binary number. This would require us to make special considerations and perhaps track some ugly wrinkle throughout the entire problem. Is there an easier way we can deal with this?

rcv (Apr 7, 2004 9:34:24 PM)
Number the squares 0 to 1023, not 1 to 1024!

MCrawford (Apr 7, 2004 9:34:33 PM)
If we subtract 1 from each unit number we get 0 - 1023. This makes us happy because we can now represent each unit number as a 10 digit binary string. Now, how do we approach the problem of tracking the 942nd unit?

rand()%0 (Apr 7, 2004 9:34:53 PM)
it's new number is 941

MCrawford (Apr 7, 2004 9:35:00 PM)
The 942nd square is now labeled as the binary form of 942 - 1 = 941 which is 1110101101. How do we track this unit through the folds?

3cnfsat (Apr 7, 2004 9:35:12 PM)
I think the shifting 1s to 0s is for 0...1023 numbering: think of 2 digits - 00,01,10,11

MCrawford (Apr 7, 2004 9:35:12 PM)
Yes, you had the idea for after the shift.

rand()%0 (Apr 7, 2004 9:35:16 PM)
if it's greater than half the number of squares, so when it's first digit is a one

MCrawford (Apr 7, 2004 9:35:52 PM)
We must consider what each fold does. The first folds takes 512 - 1023 and stacks them on top of 511 - 0. The second fold takes the stacks over 256 - 511 and stacks them on 255 - 0. How can we describe this process?

rand()%0 (Apr 7, 2004 9:37:04 PM)
we don't have to keep track of all 1024 squares, just number 941, which means it's horizontal and vertical position, two ways each, so from the left, right, top, and bottom (the duality is useful for when it's folded)

MCrawford (Apr 7, 2004 9:37:08 PM)
Each fold takes the numbers above each stack whose bottom unit is 2^n to 2^(n+1) - 1, and inverts those stacks while placing them on stacks 2^n - 1 to 0 such that the sum of the bottom number in an old stack and the bottom number in a stack that got stacked on is 2^(n+1) - 1.

MCrawford (Apr 7, 2004 9:37:24 PM)
Consider the example after 6 folds when 16 stacks remain. The seventh fold does the following: Piles stack 1111 on stack 0000 with stack 1111 inverting in order. Piles stack 1110 on stack 0001 with stack 1110 inverting in order. Piles stack 1101 on stack 0010 with stack 1110 inverting in order. Piles stack 1100 on stack 0011 with stack 1110 inverting in order. Piles stack 1011 on stack 0100 with stack 1110 inverting in order. Piles stack 1010 on stack 0101 with stack 1110 inverting in order. Piles stack 1001 on stack 0110 with stack 1110 inverting in order. Piles stack 1000 on stack 0111 with stack 1110 inverting in order.

MCrawford (Apr 7, 2004 9:37:44 PM)
If the bottom number begins with a 0, then that stack doesn't move, but has a stack piled on top of it. If the bottom number begins with a 1, then that stack gets inverted and piled on the stack where the bottom number has all different digits from the bottom number of the stack getting piled on top of it.

MCrawford (Apr 7, 2004 9:38:00 PM)
How can we use this process to track unit 1110101101?

MCrawford (Apr 7, 2004 9:39:56 PM)
We can walk through a series of folds all the way to the end. Before the first fold, unit 1110101101 is in stack 1110101101 and is 1st from the bottom. Where is it after the first fold?

rand()%0 (Apr 7, 2004 9:40:19 PM)
we reverse the ones and zeros after each fold and add one

MCrawford (Apr 7, 2004 9:40:24 PM)
1110101101 begins with a 1, so it is folded over to stack 0001010010 and is 2nd from the bottom. Where is it after the second fold?

justdudxit (Apr 7, 2004 9:40:38 PM)
on top of 0001010010

MCrawford (Apr 7, 2004 9:40:45 PM)
We now only consider the last 9 digits of the stack numbers, so we are examining stack 001010010. This stack begins with a 0, so it isn't folded. However, 2 more units were piled on it, so our original unit is now 2nd from the bottom in a stack of 4.

MCrawford (Apr 7, 2004 9:40:59 PM)
We continue like this...

rand()%0 (Apr 7, 2004 9:41:07 PM)
it doesn't get folded, and remember to reduce the digits

MCrawford (Apr 7, 2004 9:41:09 PM)
After fold 3, 01010010 doesn't move, so our unit is number 2 in a stack of 8. After fold 4, 1010010 folds to 0101101, so our unit is 17 - 2 = 15 in a stack of 16. After fold 5, 101101 folds to 010010, so our unit is 33 - 15 = 18 in a stack of 32. After fold 6, 10010 folds to 01101, so our unit is 65 - 18 = 47 in a stack of 64. After fold 7, 1101 folds to 0010, so our unit is 129 - 47 = 82 in a stack of 128. After fold 8, 010 doesn't move, so our unit is 82 in a stack of 256. After fold 9, 10 folds to 01, so our unit is 513 - 82 = 431 in a stack of 512. After fold 10, 1 folds to 0, so our unit is 1025 - 431 = 594 in a stack of 1024.

MCrawford (Apr 7, 2004 9:41:33 PM)
Be careful to answer the question that is asked. Our final answer is 593 which is the number of units below the unit that was originally 942nd from the left.

MCrawford (Apr 7, 2004 9:42:09 PM)
This is an example as to how isomorphic relationships can help us visualize a problem better.