MCrawford (Mar 24, 2004 7:03:17 PM)
1. The digits of a positive integer n are four consecutive integers in decreasing order when read from left to right. What is the sum of the possible remainders when n is divided by 37?

dgf (Mar 24, 2004 7:03:49 PM)
I'd write out the numbers

justdudxit (Mar 24, 2004 7:04:00 PM)
The numbers range from 3210 to 9876

MCrawford (Mar 24, 2004 7:04:06 PM)
The only numbers we have to consider are the 7 numbers 3210, 4321,…, 9876 Can we find their remainders when divided by 37 easily?

The_Cow_King (Mar 24, 2004 7:04:21 PM)
realize that 37 is a factor of 111, and also that u can mod 1110 out

ml2 (Mar 24, 2004 7:04:24 PM)
find all the numbers which aer under that condition looking at 3210 we get remainder 28, now adding 1111, remainder gets bigger by 1

z9R4C3 (Mar 24, 2004 7:04:47 PM)
217. note that 111 is divisible by 37. 3210, 4321, 5432 all increase by one in mod 37. 28, 29, 30, ...etc. 34

ml2 (Mar 24, 2004 7:05:00 PM)
adding up 28+29.....+34=31*7=217

MCrawford (Mar 24, 2004 7:05:10 PM)
Any questions about this problem?

MCrawford (Mar 24, 2004 7:05:22 PM)
2. Set A consists of m consecutive integers whose sum is 2m, and set B consists of 2m consecutive integers whose sum is m. The absolute value of the difference between the greatest element of A and the greatest element of B is 99. Find m.

MCrawford (Mar 24, 2004 7:05:36 PM)
How can we approach this problem?

Idiot_without_a_village (Mar 24, 2004 7:05:50 PM)
Averages

darrenhe (Mar 24, 2004 7:05:53 PM)
figure out the pattern

cold entrée (Mar 24, 2004 7:05:56 PM)
The median of set A is 1/2 and the median of set B is 2

MCrawford (Mar 24, 2004 7:06:20 PM)
What are the numbers in each set?

dts (Mar 24, 2004 7:06:58 PM)
we can express set a as x, x+1, x+2... x+2m-1, and y, y+1... y+m-1

MCrawford (Mar 24, 2004 7:07:10 PM)
We could do that, but cold entree has given us a shortcut.

MCrawford (Mar 24, 2004 7:07:40 PM)
How can we list the numbers in each set?

ml2 (Mar 24, 2004 7:08:19 PM)
working from median (m/2, or m)

Surreality (Mar 24, 2004 7:08:23 PM)
with x in the middle and numbers on both sides

MCrawford (Mar 24, 2004 7:08:49 PM)
We examine each of the sets and notice that the mean of the numbers in A is 2 and the mean of those in B is 1/2.

bookworm271828 (Mar 24, 2004 7:08:53 PM)
-2m-1, -2m, -2m+1, . . . 2m-2, 2m

MCrawford (Mar 24, 2004 7:09:03 PM)
Oops, not quite.

MCrawford (Mar 24, 2004 7:09:07 PM)
What will be the numbers in A?

dts (Mar 24, 2004 7:10:21 PM)
starting in the middle, the terms of a are 1, 2, 3,...1+(m-1)/2

MCrawford (Mar 24, 2004 7:10:32 PM)
Is this correct?

Hexahedron (Mar 24, 2004 7:10:43 PM)
2 is the middle term

MCrawford (Mar 24, 2004 7:10:51 PM)
How many numbers larger than 2?

ml2 (Mar 24, 2004 7:11:05 PM)
m-1/2

MCrawford (Mar 24, 2004 7:11:10 PM)
That's (m-1)/2

MCrawford (Mar 24, 2004 7:11:27 PM)
So, what is the largest number in A?

ml2 (Mar 24, 2004 7:11:45 PM)
(m+3)/2

Mr.Ocax (Mar 24, 2004 7:11:48 PM)
2+(m-1)/2

MCrawford (Mar 24, 2004 7:11:53 PM)
The m numbers in A must be 2 - (m-1)/2, 2 - (m-3)/2, …, 1, 2, 3,…, 2 + (m-3)/2, 2 + (m-1)/2.

MCrawford (Mar 24, 2004 7:12:27 PM)
The mean (and thus median) of B is 1/2. How many of the numbers in B will be larger than 1/2?

ml2 (Mar 24, 2004 7:12:40 PM)
m

MCrawford (Mar 24, 2004 7:12:48 PM)
So, what is the largest number in B?

bookworm271828 (Mar 24, 2004 7:13:08 PM)
m

MCrawford (Mar 24, 2004 7:13:15 PM)
The 2m numbers in B must be -m + 1, -m + 2,…, 0, 1, 2,…, m - 2, m -1, m.

MCrawford (Mar 24, 2004 7:13:26 PM)
How can we use these representations of the sets of numbers?

Idiot_without_a_village (Mar 24, 2004 7:14:06 PM)
well you know that the difference of the two largest values is 99

dgf (Mar 24, 2004 7:14:09 PM)
abs(m-(2+(m-1)/2))) = 99

MCrawford (Mar 24, 2004 7:14:16 PM)
How do we solve for m?

dgf (Mar 24, 2004 7:15:09 PM)
m has to be larger than (m-1)/2 + 2, so m-(2+(m-1)/2) = 99, or m = 201

MCrawford (Mar 24, 2004 7:15:12 PM)
We are told that the difference between the largest numbers in each set is 99, thus |m - (m+3)/2| = |(m-3)/2| = 99. Clearly m cannot be less than 3 to produce this difference so we solve the equation (m - 3)/2 = 99. m = 201.

MCrawford (Mar 24, 2004 7:15:40 PM)
As many of you have pointed out, we could also solve this as a system of equations, but this shortcut makes this a 1 minute problem.

MCrawford (Mar 24, 2004 7:15:50 PM)
3. A convex polyhedron P has 26 vertices, 60 edges, and 36 faces, 24 of which are triangular, and 12 of which are quadrilaterals. A space diagonal is a line segment connecting two non-adjacent vertices that do not belong to the same face. How many space diagonals does P have?

interesting_move (Mar 24, 2004 7:16:12 PM)
The 60 edges are extra along with 2x12 line segments, which are parts of the 12 quadrilaterals (the diagonals). Hence, we have 26C2-(60+24)=241 space diagonals.

Mr.Ocax (Mar 24, 2004 7:16:14 PM)
26!/2!24!-60 edges-24*2 for diagonals

MCrawford (Mar 24, 2004 7:16:28 PM)
We first note that there are C(26, 2) = 325 total segments connecting vertices.

MCrawford (Mar 24, 2004 7:16:36 PM)
We can find out how many are space diagonals by counting how many are not.

MCrawford (Mar 24, 2004 7:16:51 PM)
A segment will not be a space diagonal if it is either an edge or a face diagonal.

MCrawford (Mar 24, 2004 7:17:01 PM)
We are given that there are 60 edges. Only the quadrilateral faces have face diagonals and the each have 2.

MCrawford (Mar 24, 2004 7:17:06 PM)
325 - 60 - 2(12) = 241.

MCrawford (Mar 24, 2004 7:17:21 PM)
We examined this type of problem in both the Intro Counting and AMC/AIME courses this year.

rrusczyk (Mar 24, 2004 7:17:32 PM)
4. A square has sides of length 2. Set S is the set of all line segments that have length 2 and whose endpoints are on adjacent sides of the square. The midpoints of the line segments in set S enclose a region whose area to the nearest hundredth is k. Find 100k.

rrusczyk (Mar 24, 2004 7:17:36 PM)
Where do we start?

fuzzylogic (Mar 24, 2004 7:17:47 PM)
i found that the distance from the midpoint to the vertex is always one, therefore, the midpoints trace 4 quarter circles, and the area of the enclosed region is 4-pi

rrusczyk (Mar 24, 2004 7:17:58 PM)
Let's see how we'd get to that:

rrusczyk (Mar 24, 2004 7:17:58 PM)
Typically in locus problems we look for things which remain fixed as we vary whatever we're supposed to vary (the segments that make up S in this case.

rrusczyk (Mar 24, 2004 7:18:03 PM)
//s3.amazonaws.com/classroom.artofproblemsolving.com/Classes/AIME/Images/2004aimeA4fir.gif

rrusczyk (Mar 24, 2004 7:18:08 PM)
The diagram shows square ABCD. EF is one of the segments of S, and M its midpoint. What remains fixed as we slide E along AB?

Idiot_without_a_village (Mar 24, 2004 7:18:40 PM)
the distance of the midpoint to a vertex

cold entrée (Mar 24, 2004 7:18:44 PM)
the distance between M and B

rrusczyk (Mar 24, 2004 7:18:52 PM)
The distance BM = 1/2(EF) = 1, no matter where EF such that E is on AB and F on BC. Hence, what does M trace out?

justdudxit (Mar 24, 2004 7:19:05 PM)
quarter circle

htam (Mar 24, 2004 7:19:06 PM)
a quarter circle

rrusczyk (Mar 24, 2004 7:19:09 PM)
BM = 1 tells us that M traces out a quarter circle with center M, where the arc goes from the midpoint of AB to the midpoint of BC (it's pretty easy to see that every point on the arc is achievable). Hence, what is our desired region?

justdudxit (Mar 24, 2004 7:19:20 PM)
the star thing in the middle

Braggart Billy (Mar 24, 2004 7:19:24 PM)
the stuff minus the area of the four quarter circles

dgf (Mar 24, 2004 7:19:27 PM)
4-pi = .86

Surreality (Mar 24, 2004 7:19:29 PM)
it's 2*2-(4pi/4) which simplifies to 4-pi

dnbmathguy (Mar 24, 2004 7:19:34 PM)
4 - pi

rrusczyk (Mar 24, 2004 7:19:38 PM)
Our desired region is what's left of the square when the 4 quarter circles are cut out of the corner. This has area 4 - pi, so our answer is the integer nearest 100(4-pi), which is 86.

rrusczyk (Mar 24, 2004 7:19:52 PM)
If you didn't see the midpoint thing initially:

Idiot_without_a_village (Mar 24, 2004 7:19:54 PM)
another amateur approach would be to draw a few test lines and go from there if you couldn't think of that.

MCrawford (Mar 24, 2004 7:20:14 PM)
5. Alpha and Beta both took part in a two-day problem-solving competition. At the end of the second day, each had attempted questions worth a total of 500 points. Alpha scored 160 points out of 300 points attempted on the first day, and scored 140 points out of 200 points attempted on the second day. Beta who did not attempt 300 points on the first day, had a positive integer score on each of the two days, and Beta's daily success rate (points scored divided by points attempted) on each day was less than Alpha's on that day. Alpha's two-day success ratio was 300/500 = 3/5. The largest possible two-day success ratio that Beta could achieve is m/n, where m and n are relatively prime positive integers. What is m + n?

MCrawford (Mar 24, 2004 7:20:20 PM)
How can we approach this problem?

justdudxit (Mar 24, 2004 7:20:34 PM)
set up some inequalities

htam (Mar 24, 2004 7:20:41 PM)
the maximum rate on second day is better, so we need to max the second day trial attempts

dts (Mar 24, 2004 7:20:59 PM)
beta would do better to answer more problems on the second day, because alpha had a better average on that day

MCrawford (Mar 24, 2004 7:21:12 PM)
We can call the number of points Beta attempted on each day a_1 and a_2. We know that a_1 + a_2 = 500. We can call the number of points Beta scored c_1 and c_2.

MCrawford (Mar 24, 2004 7:21:18 PM)
We know that c_1/a_1 < 8/15. We know that c_2/a_2 < 7/10.

MCrawford (Mar 24, 2004 7:21:40 PM)
We know that c_1 < (8/15)(a_1) and c_2 < (7/10)(a_2).

dgf (Mar 24, 2004 7:21:48 PM)
she could have attempted 499 problems on day 2 and gotten 349 right, since 350/500 = 140/200

MCrawford (Mar 24, 2004 7:22:02 PM)
We notice that 7/10 > 8/15, so we could maximize c_1 + c_2 by making c_2 as large as possible (unless there are any slight wrinkles).

darrenhe (Mar 24, 2004 7:22:13 PM)
i reasoned that since Alpha's second day ratio was better, beta should just get 0/1 the first day and as many right as possible the second day

MCrawford (Mar 24, 2004 7:22:22 PM)
Beta can attempt at most 499 points on the second day. Of these, Beta can score at most 349 points since 349/499 < 7/10 < 350/499. This leaves Beta with 0 of 1 point attempted on the first day. Could Beta do better than 349 total points?

Hexahedron (Mar 24, 2004 7:22:41 PM)
"gets a positive integer scorce"

Hexahedron (Mar 24, 2004 7:22:45 PM)
She needs to do 2 problems on day 1

MCrawford (Mar 24, 2004 7:23:16 PM)
Oops, that was my first solution, but fortunately I get no points taken off because I'm an old old man now.

ml2 (Mar 24, 2004 7:23:24 PM)
1/2 on day one, and 348/498 on day 2, which is 349/500, irreducible so answer is 849

MCrawford (Mar 24, 2004 7:23:40 PM)
What is one way we know that 349 is the max total once we've found it?

dgf (Mar 24, 2004 7:24:13 PM)
if she got 350, then she would have 7/10, which means she must have had at least 7/10 on one of the days, which can't be

cats... (Mar 24, 2004 7:24:21 PM)
simson's (sp?) rule tells you you can have a worse avg on individual days but still have an overall better average, and you should do this by having that person have very low trials on one day, and then many trials on the other.

MCrawford (Mar 24, 2004 7:24:30 PM)
Any questions about this problem?

MCrawford (Mar 24, 2004 7:24:56 PM)
6. An integer is called snakelike if its decimal representation a_1a_2a_3…a_k satisfies a_i < a_(i+1) if i is odd and a_i > a_(i+1) if i is even. How many snakelike integers between 1000 and 9999 have four distinct digits?

MCrawford (Mar 24, 2004 7:25:05 PM)
How can we count the total number of possibilities?

hs0m0n (Mar 24, 2004 7:25:38 PM)
wut i said wuz that for numbers that dont have zero, u can choose from nine digits, so there are 9C4 possible combinations of digits.... each combination can be permutated in 5 different wayz (if a < b < c< d: da 5 numbers = acbd adbc bcad bdac and cdab).... so there r 5(9C4) snakey numbers that do not contain a zero;;;; if it contains a zero, it has to be in da a3 slot.. the other 3 digits can be selected in 9C3 wayz.... and da 4 digits can be permutated in 3 different wayz... so there are 3(9C3)...;;;; da final answer is just da sum of those two...

MCrawford (Mar 24, 2004 7:25:45 PM)
Now let's try this in English...

cpu886 (Mar 24, 2004 7:26:12 PM)
If you pick any 4 integers, they can be arranged in 5 ways to get a snakelike number, but you need to exclude possibilities in which 0 is the first digit

empyrealpaladin (Mar 24, 2004 7:26:16 PM)
5*(10 choose 4)-2*(9 choose 3)

MCrawford (Mar 24, 2004 7:26:35 PM)
Both of these approaches are good.

MCrawford (Mar 24, 2004 7:26:42 PM)
I'll walk through the casework quickly.

MCrawford (Mar 24, 2004 7:26:54 PM)
There are C(9, 3) = 84 ways to select the 3 other digits.

MCrawford (Mar 24, 2004 7:27:01 PM)
The smallest digit must either be the first or the third digit. In this case the smallest digit is 0, so it must be the third digit. Let the digits in increasing order be 0, d_1, d_2, and d_3.

MCrawford (Mar 24, 2004 7:27:07 PM)
We have some clues to narrow down the possibilities. The first digit can only be d_1 or d_2. The second digit is larger than the two around it so it can only be d_2 or d_3.

MCrawford (Mar 24, 2004 7:27:13 PM)
Possible arrangements are d_1, d_2, 0, d_3; d_1, d_3, 0, d_2; d_2, d_3, 0, d_1. This gives us 3(84) = 252 snakelike numbers with a 0 digit.

MCrawford (Mar 24, 2004 7:27:25 PM)
There are C(9, 4) = 126 ways to select the 4 digits.

MCrawford (Mar 24, 2004 7:27:33 PM)
Let the digits in increasing order be d_1, d_2, d_3, and d_4.

MCrawford (Mar 24, 2004 7:27:40 PM)
Again we have some clues to narrow down the possibilities. d_4 can't be the first digit. The second digit is at least the second largest, so it can only be d_3 or d_4. The third digit has two larger neighbors, so it can only be d_1 or d_2.

MCrawford (Mar 24, 2004 7:27:49 PM)
Possible arrangements are d_1, d_3, d_2, d_4; d_1, d_4, d_2, d_3; d_2, d_3, d_1, d_4; d_2, d_4, d_1, d_3; d_3, d_4, d_1, d_2. This gives us 5(126) = 630 snakelike numbers without a 0 digit.

MCrawford (Mar 24, 2004 7:27:55 PM)
The total number of 4 digit snakelike numbers is thus 252 + 630 = 882.

MCrawford (Mar 24, 2004 7:28:07 PM)
7. Let C be the coefficient of x^2 in the expansion of the product (1 - x)(1 + 2x)(1 - 3x)…(1 + 14x)(1 - 15x). Find |C|.

MCrawford (Mar 24, 2004 7:28:42 PM)
Ah, typical AIME problem -- we can grind it out for certain or find an elegant approach...

cpu886 (Mar 24, 2004 7:28:48 PM)
sum all the pairwise products of -1, 2, -3, ..., -15

MCrawford (Mar 24, 2004 7:29:07 PM)
If we multiply out these 15 binomials we get an x^2 term whenever 2 of the numbers -1, 2, -3,…, 14, -15 are multiplied together.

cpu886 (Mar 24, 2004 7:29:21 PM)
((-8)^2 - (1^2 + 2^2 + ... + 15^2))/2 = C

MCrawford (Mar 24, 2004 7:29:29 PM)
We can think of the 15 numbers as c_1, c_2,…, c_15. Our job is to take the sum of (c_i)(c_j) where i and j are from 1 to 15 and distinct.

MCrawford (Mar 24, 2004 7:29:40 PM)
Recognizing symmetric sums helps us solve a lot of problems with greater ease. Here we can note that (c_1 + c_2 + … + c_15)^2 - [(c_1)^2 + (c_2)^2 + … + (c_15)^2] equals twice the quantity we are trying to evaluate.

MCrawford (Mar 24, 2004 7:29:53 PM)
(c_1 + c_2 + … + c_15)^2 = (-8)^2, (c_1)^2 + (c_2)^2 + … + (c_15)^2 = (15)(16)(31)/6 = 1240.

MCrawford (Mar 24, 2004 7:30:02 PM)
(64 - 1240)/2 = -588, so the answer is 588.

MCrawford (Mar 24, 2004 7:30:17 PM)
Any questions about this problem?

Fountainhead (Mar 24, 2004 7:30:41 PM)
How do you tie symmetric sums into this again?

MCrawford (Mar 24, 2004 7:30:50 PM)
This about xy + yz + zx

MCrawford (Mar 24, 2004 7:31:14 PM)
We get this from [(x + y + z)^2 - x^2 + y^2 + z^2]/2

MCrawford (Mar 24, 2004 7:31:39 PM)
Oops

MCrawford (Mar 24, 2004 7:31:50 PM)
[(x + y + z)^2 - (x^2 + y^2 + z^2)]/2

hs0m0n (Mar 24, 2004 7:31:59 PM)
ooo... but its 15 "variables" not 3

MCrawford (Mar 24, 2004 7:32:09 PM)
Exactly, but it's the same exact process.

rrusczyk (Mar 24, 2004 7:32:26 PM)
Next problem.

rrusczyk (Mar 24, 2004 7:32:32 PM)
8. Define a regular n-pointed star to be the union of n line segments P_1P_2, P_2P_3,…, P_nP_1 such that * the points P_1, P_2,…, P_n are coplanar and no three of them are collinear, * each of the n line segments intersects at least one of the other line segments at a point other than an endpoint, * all of the angles at P_1, P_2,…, P_n are congruent, * all of the n line segments P_2P_3,…, P_nP_1 are congruent, and * the path P_1P_2, P_2P_3,…, P_nP_1 turns counterclockwise at an angle of less than 180 degrees at each vertex. There are no regular 3-pointed, 4-pointed, or 6-pointed stars. All regular 5-pointed stars are similar, but there are two non-similar regular 7-pointed stars. How many non-similar regular 1000-pointed stars are there?

rrusczyk (Mar 24, 2004 7:32:40 PM)
Often the best place to start is just by drawing the simple ones and seeing what happens.

rrusczyk (Mar 24, 2004 7:32:44 PM)
Here are the 5,7,and 8 pointed stars.

rrusczyk (Mar 24, 2004 7:32:47 PM)
//s3.amazonaws.com/classroom.artofproblemsolving.com/Classes/AIME/Images/2004aimeA8stars.gif

krustyteklown (Mar 24, 2004 7:32:55 PM)
consider the number of points you "jump" over

rrusczyk (Mar 24, 2004 7:33:10 PM)
For the 5-pointed star, we started at one point, went to a point 2 away, then another 2 away from the point, and so on, always going the same way around the circle. For the top 7-point star, we start off going to a point 3 points away from our initial point, then go around. For the bottom, we go 2 points away each time.

rrusczyk (Mar 24, 2004 7:33:15 PM)
For the 8 pointer, we go 3 away. What would happen if we only when 2 points away each time on the 8-point case?

Fermatprime (Mar 24, 2004 7:33:28 PM)
The lines don't all connect.

krustyteklown (Mar 24, 2004 7:33:30 PM)
you'd skip the odd points

rrusczyk (Mar 24, 2004 7:33:35 PM)
If we only go 2 points away each time on the 8-point case, we'll return to the initial point before we hit them all (we'll just make a square).

rrusczyk (Mar 24, 2004 7:33:43 PM)
Does this tell us how to solve the problem?

Braggart Billy (Mar 24, 2004 7:33:51 PM)
the thingies have to be relatively prime with the number of points on the circle.

Fermatprime (Mar 24, 2004 7:33:54 PM)
So, we're talking about relatively prime numbers here.

cpu886 (Mar 24, 2004 7:33:57 PM)
the number of points you jump must be relatively prime to the total number of pts

rrusczyk (Mar 24, 2004 7:34:13 PM)
If we have n points, and we go k points away each time to form our star, we'll hit our original point before visiting all the points if and only if k and n have a divisor in common (besides 1). Otherwise, we'll make one of our desired stars.

rrusczyk (Mar 24, 2004 7:34:18 PM)
Our problem is to count all the numbers less than 1000 which don't have a divisor in common with 1000. (We call these numbers which don't share a divisor with 1000 'relatively prime' to 1000.) However, do we want all of them?

dts (Mar 24, 2004 7:34:25 PM)
consider 1000 evenly spaced points on a circle, connected by 1000 lines of equal length making equal angles. we only need to consider what happens up to halfway around the circle, because the others will be mirror images

lotrfan (Mar 24, 2004 7:34:32 PM)
so we need to find all the relatively prime numbers less than half of the total

rrusczyk (Mar 24, 2004 7:34:48 PM)
No, we don't want all of them. Just as in the 7-point case, going 3 points over each time is the same as going 4 over each time, all the stars come in equivalent pairs. So we want half of them. Almost. What do we have to exclude?

empyrealpaladin (Mar 24, 2004 7:35:13 PM)
1=regular

krustyteklown (Mar 24, 2004 7:35:15 PM)
jumping over none at all

dts (Mar 24, 2004 7:35:17 PM)
1

rrusczyk (Mar 24, 2004 7:35:22 PM)
We have to exclude the case where k=1, since that just gives a regular polygon, not a star.

justdudxit (Mar 24, 2004 7:35:29 PM)
1/2 (phi(1000)) - 1

gge (Mar 24, 2004 7:35:31 PM)
It's \phi(1000) / 2 -1, where \phi is the Euler function

Fermatprime (Mar 24, 2004 7:35:38 PM)
For a certain shape to be an n-pointed star, it must move m points to connect a line to, and m must be relatively prime to n (but m can’t be 1.) In addition, one of m and (n-m) turns clockwise when you move m points. Therefore, we conclude that, since no numbers divide 1000 that don’t divide 500, the answer is 1 less than the number of numbers less than 500 relatively prime to 500, which is 200-1=199.

Idiot_without_a_village (Mar 24, 2004 7:35:42 PM)
would that be the phi function?

rrusczyk (Mar 24, 2004 7:35:52 PM)
Yes: Hence, we want to count the number of numbers less than 1000 which are relatively prime to 1000, divide that by 2, then subtract 1.

rrusczyk (Mar 24, 2004 7:35:57 PM)
The number of numbers less than 1000 which are relatively prime to 1000 is 1000(1-1/2)(1-1/5) = 400. (See if you can prove why). Thus, our answer is 400/2-1 = 199.

rrusczyk (Mar 24, 2004 7:36:05 PM)
For those of you who don't know phi:

Braggart Billy (Mar 24, 2004 7:36:22 PM)
(1000-500-200+100)/2 - 1... because a 3- star is the same as a 997 star and a 1-star and a 999-star don't work

rrusczyk (Mar 24, 2004 7:36:38 PM)
Any questions?

Surreality (Mar 24, 2004 7:36:52 PM)
what is the phi function?

Idiot_without_a_village (Mar 24, 2004 7:37:17 PM)
it counts the numbers relatively prime to some given number

rrusczyk (Mar 24, 2004 7:37:19 PM)
phi(n) = the number of numbers less than n which do not have a factor in common with n (besides) 1

The_Cow_King (Mar 24, 2004 7:37:23 PM)
# of numbers relatively prime to n, so phi(4)= 1 ( only one is 3)

rrusczyk (Mar 24, 2004 7:37:32 PM)
Next problem:

Surreality (Mar 24, 2004 7:37:39 PM)
and how do you calculate that?

gauss202 (Mar 24, 2004 7:37:57 PM)
actually phi(4) = 2 (1 and 3)

rrusczyk (Mar 24, 2004 7:38:05 PM)
nice catch.

rrusczyk (Mar 24, 2004 7:38:44 PM)
n(1-1/p_1)(1-1/p_2)(1-1/p_3) . . . where the p_i are the distinct prime factors of n

rrusczyk (Mar 24, 2004 7:38:49 PM)
See if you can prove it.

rcv (Mar 24, 2004 7:39:39 PM)
phi(p)=p-1, if p is prime. phi(p*q)=phi(p)*phi(q), if p and q are prime. phi(p^n)=(p^(n-1))*phi(p). I think that's most of the rules. phi(1000)=phi(8)*phi(125)=4*phi(2)*25*phi(5)=4*1*25*4=400.

rrusczyk (Mar 24, 2004 7:39:48 PM)
Time for the next problem:

rrusczyk (Mar 24, 2004 7:39:50 PM)
9. Let ABC be a triangle with sides 3, 4, and 5, and DEFG be a 6-by-7 rectangle. A segment is drawn to divide triangle ABC into a triangle U_1 and a trapezoid V_1 and another segment is drawn to divide rectangle DEFG into a triangle U_2 and a trapezoid V_2 such that U_1 is similar to U_2 and V_1 is similar to V_2. The minimum value of the area of U_1 can be written in the form m/n, where m and n are relatively prime positive integers. Find m + n.

rrusczyk (Mar 24, 2004 7:40:04 PM)
Should we start with our triangle or our rectangle?

bookworm271828 (Mar 24, 2004 7:40:23 PM)
triangle

lotrfan (Mar 24, 2004 7:40:25 PM)
triangle, less possibilities

rrusczyk (Mar 24, 2004 7:40:30 PM)
What does the triangle tell us?

dnbmathguy (Mar 24, 2004 7:40:50 PM)
the line has to be parallel to the base

dgf (Mar 24, 2004 7:40:54 PM)
we're drawing a line parallel to one of the sides

Idiot_without_a_village (Mar 24, 2004 7:40:58 PM)
isnt it a right triangle?

Idiot_without_a_village (Mar 24, 2004 7:41:00 PM)
you got the 3, 4, 5 thing going on

rrusczyk (Mar 24, 2004 7:41:06 PM)
We can't get a whole lot of information from the triangle, except that we know the triangle we form will be 3-4-5.

rrusczyk (Mar 24, 2004 7:41:14 PM)
What do we have to consider with the rectangle?

dnbmathguy (Mar 24, 2004 7:41:19 PM)
only way you can form a triangle and trapezoid from a rectangle is with a line drawn from one vertex to an opposite side

empyrealpaladin (Mar 24, 2004 7:41:27 PM)
which side to cut

rrusczyk (Mar 24, 2004 7:41:38 PM)
So, how many options do we have?

empyrealpaladin (Mar 24, 2004 7:41:52 PM)
four total...which side of triangle, which side of rectangle

lotrfan (Mar 24, 2004 7:41:56 PM)
four

krustyteklown (Mar 24, 2004 7:41:58 PM)
2

bookworm271828 (Mar 24, 2004 7:42:00 PM)
two

rrusczyk (Mar 24, 2004 7:42:08 PM)
Let's see how we turn that 4 into 2:

rrusczyk (Mar 24, 2004 7:42:12 PM)
The segment cutting the rectangle has one vertex at a vertex of the rectangle. The other vertex is on either the long side or the short side.

rrusczyk (Mar 24, 2004 7:42:15 PM)
//s3.amazonaws.com/classroom.artofproblemsolving.com/Classes/AIME/Images/2004aimeA9rect.gif

rrusczyk (Mar 24, 2004 7:42:33 PM)
What else can we deduce about our triangles in these two rectangles?

dgf (Mar 24, 2004 7:42:57 PM)
they are similar to the 3-4-5 triangle

justdudxit (Mar 24, 2004 7:42:59 PM)
it's 3-4-5

rrusczyk (Mar 24, 2004 7:43:32 PM)
OK. But is the side of the triangle that is also a side of the rectangle the '3' the '4' or the '5'?

justdudxit (Mar 24, 2004 7:43:58 PM)
The 4

dnbmathguy (Mar 24, 2004 7:44:02 PM)
the 4

Surreality (Mar 24, 2004 7:44:07 PM)
the 4 because if it's the 3 then the 4 side is 8

lotrfan (Mar 24, 2004 7:44:12 PM)
3 or 4, but if its 3, then there isn't enough room

empyrealpaladin (Mar 24, 2004 7:44:21 PM)
which is how you pare the cases down to 2

rrusczyk (Mar 24, 2004 7:44:28 PM)
Exactly.

rrusczyk (Mar 24, 2004 7:44:35 PM)
We know that in either case, the leg of the triangle is 4/5 of the hypotenuse. We know this because the sides of the rectangle are 6 and 7. Since EF = 7, if EF/EX = 3/4, then FX > 6, which is impossible. Similarly, we deduce that in the other case, ED/DY = 4/3. Which of these cases is going to give us our smallest triangle when we cut up the triangle to make a similar trapezoid?

dnbmathguy (Mar 24, 2004 7:45:27 PM)
if we have 7 and 21/4

krustyteklown (Mar 24, 2004 7:45:31 PM)
the case on the left

justdudxit (Mar 24, 2004 7:45:38 PM)
first case

htam (Mar 24, 2004 7:45:41 PM)
the trapezoid has height 7

rrusczyk (Mar 24, 2004 7:45:48 PM)
The EX case (the one on the left) will give us our smallest triangle because it will give us the largest trapezoid (since ED/XG > EF>YG, the trapezoid we form by cutting ABC that is similar to EXGD will take up more of the triangle ABC than the trapezoid we could form similar to EFGY.

rrusczyk (Mar 24, 2004 7:46:00 PM)
So, let's take a look at our triangle. First, is the segment cutting it going to be parallel to the side with length 3 or the side with length 4?

rrusczyk (Mar 24, 2004 7:46:25 PM)
(and why?)

Surreality (Mar 24, 2004 7:47:34 PM)
the three side

Surreality (Mar 24, 2004 7:47:37 PM)
because it makes the trapezoids the same shape

rrusczyk (Mar 24, 2004 7:47:42 PM)
Our trapezoid EXGD gives us the answer; angle XED = angle EXF = angle opposite the long leg. Hence, our segment is parallel to the short leg of ABC:

rrusczyk (Mar 24, 2004 7:47:46 PM)
//s3.amazonaws.com/classroom.artofproblemsolving.com/Classes/AIME/Images/2004aimeA9leg.gif

rrusczyk (Mar 24, 2004 7:48:02 PM)
Make sure you see how we use the similarity condition here.

rrusczyk (Mar 24, 2004 7:48:21 PM)
Now what?

lotrfan (Mar 24, 2004 7:48:48 PM)
use proportions to determine WZ

empyrealpaladin (Mar 24, 2004 7:48:50 PM)
calculate area with known side lengths

rrusczyk (Mar 24, 2004 7:49:05 PM)
We know the triangles are similar (WZC ~ XFE), now we must make the trapezoids similar. How?

htam (Mar 24, 2004 7:49:59 PM)
BZ = AB / ED * DG

Hexahedron (Mar 24, 2004 7:50:19 PM)
AB=3 ED=6 so the ratio is 1/2

rrusczyk (Mar 24, 2004 7:50:27 PM)
All our angles match up, now we match up the ratios of sides. ED = 6, DG = 7, AB =3, so BZ = 7/2.

rrusczyk (Mar 24, 2004 7:50:39 PM)
So?

Hexahedron (Mar 24, 2004 7:51:01 PM)
ZC=1/2

lotrfan (Mar 24, 2004 7:51:16 PM)
and ZW=3/8

rrusczyk (Mar 24, 2004 7:51:36 PM)
Thus, CZ = 4 - BZ = 1/2, and WZ = (3/4)CZ = 3/8 (thus WZ/AB = 1/8 = XG/ED, as expected, since XG = 6 - FX = 6 - (3/4)EF = 3/4.)

empyrealpaladin (Mar 24, 2004 7:51:43 PM)
A=(1/2)(3/8)(4/8)=3/32 => 035

rrusczyk (Mar 24, 2004 7:51:45 PM)
Hence, our area is (3/8)(1/2)(1/2) = 3/32 and our answer is 35.

rrusczyk (Mar 24, 2004 7:51:54 PM)
Any questions?

gge (Mar 24, 2004 7:52:33 PM)
extend EX to intersect DG in the first case and FG in the 2nd case, you see the similarities right away

rrusczyk (Mar 24, 2004 7:52:49 PM)
Good observation for how to know where to draw the line in the triangle.

rrusczyk (Mar 24, 2004 7:52:56 PM)
Next problem.

rrusczyk (Mar 24, 2004 7:53:04 PM)
10. A circle of radius 1 is randomly placed in a 15-by-36 rectangle ABCD so that the circle lies completely within the rectangle. Given that the probability that the circle will not touch diagonal AC is m/n, where m and n are relatively prime positive integers. Find m + n.

rrusczyk (Mar 24, 2004 7:53:13 PM)
How do we find the probability?

lotrfan (Mar 24, 2004 7:53:25 PM)
area

tetrahedr0n (Mar 24, 2004 7:53:29 PM)
area where it doesnt/total area

empyrealpaladin (Mar 24, 2004 7:53:36 PM)
by using areas*

rrusczyk (Mar 24, 2004 7:53:45 PM)
We use area. Area of what?

Surreality (Mar 24, 2004 7:54:02 PM)
we could make a picture showing where the center of the circle can and cant be

empyrealpaladin (Mar 24, 2004 7:54:09 PM)
calculate viable locations for the circle's center

MarkSmith888 (Mar 24, 2004 7:54:17 PM)
Possible points where the center can be

Mr.Ocax (Mar 24, 2004 7:54:46 PM)
first, since it's dropped entirely on hte rectangle, can we set our limits?

rrusczyk (Mar 24, 2004 7:54:50 PM)
yes:

hs0m0n (Mar 24, 2004 7:54:52 PM)
we are told it has tob e inside the 13 by 34 rectangle, one away from each side

rrusczyk (Mar 24, 2004 7:54:55 PM)
We measure where the circle is by its center: our possible region is a 13 by 34 rectangle inside ABCD (since the center must be at least 1 unit away from all sides of the rectangle. Figuring out our desired region, the area in which the center can fall so that the circle does not touch AC, is harder. How do we do it?

hs0m0n (Mar 24, 2004 7:55:37 PM)
well... the closest the center can be to the corner is one from each side

dts (Mar 24, 2004 7:55:43 PM)
use the diagonal of the rectangle to split it into two right triangles

Mr.Ocax (Mar 24, 2004 7:55:49 PM)
the center is 1 away from the line

Surreality (Mar 24, 2004 7:56:04 PM)
make lines 1 unit away from the diagonal to show the limits of where the center can be

rrusczyk (Mar 24, 2004 7:56:13 PM)
We consider the extreme locations of the circle:

rrusczyk (Mar 24, 2004 7:56:17 PM)
//s3.amazonaws.com/classroom.artofproblemsolving.com/Classes/AIME/Images/2004aimeA10cir.gif

rrusczyk (Mar 24, 2004 7:56:25 PM)
Our problem is just finding the area of EFG, then doubling it. How can we find the area of EFG?

justdudxit (Mar 24, 2004 7:56:44 PM)
Its similar to ABC

rrusczyk (Mar 24, 2004 7:56:52 PM)
True, but what are the side lengths?

rrusczyk (Mar 24, 2004 7:57:18 PM)
We know that GF is 1 away from CD, and that EG is 1 away from AD. All we have to do is figure out how far E is from AB, and F is from BC. How do we do it?

gge (Mar 24, 2004 7:57:27 PM)
look at circle F the tangent from C is 5

rrusczyk (Mar 24, 2004 7:57:29 PM)
why?

fubu (Mar 24, 2004 7:57:43 PM)
draw the perpendicular and do similar triangles using the diameter is 2

tetrahedr0n (Mar 24, 2004 7:57:45 PM)
angles

dts (Mar 24, 2004 7:57:58 PM)
draw perpendiculars from E to AC and CD

rrusczyk (Mar 24, 2004 7:58:11 PM)
We can do it with similar triangles at this point, as you are all suggesting.

rrusczyk (Mar 24, 2004 7:58:22 PM)
You can also use trig.

rrusczyk (Mar 24, 2004 7:58:34 PM)
Here's a pretty fast way:

rrusczyk (Mar 24, 2004 7:58:42 PM)
We know that the radius of E is 1; if we view it as a circle inscribed in a right triangle, we can get the information we need:

rrusczyk (Mar 24, 2004 7:58:45 PM)
//s3.amazonaws.com/classroom.artofproblemsolving.com/Classes/AIME/Images/2004aimeA10ans.gif

rrusczyk (Mar 24, 2004 7:58:51 PM)
Circle E is inscribed in AXZ. We know that the sides of AXZ are in a 5-12-13 ratio, but we don't know how large it is. How do we find out?

justdudxit (Mar 24, 2004 7:59:20 PM)
A/s = r

rrusczyk (Mar 24, 2004 7:59:27 PM)
That's one way, what's even faster?

gge (Mar 24, 2004 7:59:57 PM)
5x-12x-13x, then (12x-1) + (5x-1) = 13x

Mr.Ocax (Mar 24, 2004 8:00:09 PM)
12-x+5-x=13

Mr.Ocax (Mar 24, 2004 8:00:18 PM)
r=2

rrusczyk (Mar 24, 2004 8:00:20 PM)
Basically right, let's see what they're getting at.

rrusczyk (Mar 24, 2004 8:00:30 PM)
The inradius, or radius of the inscribed circle, in a right triangle is (a+b-c)/2, where c is the hypotenuse (make sure you know how to prove it). Thus, a 5-12-13 triangle has an inradius with length (12+5-13)/2 = 2.

rrusczyk (Mar 24, 2004 8:00:35 PM)
What does this tell us about AXZ?

lotrfan (Mar 24, 2004 8:01:24 PM)
its 2.5-6-6.5

Hexahedron (Mar 24, 2004 8:01:27 PM)
AX=2.5

pi^2 (Mar 24, 2004 8:01:30 PM)
its lengths are half of those of a 5-12-13 triangle?

dgf (Mar 24, 2004 8:01:33 PM)
it's sides are 5/2, 6, 13/2

rrusczyk (Mar 24, 2004 8:01:37 PM)
The inradius of AXZ is 1, which is half the inradius of a 5-12-13 right triangle. Hence, our AXZ must have side lengths half as long, or AX = 5/2,XZ = 6. Hence, how far is E from AB?

Fountainhead (Mar 24, 2004 8:02:15 PM)
5/2-1=1.5

lotrfan (Mar 24, 2004 8:02:17 PM)
2.5-1=1.5

rrusczyk (Mar 24, 2004 8:02:20 PM)
Since EY = 1 and AX = 5/2, we know E is 3/2 from AB. Similarly, we find YZ = XZ - XY = 6 - 1 = 5, so F is 5 from BC.

rrusczyk (Mar 24, 2004 8:02:32 PM)
So, what is EG?

dgf (Mar 24, 2004 8:03:16 PM)
15-1.5-1=12.5

Surreality (Mar 24, 2004 8:03:19 PM)
25/2

Fountainhead (Mar 24, 2004 8:03:22 PM)
15-1.5-1=12.5

rrusczyk (Mar 24, 2004 8:03:23 PM)
E is 3/2 from AB, G is 1 from CD, so EG = 15 - 5/2 = 25/2. Similarly, GF = 36 - 1 - 5 = 30. So, what is the area of our desired region?

empyrealpaladin (Mar 24, 2004 8:04:02 PM)
375

Hexahedron (Mar 24, 2004 8:04:12 PM)
375

Surreality (Mar 24, 2004 8:04:25 PM)
so 750/4*2=375

rrusczyk (Mar 24, 2004 8:04:28 PM)
Our desired region has area 2[EFG] = 2(1/2)(25/2)(30) = (25)(15).

rrusczyk (Mar 24, 2004 8:04:31 PM)
What is our probability?

captcha000 (Mar 24, 2004 8:05:09 PM)
375/(13*34)

Fountainhead (Mar 24, 2004 8:05:16 PM)
375/442

captcha000 (Mar 24, 2004 8:05:19 PM)
375/442

rrusczyk (Mar 24, 2004 8:05:26 PM)
Our probability is [(25)(15)] / [(13)(34)] = 375/442, so our answer is 817.

Mr.Ocax (Mar 24, 2004 8:05:53 PM)
why is it only out of the smaller rectangle?

tetrahedr0n (Mar 24, 2004 8:06:05 PM)
center cant be out of it

justdudxit (Mar 24, 2004 8:06:11 PM)
that's where the center can go

masamune2387 (Mar 24, 2004 8:06:15 PM)
thats the only place the center can be if its in the rectangle

rrusczyk (Mar 24, 2004 8:06:20 PM)
Any more questions?

rrusczyk (Mar 24, 2004 8:07:21 PM)
11. A solid in the shape of a right circular cone is 4 inches tall and its base has a 3-inch radius. The entire surface of the cone, including its base, is painted. A plane parallel to the base of the cone divides the cone into two solids, a smaller cone-shaped solid C and a frustum-shaped solid F, in such a way that the ratio between the areas of the painted surfaces of C and F and the ratio between the volumes of C and F are both equal to k. Given that k = m/n, where m and n are relatively prime positive integers, find m + n.

rrusczyk (Mar 24, 2004 8:08:04 PM)
What makes this problem hard?

bookworm271828 (Mar 24, 2004 8:08:27 PM)
what is a right cone?

rrusczyk (Mar 24, 2004 8:08:27 PM)
line from vertex to center of base is perpendicular to base

albertfermat1 (Mar 24, 2004 8:08:30 PM)
formulas for a frustrum and cone

rrusczyk (Mar 24, 2004 8:08:43 PM)
The frustum makes it hard. How can we deal with that?

masamune2387 (Mar 24, 2004 8:08:57 PM)
Large cone - small cone

Dark_Shadow (Mar 24, 2004 8:08:59 PM)
cone - smaller cone

htam (Mar 24, 2004 8:09:01 PM)
big cone - small cone

rrusczyk (Mar 24, 2004 8:09:11 PM)
We could also do it like this:

rrusczyk (Mar 24, 2004 8:09:15 PM)
Instead of comparing the little cone to the frustum, we can compare the little cone to the big cone.

rrusczyk (Mar 24, 2004 8:09:26 PM)
Why?

empyrealpaladin (Mar 24, 2004 8:09:38 PM)
because you have more knowledge about cones

lotrfan (Mar 24, 2004 8:09:43 PM)
simpler equations later on

rrusczyk (Mar 24, 2004 8:09:51 PM)
Here's why it works:

rrusczyk (Mar 24, 2004 8:09:52 PM)
We're given that A(C) / A(F) = V(C)/V(F), where A(F) = painted area of the frustum, V(F) = volume of frustum and likewise for the cone.

rrusczyk (Mar 24, 2004 8:09:58 PM)
From this equality, we can deduce A(C) / [A(F) + A(C)] = V(C)/[V(F)+V(C)]. Make sure you see why. Here's a quick proof: If a/b = x/y, then b/a = y/x. Add 1 to each side and we have (b+a)/a = (y+x)/x. Flip 'em back over and we're done.

rrusczyk (Mar 24, 2004 8:10:13 PM)
(Note that the similarity is not enough!)

Fermatprime (Mar 24, 2004 8:10:17 PM)
Because instead of (little cone):(big cone - little cone), it's the easier (little cone):(big cone)

masamune2387 (Mar 24, 2004 8:10:20 PM)
cool, that makes things a lot easier

rrusczyk (Mar 24, 2004 8:10:26 PM)
Exactly, that's why we like it.

rrusczyk (Mar 24, 2004 8:10:39 PM)
So, we want to compute A(C) / [A(F) + A(C)] = V(C)/[V(F)+V(C)]

dgf (Mar 24, 2004 8:10:50 PM)
SA of cone = 15pi + 9pi=24pi

rrusczyk (Mar 24, 2004 8:10:58 PM)
OK, and the volume?

Hexahedron (Mar 24, 2004 8:11:07 PM)
12pi

justdudxit (Mar 24, 2004 8:11:09 PM)
12pi

dts (Mar 24, 2004 8:11:13 PM)
12pi

rrusczyk (Mar 24, 2004 8:11:15 PM)
Those denominators are just the original cone. Now we're pretty set. The volume of our original cone is 12pi and the painted area is 15pi+9pi = 24pi, so we have

rrusczyk (Mar 24, 2004 8:11:20 PM)
A(C)/V(C) = 2. Letting the radius of the little cone be r, what does our expression become?

rrusczyk (Mar 24, 2004 8:14:04 PM)
What is the area in terms of r?

justdudxit (Mar 24, 2004 8:15:07 PM)
(pi * r * 5r/3)/(1/3 *pi * r^2 * 4r/3) = 2

htam (Mar 24, 2004 8:15:12 PM)
pi 5/3 r^2

dgf (Mar 24, 2004 8:15:18 PM)
since l/5 = r/3, l = 5r/3, so a=pi(r)(5r/3)

rrusczyk (Mar 24, 2004 8:15:40 PM)
The little cone will also have radius:height = 3:4, so A(C) = (radius)(slant height)(pi) = r(5r/3)pi, and our volume?

dgf (Mar 24, 2004 8:16:19 PM)
1/3(pi)(r^2)(4r/3)

<><><> (Mar 24, 2004 8:16:22 PM)
r^2*pi*4/3r/3

rrusczyk (Mar 24, 2004 8:16:35 PM)
Put these together, we get justdud's equation:

rrusczyk (Mar 24, 2004 8:16:40 PM)
The little cone will also have radius:height = 3:4, so A(C) = (radius)(slant height)(pi) = r(5r/3)pi, and volume = (pi)r^2(height)/3 = 4r^3(pi)/9, so we have

rrusczyk (Mar 24, 2004 8:16:50 PM)
A(C)/V(C) = (5/3) / [4r/9] = 15 / 4r = 2, so r = 15/8.

rrusczyk (Mar 24, 2004 8:16:54 PM)
Now what?

Hexahedron (Mar 24, 2004 8:17:11 PM)
Use the ratio

lotrfan (Mar 24, 2004 8:17:13 PM)
find k

timhlu (Mar 24, 2004 8:17:15 PM)
plug it back in

rrusczyk (Mar 24, 2004 8:17:23 PM)
What do we get?

dgf (Mar 24, 2004 8:17:27 PM)
find the A(small)/V(small)

rrusczyk (Mar 24, 2004 8:17:30 PM)
Which is?

rrusczyk (Mar 24, 2004 8:18:22 PM)
Sorry - we want the ratio of A(small) / A(big), right?

dgf (Mar 24, 2004 8:18:49 PM)
don't we want A(small)/A(F)?

rrusczyk (Mar 24, 2004 8:18:57 PM)
That's what we want for our final answer.

rrusczyk (Mar 24, 2004 8:19:28 PM)
We already have an expression for A(small)/A(big), so we can just substitute in that, then we can quickly get A(small)/A(F) from the result.

<><><> (Mar 24, 2004 8:20:21 PM)
a(sm)/a(big) is 5r^2 /72

rrusczyk (Mar 24, 2004 8:20:45 PM)
Our ratio A(C) / [A(F) + A(C)] = [(5/3)(pi)r^2] / [24(pi)] = 125/512, so what is our desired ratio A(C)/A(F)?

justdudxit (Mar 24, 2004 8:21:08 PM)
125/(512-125) => 512

Hexahedron (Mar 24, 2004 8:21:15 PM)
125/(512-125)

rrusczyk (Mar 24, 2004 8:21:20 PM)
our desired ratio A(C)/A(F) = 125/(512-125) = 125/387, and our answer is 512.

rrusczyk (Mar 24, 2004 8:21:24 PM)
Any questions?

rrusczyk (Mar 24, 2004 8:22:00 PM)
Next problem.

rrusczyk (Mar 24, 2004 8:22:03 PM)
12. Let S be the set of ordered pairs (x, y) such that 0 < x <= 1, 0 < y <= 1, and [log_2 (1/x)] and [log_5 (1/y)] are both even. Given that the area of the graph of S is m/n, where m and n are relatively prime positive integers, find m + n. The notation [z] denotes the greatest integer that is less than or equal to z.

dts (Mar 24, 2004 8:22:11 PM)
is zero considered an even number for this problem?

rrusczyk (Mar 24, 2004 8:22:18 PM)
0 is always considered an even number

rrusczyk (Mar 24, 2004 8:22:21 PM)
As with many of the late AIME problems, we start off playing with it. When is [log_2 (1/x)] even?

Dark_Shadow (Mar 24, 2004 8:22:53 PM)
when x is 1-0.5, 1.25 to 0.125, 0.0625-0.03125, etc.

masamune2387 (Mar 24, 2004 8:22:56 PM)
when x = 1 to 1/2, 1/4 to 1/8, etc

rrusczyk (Mar 24, 2004 8:23:02 PM)
[log(1/x)] is 0 when x is between 1/2 and 1. It is 1 when x is between 1/2 and 1/4, 2 when between 1/4 and 1/8, 3 when between 1/8 and 1/16, and so on.

rrusczyk (Mar 24, 2004 8:23:06 PM)
How about [log(1/y)]?

Dark_Shadow (Mar 24, 2004 8:23:25 PM)
1-1/5, 1/25-1-125, etc.

masamune2387 (Mar 24, 2004 8:23:27 PM)
1 to 1/5, 1/25 to 1/125...

lotrfan (Mar 24, 2004 8:23:30 PM)
1 to 1/5, 1/25 to 1/125...

rrusczyk (Mar 24, 2004 8:23:33 PM)
[log(1/y)] is 0 when y is between 1/5 and 1, 1 when y is between 1/25 and 1/5, 2 when y is between 1/125 and 1/25, and so. Thus, our region is a bunch of rectangles:

rrusczyk (Mar 24, 2004 8:23:36 PM)
//s3.amazonaws.com/classroom.artofproblemsolving.com/Classes/AIME/Images/2004aimeA12squ.gif

rrusczyk (Mar 24, 2004 8:23:55 PM)
(Actually, that diagram should be rotated slightly, but you get the picture.)

rrusczyk (Mar 24, 2004 8:24:03 PM)
The diagram shows 4 of them. How do we find the area of all of them?

Dark_Shadow (Mar 24, 2004 8:24:12 PM)
multiply the infinite series

masamune2387 (Mar 24, 2004 8:24:14 PM)
so all we have to do is multiply two series, and we have all the rectangles

rrusczyk (Mar 24, 2004 8:24:25 PM)
Let's see how we would get to this real quick.

rrusczyk (Mar 24, 2004 8:24:36 PM)
What is the total area of the right-most column?

masamune2387 (Mar 24, 2004 8:25:42 PM)
1/2(4/5 + 4/125 + ...)

rrusczyk (Mar 24, 2004 8:25:46 PM)
The right-most column of rectangles has total area (1/2)(4/5) + (1/2)(4/125) + (1/2)(4/5^5) + . . . = (1/2)(4/5 + 4/5^3 + 4/5^5 + . . .) = (1/2)(5/6) = 5/12.

rrusczyk (Mar 24, 2004 8:25:50 PM)
What about the next column?

masamune2387 (Mar 24, 2004 8:26:23 PM)
same thing, with 1/8 as the coefficient

dts (Mar 24, 2004 8:26:29 PM)
1/8(4/5+4/125... etc

lotrfan (Mar 24, 2004 8:26:31 PM)
1/8(4/5+4/125+...)

rrusczyk (Mar 24, 2004 8:26:35 PM)
The next column has total area that is 1/4 the previous, since the widths of the rectangles are 1/4 of those in the previous rightmost column. Thus, that area is (5/12)(1/4).

rrusczyk (Mar 24, 2004 8:26:39 PM)
Continuing, we can add up all the columns: (5/12) + (5/12)(1/4) + (5/12)(1/4)^2 + . . . = (5/12)(1 + 1/4 + 1/16 + . . . ) = (5/12)(4/3) = 5/9, so our answer is 14.

rrusczyk (Mar 24, 2004 8:26:55 PM)
Some of you probably just noted you can hit all the rectangles at once with (1/2 + 1/8 + 1/16 + . . . )(4/5 + 4/5^3 + 4/5^5 + . . . ) Make sure you see why this gets them all.

rrusczyk (Mar 24, 2004 8:27:26 PM)
Any questions?

justdudxit (Mar 24, 2004 8:27:36 PM)
woah... wouldn't it be (1/2 + 1/8 + 1/32...)?

rrusczyk (Mar 24, 2004 8:27:40 PM)
Yeah, sorry:

rrusczyk (Mar 24, 2004 8:27:48 PM)
Some of you probably just noted you can hit all the rectangles at once with (1/2 + 1/8 + 1/32 + . . . )(4/5 + 4/5^3 + 4/5^5 + . . . )

MCrawford (Mar 24, 2004 8:28:20 PM)
13. The polynomial P(x) = (1 + x + x^2 + … + x^17)^2 - x^17 Has 34 complex roots of the form z_k = r_k[cos(2(pi)a_k) + i*sin(2(pi)a_k], k = 1, 2, 3,…, 34, with 0 < a_1 <= a_2 <= a_3 <= … <= a_34 < 1 and r_k > 0. Given that a_1 + a_2 + a_3 + a_4 + a_5 = m/n, where m and n are relatively prime positive integers, find m + n.

MCrawford (Mar 24, 2004 8:28:31 PM)
What are we trying to evaluate?

justdudxit (Mar 24, 2004 8:28:43 PM)
the roots of the polynomial

MCrawford (Mar 24, 2004 8:28:49 PM)
It is important to first recognize what it is we are examining. In this case we are hunting for the roots of (1 + x + x^2 + … + x^17)^2 - x^17 = 0. What is interesting about this equation?

justdudxit (Mar 24, 2004 8:29:06 PM)
The big ugly one on the left is a geometric series

masamune2387 (Mar 24, 2004 8:29:09 PM)
the - x^17

MCrawford (Mar 24, 2004 8:29:15 PM)
The two obvious interesting features are the geometric progression that is squared and the x^17 outside of that. Can we use either of these features?

TheSouthpaw (Mar 24, 2004 8:29:28 PM)
The lefthand is x^18-1/x-1

TheSouthpaw (Mar 24, 2004 8:29:35 PM)
squared

gge (Mar 24, 2004 8:29:42 PM)
(x^2-1) * P(x) = (x^17 - 1) * (x^19 - 1)

MCrawford (Mar 24, 2004 8:29:51 PM)
We can multiply the equation through by (x - 1)^2. This gives us a 36th degree polynomial into which we have injected a double root at x = 1: (x^18 - 1)^2 - x^17(x - 1)^2 = 0, thus x^36 - 2x^18 + 1 - x^19 + 2x^18 - x^17 = 0.

MCrawford (Mar 24, 2004 8:30:10 PM)
After we cancel the x^18 terms and rearrange we have x^36 - x^19 - x^17 + 1 = 0. We can factor this into the form (x^19 - 1)(x^17 - 1) = 0. What have we discovered?

justdudxit (Mar 24, 2004 8:30:22 PM)
so that's the 17th and 19th roots of unity

masamune2387 (Mar 24, 2004 8:30:25 PM)
19th roots and 17th roots of unity

gge (Mar 24, 2004 8:30:31 PM)
sorry, should be (x-1)^2 * P(x) above

lculus (Mar 24, 2004 8:30:36 PM)
Except 1

MCrawford (Mar 24, 2004 8:30:46 PM)
We now see that the roots of the original equation are the 17th and 19th roots of unity (except that we inserted the 1's in both cases). What is it that we are trying to do with these roots?

Fermatprime (Mar 24, 2004 8:31:11 PM)
But how do we order the 17th and 19th roots of unity to solve the problem?

dgf (Mar 24, 2004 8:31:14 PM)
find the angles

TheSouthpaw (Mar 24, 2004 8:31:25 PM)
rcis theta

MCrawford (Mar 24, 2004 8:31:37 PM)
We are examining the complex form of these roots and we are interested in the fractions of the angles around the unit circle that are the arguments of these roots. What are those fractions?

dts (Mar 24, 2004 8:32:10 PM)
1/19, 1/17,2/19, 3/19, 2/17

justdudxit (Mar 24, 2004 8:32:12 PM)
1/19<1/17<2/19<2/17<3/19

dgf (Mar 24, 2004 8:32:22 PM)
the angles are 2pi/17, 4pi/17, 6pi/17, etc and 2pi/19, 4pi/19 etc

MCrawford (Mar 24, 2004 8:33:02 PM)
Each angle is in the form 2(pi)k/n, where n is 17 or 19 and k is 1 to 17-1 or 19-1.

MCrawford (Mar 24, 2004 8:33:38 PM)
The roots of unity are equally spaced around the unit circle. If you do not already know what this is true, think about DeMoivre's theorem and see if you can prove it on your own.

MCrawford (Mar 24, 2004 8:33:46 PM)
The arguments of the roots are k[2(pi)/17] and k[2(pi)/19], so the a_k that we are interested in are 1/17, 2/17,…, 16/17 and 1/19, 2/19,…, 18/19. What is our final answer?

dts (Mar 24, 2004 8:34:08 PM)
the sum of the five smallest fractions

lotrfan (Mar 24, 2004 8:34:33 PM)
1/19+2/19+3/19+1/17+2/17

MCrawford (Mar 24, 2004 8:34:36 PM)
We are asked to sum the 5 smallest of these fractions. 1/19 + 1/17 + 2/19 + 2/17 + 3/19 = 159/323. Our answer is 159 + 323 = 482.

MCrawford (Mar 24, 2004 8:34:43 PM)
We examined this type of equation in both the Intermediate Algebra and AMC/AIME classes.

justdudxit (Mar 24, 2004 8:34:59 PM)
How can you be sure those are the smallest?

Fermatprime (Mar 24, 2004 8:35:45 PM)
Cross-multiply and check.

rrusczyk (Mar 24, 2004 8:35:47 PM)
Can look at the decimal expression, or compare 4/19 and 3/17 to 3/19 and 2/17 and note that the former are both greater than the latter.

rrusczyk (Mar 24, 2004 8:35:53 PM)
Any more questions?

rrusczyk (Mar 24, 2004 8:36:13 PM)
14. A unicorn is tethered by a 20-foot silver rope to the base of a magician's cylindrical tower whose radius is 8 feet. The rope is attached to the tower at ground level and to the unicorn at a height of 4 feet. The unicorn has pulled the rope taut, the end of the rope is 4 feet from the nearest point on the tower, and the length of the rope that is touching the tower is [a - sqrt(b)]/c feet, where a, b, and c are positive integers, and c is prime. Find a + b + c.

rrusczyk (Mar 24, 2004 8:36:23 PM)
What are most 3-D problems?

Fermatprime (Mar 24, 2004 8:36:28 PM)
Is the rope considered infinitely thin? (I assume it is.)

rrusczyk (Mar 24, 2004 8:36:30 PM)
yes

tokenadult (Mar 24, 2004 8:36:43 PM)
2d

eminemnshady (Mar 24, 2004 8:36:46 PM)
2d in disguise

htam (Mar 24, 2004 8:36:50 PM)
they are actually 2-D problems stacked together

rrusczyk (Mar 24, 2004 8:36:59 PM)
Most 3-D problems are 2-D problems in disguise. We just have to figure out what 2-D pieces to look at.

rrusczyk (Mar 24, 2004 8:37:04 PM)
To find the length of the rope that touches the tower, what do we have to find?

krustyteklown (Mar 24, 2004 8:37:30 PM)
the length that doesn't touch

htam (Mar 24, 2004 8:37:33 PM)
the length of the rope that does not touch the tower

rrusczyk (Mar 24, 2004 8:37:51 PM)
We just have to find the length of the rope not touching the tower.

justdudxit (Mar 24, 2004 8:37:52 PM)
So is the rope wrapped around the tower?

rrusczyk (Mar 24, 2004 8:37:54 PM)
yes

rrusczyk (Mar 24, 2004 8:37:57 PM)
How do we make this into a 2-D problem we can deal with? What makes it hard?

dts (Mar 24, 2004 8:38:14 PM)
that the rope spirals up the tower

tokenadult (Mar 24, 2004 8:38:16 PM)
the uincorn height

justdudxit (Mar 24, 2004 8:38:18 PM)
The height of the unicorn

rrusczyk (Mar 24, 2004 8:38:24 PM)
What makes this hard is that the rope goes down from the unicorn to the base. If it didn't, we'd have a pretty easy problem (just find the length of the tangent from the unicorn to the tower). What 2-D pieces should we consider?

lotrfan (Mar 24, 2004 8:38:41 PM)
we could unwrap the rope, and look at the triangle formed

MPS-vras (Mar 24, 2004 8:38:43 PM)
unwrap the cylinder and turn it into a plane

rrusczyk (Mar 24, 2004 8:39:01 PM)
We'll probably wanting to look at that - that gives us a right triangle, which we like.

htam (Mar 24, 2004 8:39:04 PM)
if we look from the top, we can see how long it is not touching projected

lotrfan (Mar 24, 2004 8:39:06 PM)
a top view to determine the horizontal distance of the unicorn to the side of the tower

rrusczyk (Mar 24, 2004 8:39:14 PM)
There's another view.

rrusczyk (Mar 24, 2004 8:39:34 PM)
Let's start with that one:

rrusczyk (Mar 24, 2004 8:39:42 PM)
//s3.amazonaws.com/classroom.artofproblemsolving.com/Classes/AIME/Images/2004aimeA14bird.gif

rrusczyk (Mar 24, 2004 8:40:09 PM)
This is our view from above. Why do we like it?

masamune2387 (Mar 24, 2004 8:40:22 PM)
wow thats a nice view, its circles and tangents!

htam (Mar 24, 2004 8:40:26 PM)
we have a right triangle with two lengths known

tokenadult (Mar 24, 2004 8:40:28 PM)
it 2d

dgf (Mar 24, 2004 8:40:35 PM)
we are looking for AC

rrusczyk (Mar 24, 2004 8:40:38 PM)
What is AC?

lotrfan (Mar 24, 2004 8:41:02 PM)
BC=8, AB=12, AC=4rt(5)

Hexahedron (Mar 24, 2004 8:41:06 PM)
AC=4sqrt5

dgf (Mar 24, 2004 8:41:15 PM)
AB is 12, and BC is 8, so AC = 4sqrt5

rrusczyk (Mar 24, 2004 8:41:17 PM)
We know that AD = 4, BD = 8, and BC = 8, so AC = 4*sqrt(5).

rrusczyk (Mar 24, 2004 8:41:31 PM)
Is AC the length of the rope that is not touching the cylinder?

masamune2387 (Mar 24, 2004 8:41:48 PM)
no, its the projection

lotrfan (Mar 24, 2004 8:41:49 PM)
no, we didn't factor in vertical distance

empyrealpaladin (Mar 24, 2004 8:41:52 PM)
no, it's the horizontal distance

rrusczyk (Mar 24, 2004 8:41:57 PM)
Right, If we think about the plane that is tangent to the tower and includes the rope as it goes from the tower to the goat, we have something like this:

rrusczyk (Mar 24, 2004 8:42:03 PM)
//s3.amazonaws.com/classroom.artofproblemsolving.com/Classes/AIME/Images/2004aimeA14side.gif

rrusczyk (Mar 24, 2004 8:42:06 PM)
(diagram obviously not to scale!)

rrusczyk (Mar 24, 2004 8:42:13 PM)
The cylinder is in purple, and is behind our plane. The vertical line is where the plane we are looking at touches the cylinder; AX is the rope.

rrusczyk (Mar 24, 2004 8:42:22 PM)
How are we going to get AX?

Dark_Shadow (Mar 24, 2004 8:42:38 PM)
similar triangles

rrusczyk (Mar 24, 2004 8:42:44 PM)
Where are we going to get them?

htam (Mar 24, 2004 8:43:01 PM)
the totla length and the total rise of the rope

Dark_Shadow (Mar 24, 2004 8:43:04 PM)
with the big right 20-4 triangle

rrusczyk (Mar 24, 2004 8:43:17 PM)
Now we can use similar triangles. We know that A is 4 from the ground. If we 'unfurl' our rope, we will have a right triangle with hypotenuse 20 and this leg 4.

rrusczyk (Mar 24, 2004 8:43:22 PM)
//s3.amazonaws.com/classroom.artofproblemsolving.com/Classes/AIME/Images/2004aimeA14furl.gif

rrusczyk (Mar 24, 2004 8:43:47 PM)
We are given AD = 4, AE = 20. The solution to our problem is XE, and we know AC = 4sqrt(5).

rrusczyk (Mar 24, 2004 8:43:49 PM)
So?

Hexahedron (Mar 24, 2004 8:43:53 PM)
other leg=8sqrt6

rrusczyk (Mar 24, 2004 8:44:00 PM)
DE = 4sqrt(25-1) = 8sqrt(6)

rrusczyk (Mar 24, 2004 8:44:55 PM)
So?

dgf (Mar 24, 2004 8:46:04 PM)
8sqrt(6)/(4sqrt(5)) = AX/20

rrusczyk (Mar 24, 2004 8:46:39 PM)
from AX/AC = AE/DE, we have AX = (20)/(8sqrt(6)) * (4sqrt(5)) = 10*(sqrt(6/5).

rrusczyk (Mar 24, 2004 8:47:00 PM)
(dgf has the left fraction flipped)

rrusczyk (Mar 24, 2004 8:47:21 PM)
(and I flipped the 6/5)

Hexahedron (Mar 24, 2004 8:47:27 PM)
AX=10sqrt5/sqrt6

rrusczyk (Mar 24, 2004 8:47:31 PM)
from AX/AC = AE/DE, we have AX = (20)/(8sqrt(6)) * (4sqrt(5)) = 10*(sqrt(5/6)).

lotrfan (Mar 24, 2004 8:47:36 PM)
now 20-that is what we want

rrusczyk (Mar 24, 2004 8:47:44 PM)
Hence, XE = 20 - 10sqrt(5/6) = 20 - 5sqrt(30)/3 = (60-5sqrt(30)) / 3 = (60 - sqrt(750)) / 3, so our answer is 813.

rrusczyk (Mar 24, 2004 8:47:54 PM)
Any questions?

masamune2387 (Mar 24, 2004 8:48:09 PM)
wow that didn't seem to hard at all

rrusczyk (Mar 24, 2004 8:48:20 PM)
Nope - most of these 3D problems fall apart just like that.

zabelman (Mar 24, 2004 8:48:42 PM)
thats almost exactly how i did it!

rrusczyk (Mar 24, 2004 8:48:45 PM)
The next problem, however is a little trickier.

MCrawford (Mar 24, 2004 8:49:00 PM)
15. For all positive integers x, let f(x) = 1 if x = 1, f(x) = x/10 if x is divisible by 10, f(x) = x + 1 otherwise, and define a sequence as follows: x_1 = x and x_(n+1) = f(x_n) for all positive integers n. Let d(x) be the smallest n such that x_n = 1. (For example, d(100) = 3 and d(87) = 7.) Let m be the number of positive integers x such that d(x) = 20. Find the sum of the distinct prime factors of m.

MCrawford (Mar 24, 2004 8:49:11 PM)
This is one of the harder problems to ever appear on the AIME for a number of reasons. First, it is time consuming just to get a grip on what is going on in this problem. Second, the wrinkles in this problem seem to prevent us from developing an elegant solution. This might even encourage us to change methodologies several times. On a test as long as this AIME my advice would be to skip this problem unless you're simply done with all the rest with time to spare.

MCrawford (Mar 24, 2004 8:49:34 PM)
How might we approach this problem?

masamune2387 (Mar 24, 2004 8:49:49 PM)
Understand it

justdudxit (Mar 24, 2004 8:49:57 PM)
start with small cases. Then skip it

Mr.Ocax (Mar 24, 2004 8:50:14 PM)
start out at the end and work backwards?

MCrawford (Mar 24, 2004 8:50:30 PM)
Sometimes this is a good idea. I'm not sure if it's easy in this case.

MPS-vras (Mar 24, 2004 8:50:37 PM)
examine the function first, then try to figure what d(x) counts

Fermatprime (Mar 24, 2004 8:50:52 PM)
Play around with it until you think you have an approach?

Dark_Shadow (Mar 24, 2004 8:50:55 PM)
build a tree

MCrawford (Mar 24, 2004 8:51:01 PM)
The most obvious route to take on a problem such as this one is to look for a way to relate the quantities d(1), d(2),…, d(n),… and use that relationship to establish a count. Unfortunately this problem does not seem to lend itself to nice combinatoric or other counting manipulations and the count seems to be too large to want to attempt the casework by brute-force. Most experienced students should at this point imagine the possibility of a recursive relationship.

Hexahedron (Mar 24, 2004 8:51:34 PM)
yeah make a tree starting at the end 1,10 then 9 or 100......

MCrawford (Mar 24, 2004 8:51:47 PM)
Unfortunately you'll be drawing that tree when you sigh your last breath.

MCrawford (Mar 24, 2004 8:51:53 PM)
Now, let's first get a grip on the function f(x). We see that there are 3 ways in which f is defined for various positive integers. We will be dealing with a sequence {x_n} that is a sequence of compositions of f. How might we explore the behavior of {x_n}?

dgf (Mar 24, 2004 8:52:23 PM)
try some numbers

MCrawford (Mar 24, 2004 8:52:29 PM)
It seems reasonable to play around with some possible values until we have a good grip on the behavior of {x_n} (and also how that behavior relates to the definition of f(x)).

MCrawford (Mar 24, 2004 8:52:39 PM)
f(11) = 12, f(12) = 13, f(13) = 14, f(14) = 15, f(15) = 16, f(16) = 17, f(17) = 18, f(18) = 19, f(19) = 20, f(20) = 2, f(2) = 3, f(3) = 4, f(4) = 5, f(5) = 6, f(6) = 7, f(7) = 8, f(8) = 9, f(9) = 10, f(10) = 1.

MCrawford (Mar 24, 2004 8:52:57 PM)
This tells us that if x = x_1 = 11, then x_2 = 12, x_3 = 13,…, x_20 = 1. This also tells us that d(11) = 20, d(12) = 19, …, d(1) = 1.

MCrawford (Mar 24, 2004 8:53:11 PM)
What important features do we notice about f(x) and {x_n} that affect our understanding about how d(x) will behave?

Dark_Shadow (Mar 24, 2004 8:53:24 PM)
wait wait WAIT! doesn't each number have two values from whence it can come from? (10x and x-1?

Dark_Shadow (Mar 24, 2004 8:53:31 PM)
except for those that end in one from which there is only one?

MCrawford (Mar 24, 2004 8:53:54 PM)
Most of the time f(x) = x + 1, but there are two other pieces to the function that we must work with. It seems difficult to establish a recursion or relationship straight from looking at the function definition so we think to try calculate some totals for the numbers of x such that d(x) = m for small integers m.

MCrawford (Mar 24, 2004 8:54:21 PM)
We first note that d(1) = 1. x = 1 is clearly the only value for which d(x) = 1.

MCrawford (Mar 24, 2004 8:54:32 PM)
For how many x will d(x) = 2?

dgf (Mar 24, 2004 8:54:35 PM)
the second to the last therm must be 10

MCrawford (Mar 24, 2004 8:54:42 PM)
In order for d(x) = 2, x_2 = 1 = f(x_1) = f(x). The only ways to produce a 1 are if x = 1 and x = 10. Since we already know d(1) = 1, d(10) = 2 and x = 10 is the only x such that d(x) = 2.

MCrawford (Mar 24, 2004 8:54:54 PM)
For how many x will d(x) = 3?

empyrealpaladin (Mar 24, 2004 8:55:37 PM)
2

tuillip (Mar 24, 2004 8:55:40 PM)
2: 9, 100

MCrawford (Mar 24, 2004 8:55:49 PM)
In order for d(x) = 3, x_3 = 1 = f(x_2) = f(f(x_1)) = f(f(x)). f(f(x)) = 1 when f(x) = 1 or 10. We don't worry about the 1 since we only care about sequences where x_3 is the first 1. Thus f(x) = 10. By the definition of f(x), f(x) = 10 means that either x = 100 or x = 9, so there are 2 x such that d(x) = 3.

MCrawford (Mar 24, 2004 8:56:06 PM)
For how many x will d(x) = 4?

tuillip (Mar 24, 2004 8:56:32 PM)
4: 8, 99, 90, 1000

dgf (Mar 24, 2004 8:56:40 PM)
f(x) = 9 or 100, so 8, 90, 99, 1000

MCrawford (Mar 24, 2004 8:56:47 PM)
Using some of the chain of values we have already established we know that we want x_2 to be either 9 or 100. For what x will f(x) = 9 or f(x) = 100?

MCrawford (Mar 24, 2004 8:56:58 PM)
f(8) = f(90) = 9. f(99) = f(1000) = 100. There are 4 values of x such that d(x) = 4.

MCrawford (Mar 24, 2004 8:57:10 PM)
It seems as though the number of x such that d(x) = m is based on the number of x such that d(x) = m - 1. In fact, we have been taking each x such that d(x) = m - 1 and either subtracting 1 or multiplying by 10. Could the total be doubling each and every time?

Dark_Shadow (Mar 24, 2004 8:57:41 PM)
no, because 11 doesn't have two places to come from-- only 110

dgf (Mar 24, 2004 8:57:46 PM)
no: when we get 2 as a solution

MCrawford (Mar 24, 2004 8:57:59 PM)
It seems as though the number of x such that d(x) = m is based on the number of x such that d(x) = m - 1. In fact, we have been taking each x such that d(x) = m - 1 and either subtracting 1 or multiplying by 10. Could the total be doubling each and every time?

MCrawford (Mar 24, 2004 8:58:29 PM)
If we let g(m) be the total number of x such that d(x) = m then we have g(1) = 1, g(2) = 1, g(3) = 2, and g(4) = 4. Why didn't g double as we went from g(1) to g(2)?

bookworm271828 (Mar 24, 2004 8:59:02 PM)
1 can only go to 10, not 0

Dark_Shadow (Mar 24, 2004 8:59:05 PM)
1 can't come from 0 and 10, only 10

MCrawford (Mar 24, 2004 8:59:20 PM)
We have found values of x such that d(x) = m by either subtracting 1 from x such that d(x) = m - 1 or multiplying those x by 10. However, we can't always subtract 1 or multiply by 10. When will one or both of these processes fail?

Fermatprime (Mar 24, 2004 8:59:45 PM)
When we get to a number ending in 1.

dgf (Mar 24, 2004 8:59:47 PM)
just like 2 won't be able to come from 1 and 20, just 20

MCrawford (Mar 24, 2004 9:00:02 PM)
We can always multiply by 10. f(10x) = x, so if x_n = 10x, x_(n+1) = x. We can't however always subtract 1 from an x such that f(x) = m - 1 to get an x such that f(x) = m. This is because f(x) does not equal x + 1 when x is a multiple of 10 or x = 1. This latter wrinkle is the reason why g(2) = 1, not 2. We could multiply 1 by 10 to get to 10, but if we subtracted 1 from 1 we would no longer have a positive integer.

MCrawford (Mar 24, 2004 9:00:24 PM)
How can we use what we have discovered to find g(20)?

MCrawford (Mar 24, 2004 9:00:49 PM)
We note that g(4) = 2g(3) = 2(2g(2)), so doubling does seem to work some of the time. Why is that?

Fermatprime (Mar 24, 2004 9:01:18 PM)
Because those are "simpler" cases.

justdudxit (Mar 24, 2004 9:01:20 PM)
usually there are 2 ways to get to x

htam (Mar 24, 2004 9:01:25 PM)
count how many of them ends in 1 or is precisely 2 in each group

zabelman (Mar 24, 2004 9:01:29 PM)
since none of the numbers end in 1 or are equal to 2

MCrawford (Mar 24, 2004 9:01:40 PM)
We can double most of the time as long as we are aware of when x has a units digit of 1 or x = 2 (this exception is extremely important to note). There are no such x for which d(x) = 2, 3, 4, 5,… . When will we start running into x = 2 or units digits of 1?

dts (Mar 24, 2004 9:02:32 PM)
d(x)=10

MCrawford (Mar 24, 2004 9:02:39 PM)
d(2) = 10, so g doubles from g(2) until g(10 + 1): g(1) = 1, g(2) = 1, g(3) = 2, g(4) = 2^2, g(5) = 2^3,…, g(10) = 2^8. What is g(11)?

Dark_Shadow (Mar 24, 2004 9:02:56 PM)
2^9 - 1

empyrealpaladin (Mar 24, 2004 9:03:06 PM)
2^9-1

MCrawford (Mar 24, 2004 9:03:07 PM)
g(11) will include x that are 10 times the x for which d(x) = 10 and also x that are 1 less than the x for which d(x) = 10 except for x = 2. Thus g(11) = 2g(10) - 1 = 2^9 - 1.

MCrawford (Mar 24, 2004 9:03:17 PM)
How does g now behave as it goes up from g(11)?

Mr.Ocax (Mar 24, 2004 9:03:34 PM)
the same until we hit another 1

MCrawford (Mar 24, 2004 9:03:42 PM)
We have already dealt with the x = 2 problem, so we now need only pay attention to situations where x has a units digit of 1. When does that happen?

htam (Mar 24, 2004 9:04:35 PM)
starting from g(12), every step

MCrawford (Mar 24, 2004 9:05:25 PM)
How do we know?

dgf (Mar 24, 2004 9:06:23 PM)
we have to start finding d(11), d(21), d(31), etc and try to find where the next turn will be

MCrawford (Mar 24, 2004 9:06:40 PM)
What is min{d(11), d(12), ..., d(91)}?

htam (Mar 24, 2004 9:06:57 PM)
g(12) will get the one that grew from the tree 1-10-100-99-98, etc and the rest will AT LEAST have the one from n-10n where n is [2,10] from the original series

empyrealpaladin (Mar 24, 2004 9:07:23 PM)
d(91)

MCrawford (Mar 24, 2004 9:07:27 PM)
What is that equal to?

lculus (Mar 24, 2004 9:08:13 PM)
d(91)=12

MCrawford (Mar 24, 2004 9:08:16 PM)
d(91) = 12 and involves the smallest possible path from a number with a units digit of 1 to a power of 10 through addition of 1's and/or divisions by 10.

MCrawford (Mar 24, 2004 9:08:35 PM)
Since g(11) doesn't count any possibilities where x has a units digit of 1, we know that g(12) = 2g(11) = 2^9 - 2.

MCrawford (Mar 24, 2004 9:08:48 PM)
However, we must now begin subtracting out x with units digits of 1 after each doubling. How can we count the total number of x with units digits of 1 such that d(x) = 12, 13, 14,…, 19?

Fermatprime (Mar 24, 2004 9:09:31 PM)
Recursively?

MCrawford (Mar 24, 2004 9:09:34 PM)
But how?

MCrawford (Mar 24, 2004 9:10:13 PM)
How many exceptions must we subtract from 2g(12) when calculating g(13)? Or from 2g(n) when calculating g(n+1) for the values we're interested in?

MCrawford (Mar 24, 2004 9:10:49 PM)
Working backwards, how do we ever arrive at a units digit of 1?

zabelman (Mar 24, 2004 9:11:14 PM)
multiply by 10 a few times and then subtract 1 9 times

MCrawford (Mar 24, 2004 9:11:32 PM)
What does that mean in regards to our next calculations?

htam (Mar 24, 2004 9:13:31 PM)
g(n-10) since g(12) cares how many in 3 that has 0 and that is how many g(2) there are

MCrawford (Mar 24, 2004 9:13:44 PM)
Very close. But the exact right idea.

zabelman (Mar 24, 2004 9:13:48 PM)
i think the number of exceptions doubles at each stage

htam (Mar 24, 2004 9:15:02 PM)
actually g(13) cares about that, so is g(n-11)

MCrawford (Mar 24, 2004 9:15:15 PM)
For each time there is a units digit of 1 there were 9 immediately previous steps in which 1 was subtracted from a previous x and 1 in which x was multiplied by 10. This means that our new step from g(12) to g(13) excludes a number of x equal to g(2).

MCrawford (Mar 24, 2004 9:15:53 PM)
This means that g(13) = 2g(12) - g(2) = 2^11 - 2^2 - 1. Likewise, g(14) = 2g(13) - g(3) = 2^12 - 2^3 - 2^2, g(15) = 2g(14) - g(4) = 2^13 - 2^4 - 2^3 - 2^2, g(16) = 2g(15) - g(5) = 2^14 - 2^6, g(17) = 2g(16) - g(6) = 2^15 - 2^7 - 2^4, g(18) = 2g(17) - g(7) = 2^16 - 2^8 - 2^6, g(19) = 2g(18) - g(8) = 2^17 - 2^9 - 2^7 - 2^6, g(20) = 2g(19) - g(9) = 2^18 - 2^10 - 2^9 = 2^9(2^9 - 2 - 1) = 512(509).

MCrawford (Mar 24, 2004 9:16:05 PM)
Since 509 is prime, our answer is 2 + 509 = 511.

MCrawford (Mar 24, 2004 9:16:28 PM)
This problem contained a number of serious difficulties. First, we are dealing with two functions and a sequence. The first function is a piecewise function and so we have an intricate set of details to work around. These difficulties might lead us to alter our methodologies as we fail to hone in on an elegant solution. This problem is so time consuming that changing paths means letting go of a large time investment.

MCrawford (Mar 24, 2004 9:17:02 PM)
That is all for tonight.

MCrawford (Mar 24, 2004 9:17:10 PM)
Any questions about the problems?

masamune2387 (Mar 24, 2004 9:17:19 PM)
how many people in here actually got it? (say yes if you did)

MCrawford (Mar 24, 2004 9:18:05 PM)
This is one of the hardest aime problems ever. I doubt many people got it.

MCrawford (Mar 24, 2004 9:18:15 PM)
Very time consuming.