## AIME

Go back to the Math Jam Archive
**Copyright © 2015 AoPS Incorporated. This page is copyrighted
material. You can view and print this page for your own use, but you cannot
share the contents of this file with others.**

#### Facilitator: Mathew Crawford

2

3

4

5

6

7

8

9

10

11

12

13

14

15

**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.