1994 AIME — Problems & Online Timed Exam

1.

The increasing sequence

3,

15,

24,

48,

\ldots

consists of those positive multiples of

3

that are one less than a perfect square. What is the remainder when the

1994

th term of the sequence is divided by

1000?

Answer

Answer: 63

Concepts:modular arithmetic counting integers in a range perfect square

Difficulty rating: 1640

Small hint:

A number

k^2-1

is divisible by

3

exactly when

k

is not divisible by

3

Big hint:

Index the eligible values of

k

in pairs, then reduce the required square modulo

1000

Solution:

The terms are

k^2-1

for integers

k\geq2

not divisible by

3.

In each block of three consecutive

k

’s there are two eligible values. The

1994=2\cdot997

th corresponds to

k=3(997)+1=2992.

Since

2992\equiv992\equiv-8\pmod {1000},

\begin{aligned}k^2-1&\equiv(-8)^2-1\\&\equiv63\pmod {1000}.\end{aligned}

2.

A circle with diameter

\overline{PQ}

of length

10

is internally tangent at

P

to a circle of radius

20.

Square

ABCD

is constructed with

A

and

B

on the larger circle,

\overline{CD}

tangent at

Q

to the smaller circle, and the smaller circle outside

ABCD.

The length of

\overline{AB}

can be written in the form

m+\sqrt n,

where

m

and

n

are integers. Find

m+n.

Answer

Answer: 312

Concepts:chord square (geometry)quadratic

Difficulty rating: 2170

Small hint:

Place the large circle at the origin and put

P

and

Q

on a diameter

Big hint:

If the square’s side is

s

, its chord side

AB

lies at distance

|10-s|

from the large circle’s center

Solution:

Put the large circle at the origin with

P=(20,0)

and

Q=(10,0).

Let the square’s side be

s.

Because the smaller circle is outside the square,

\overline{CD}

lies on

x=10

and the parallel chord

\overline{AB}

lies on

x=10-s.

A chord of the radius-

20

circle then gives

s=2\sqrt{400-(10-s)^2}.

Squaring yields

s^2-16s-240=0,

so

s=8+4\sqrt{19}=8+\sqrt{304}.

Thus

m+n=8+304=312.

3.

The function

f

has the property that, for each real number

x,

f(x)+f(x-1)=x^2.

If

f(19)=94,

what is the remainder when

f(94)

is divided by

1000?

Answer

Answer: 561

Concepts:recursion summation modular arithmetic

Difficulty rating: 1900

Small hint:

First use

x=20

to find

f(20)

Big hint:

Eliminate alternating terms by deriving a recurrence from

f(x)

to

f(x-2)

Solution:

First

f(20)=20^2-f(19)=306.

Subtracting through two steps gives

\begin{aligned}f(x)&=x^2-(x-1)^2+f(x-2)\\&=2x-1+f(x-2).\end{aligned}

Therefore

\begin{aligned}f(94)&=306+\sum_{j=11}^{47}(4j-1)\\&=306+4(1073)-37\\&=4561.\end{aligned}

The requested remainder is

561.

4.

Find the positive integer

n

for which

\begin{aligned}&\lfloor\log_2 1\rfloor+\lfloor\log_2 2\rfloor+\lfloor\log_2 3\rfloor\\&\quad+\cdots+\lfloor\log_2 n\rfloor=1994.\end{aligned}

(For real

x,

\lfloor x\rfloor

is the greatest integer not exceeding

x.

)

Answer

Answer: 312

Concepts:floor and ceiling functions logarithm power of 2

Difficulty rating: 1980

Small hint:

Group integers having the same value of

\lfloor\log_2 k\rfloor

Big hint:

Compute the sum through

255

, after which every new term initially contributes

8

Solution:

For

2^j\leq k<2^{j+1},

the summand is

j.

Thus the sum through

255=2^8-1

is

\sum_{j=0}^7j2^j=(8-2)2^8+2=1538.

The remaining

1994-1538=456

is

57\cdot8,

so we include

57

more integers beginning with

256.

Hence

n=255+57=312.

5.

Given a positive integer

n,

let

p(n)

be the product of the nonzero digits of

n.

(If

n

has only one digit, then

p(n)

is equal to that digit.) Let

\begin{aligned}S&=p(1)+p(2)+p(3)\\&\quad+\cdots+p(999).\end{aligned}

What is the largest prime factor of

S?

Answer

Answer: 103

Concepts:digits multiplication principle prime factorization

Difficulty rating: 2110

Small hint:

Write every number from

000

through

999

using three digits and let a zero digit contribute a factor of

1

Big hint:

The sum factors by digit position; remember to remove the contribution of

000

Solution:

For one digit position, the sum of its effective factors is

1+1+2+\cdots+9=46,

where the first

1

represents digit

0.

Thus the sum over

000

through

999

is

46^3.

Removing the artificial contribution

1

from

000

gives

\begin{aligned}S&=46^3-1\\&=45(46^2+46+1)\\&=45\cdot2163.\end{aligned}

Since

2163=3\cdot721=3\cdot7\cdot103,

the largest prime factor is

103.

6.

The graphs of the equations

\begin{aligned}y&=k,\\y&=\sqrt3x+2k,\\y&=-\sqrt3x+2k,\end{aligned}

are drawn in the coordinate plane for

k=-10,

-9,

-8,

\ldots,

9,

10.

These

63

lines cut part of the plane into equilateral triangles of side

\frac{2}{\sqrt3}.

How many such triangles are formed?

Answer

Answer: 660

Concepts:equilateral triangle counting regions counting pairs

Difficulty rating: 2350

Small hint:

Index one line from each family by

i,j,k

in

[-10,10]

Big hint:

A smallest triangular cell occurs precisely when

i=j+k+1

or

i=j+k-1

Solution:

A unit triangular cell is determined by indices

i,j,k\in[-10,10]

satisfying

i=j+k\pm1.

For the plus sign,

-11\leq j+k\leq9.

There are

21-|s|

ordered pairs

(j,k)

with sum

s,

so this orientation contributes

\sum_{s=-11}^{9}(21-|s|)=330.

By symmetry the other orientation also contributes

330,

for a total of

660.

7.

For certain ordered pairs

(a,b)

of real numbers, the system of equations

\begin{aligned}ax+by&=1,\\x^2+y^2&=50\end{aligned}

has at least one solution, and each solution is an ordered pair

(x,y)

of integers. How many such ordered pairs

(a,b)

are there?

Answer

Answer: 72

Concepts:lattice point chord tangent line

Difficulty rating: 2350

Small hint:

List all integer points on

x^2+y^2=50

Big hint:

Count both chords through two non-antipodal lattice points and tangents at one lattice point

Solution:

The circle has the

12

lattice points obtained from

(\pm1,\pm7),

(\pm5,\pm5),

and

(\pm7,\pm1).

A secant satisfying the condition is determined by any two non-antipodal lattice points. This gives

\binom{12}{2}-6=60

lines; antipodal pairs are excluded because their line passes through the origin and cannot have equation

ax+by=1.

There are also

12

tangents, one at each lattice point. Each line has a unique normalization

ax+by=1,

so the total is

60+12=72.

8.

The points

(0,0),

(a,11),

and

(b,37)

are the vertices of an equilateral triangle. Find the value of

ab.

Answer

Answer: 315

Concepts:coordinate geometry vector equilateral triangle

Difficulty rating: 1940

Small hint:

The vector

(b,37)

is a rotation of

(a,11)

through

60^\circ

or

-60^\circ

Big hint:

Use the second coordinate of the rotation first, then compute the first coordinate

Solution:

For a

60^\circ

rotation,

37=\frac{\sqrt3}{2}a+\frac{11}{2},

so

a=21\sqrt3.

The first coordinate is then

b=\frac a2-\frac{11\sqrt3}{2}=5\sqrt3.

The opposite orientation changes both signs and leaves the product unchanged. Hence

ab=(21\sqrt3)(5\sqrt3)=315.

9.

A solitaire game is played as follows. Six distinct pairs of matched tiles are placed in a bag. The player randomly draws tiles one at a time from the bag and retains them, except that matching tiles are put aside as soon as they appear in the player’s hand. The game ends if the player ever holds three tiles, no two of which match; otherwise the drawing continues until the bag is empty. The probability that the bag will be emptied is

\frac{p}{q},

where

p

and

q

are relatively prime positive integers. Find

p+q.

Answer

Answer: 394

Concepts:recursive probability sampling without replacement process simulation

Difficulty rating: 2460

Small hint:

Track the number

r

of unseen pairs and the number

h

of unmatched tiles currently held

Big hint:

From state

(r,h)

, the next tile either matches one of the

h

held tiles or opens one of the

r

unseen pairs

Solution:

Let

F(r,h)

be the chance of success with

r

unseen pairs and

h\leq2

unmatched tiles held. Among

2r+h

remaining tiles,

h

close an open pair and

2r

open a new pair; the latter move fails when

h=2.

Thus

\begin{aligned}F(r,h)&=\frac{hF(r,h-1)}{2r+h}\\&\quad+\frac{2rF(r-1,h+1)}{2r+h},\end{aligned}

omitting the second term when

h=2,

with

F(0,h)=1.

Evaluating this three-state recursion gives

\begin{aligned}F(r,0):\quad&1,\ 1,\ \frac35,\ \frac9{35},\\&\frac3{35},\ \frac9{385}\end{aligned}

for

r=1,2,\ldots,6.

Hence

\frac{p}{q}=\frac{9}{385}

and

p+q=394.

10.

In triangle

ABC,

angle

C

is a right angle and the altitude from

C

meets

\overline{AB}

at

D.

The lengths of the sides of

\triangle ABC

are integers,

BD=29^3,

and

\cos B=\frac{m}{n},

where

m

and

n

are relatively prime positive integers. Find

m+n.

Answer

Answer: 450

Concepts:altitude Pythagorean Triple divisibility

Difficulty rating: 2270

Small hint:

Use similarity to write

BD=\frac{BC^2}{AB}

Big hint:

Express

\frac{BC}{AB}=\frac{m}{n}

in lowest terms and use the prime factorization of

29^3

Solution:

Write

\frac{BC}{AB}=\frac{m}{n}

in lowest terms, with

BC=km

and

AB=kn.

Similarity gives

29^3=BD=\frac{BC^2}{AB}=\frac{km^2}{n}.

Hence

k

is divisible by

n;

writing

k=nt

gives

tm^2=29^3.

The possibility

m=1

cannot be a leg of a nondegenerate integer right triangle, so

m=29.

Writing the other leg of the primitive triple as

u,

we have

(n-u)(n+u)=29^2,

giving

n=421

and

u=420.

Therefore

m+n=29+421=450.

11.

Ninety-four bricks, each measuring

4''\times10''\times19'',

are to be stacked one on top of another to form a tower

94

bricks tall. Each brick can be oriented so it contributes

4'',

10'',

or

19''

to the total height of the tower. How many different tower heights can be achieved using all

94

of the bricks?

Answer

Answer: 465

Concepts:Diophantine Equation parity counting integers in a range

Difficulty rating: 2270

Small hint:

Start with all bricks contributing

4

inches and count possible increments

Big hint:

If

c

bricks contribute

19

inches, the remaining increments form a parity interval as the number of

10

-inch bricks varies

Solution:

If

b

bricks use height

10

and

c

use height

19,

the total is

376+3(2b+5c),

where

b,c\geq0

and

b+c\leq94.

For fixed

c,

the value

v=2b+5c

runs by twos from

5c

to

188+3c.

The even-

c

intervals cover every even

v

from

0

through

464,

as well as

470,

missing only

466

and

468.

The odd-

c

intervals cover every odd

v

from

5

through

461,

as well as

465

and

467,

missing only

1,

3,

463,

and

469.

Thus there are

471-6=465

distinct heights.

12.

A fenced, rectangular field measures

24

meters by

52

meters. An agricultural researcher has

1994

meters of fence that can be used for internal fencing to partition the field into congruent, square test plots. The entire field must be partitioned, and the sides of the squares must be parallel to the edges of the field. What is the largest number of square test plots into which the field can be partitioned using all or some of the

1994

meters of fence?

Answer

Answer: 702

Concepts:tiling divisibility optimization

Difficulty rating: 1900

Small hint:

If there are

m

rows and

n

columns, equality of square side lengths forces

m:n=6:13

Big hint:

Write

m=6k

and

n=13k

, then calculate only the internal fence length

Solution:

Let the grid have

6k

rows and

13k

columns, so each square has side

\frac{4}{k}.

The internal vertical and horizontal fences have total length

\begin{aligned}&52(6k-1)+24(13k-1)\\&\quad=624k-76.\end{aligned}

Requiring this to be at most

1994

gives

k\leq3.

With

k=3,

the number of plots is

(6k)(13k)=78k^2=702.

13.

The equation

x^{10}+(13x-1)^{10}=0

has

10

complex roots

r_1,

\overline{r_1},

r_2,

\overline{r_2},

r_3,

\overline{r_3},

r_4,

\overline{r_4},

r_5,

\overline{r_5},

where the bar denotes complex conjugation. Find the value of

\begin{aligned}&\frac1{r_1\overline{r_1}}+\frac1{r_2\overline{r_2}}+\frac1{r_3\overline{r_3}}\\&\quad+\frac1{r_4\overline{r_4}}+\frac1{r_5\overline{r_5}}.\end{aligned}

Answer

Answer: 850

Concepts:roots of unity complex number summation

Difficulty rating: 2650

Small hint:

Set

\frac{x}{13x-1}=\zeta,

where

\zeta^{10}=-1

Big hint:

Express

\frac{1}{|x|^2}

in terms of

\zeta+\overline\zeta

and sum over the five conjugate pairs

Solution:

Let

\zeta=\frac{x}{13x-1},

so

\zeta^{10}=-1

and

\begin{aligned}x&=\frac{\zeta}{13\zeta-1},\\\frac1x&=13-\zeta^{-1}.\end{aligned}

Since

|\zeta|=1,

\begin{aligned}\frac1{|x|^2}&=|13-\zeta^{-1}|^2\\&=170-13(\zeta+\overline\zeta).\end{aligned}

Summing one value for each of the five conjugate pairs gives

5\cdot170

minus

13

times the sum of all ten roots of

z^{10}+1,

which is

0.

The requested value is

850.

14.

A beam of light strikes

\overline{BC}

at point

C

with angle of incidence

\alpha=19.94^\circ

and reflects with an equal angle of reflection as shown. The light beam continues its path, reflecting off line segments

\overline{AB}

and

\overline{BC}

according to the rule: angle of incidence equals angle of reflection. Given that

\beta=\frac{\alpha}{10}=1.994^\circ

and

AB=BC,

determine the number of times the light beam will bounce off the two line segments. Include the first reflection at

C

in your count.

Answer

Answer: 71

Concepts:reflection (geometry)angle chasing floor and ceiling functions

Difficulty rating: 2790

Small hint:

Unfold each reflection by reflecting the next copy of the two-segment angle instead of reflecting the beam

Big hint:

After

k

reflections beyond the first one, the relevant boundary ray has turned through

k\beta

Solution:

Unfold the path at each bounce, so the beam becomes one straight line crossing successive reflected copies of the angle at

B.

After

k

reflections beyond the initial reflection at

C,

the next boundary ray makes angle

k\beta

with the original one. Using

AB=BC,

the crossing remains on the finite segments exactly while

k\beta\leq180^\circ-2\alpha.

Therefore

k\leq\frac{180-2(19.94)}{1.994}\approx70.27,

so there are

70

further reflections. Including the first reflection at

C

gives

71.

15.

Given a point

P

on a triangular piece of paper

ABC,

consider the creases that are formed in the paper when

A,

B,

and

C

are folded onto

P.

Let us call

P

a fold point of

\triangle ABC

if these creases, which number three unless

P

is one of the vertices, do not intersect. Suppose that

AB=36,

AC=72,

and

\angle B=90^\circ.

Then the area of the set of all fold points of

\triangle ABC

can be written in the form

q\pi-r\sqrt s,

where

q,

r,

and

s

are positive integers and

s

is not divisible by the square of any prime. What is

q+r+s?

Answer

Answer: 597

Concepts:paper folding perpendicular bisector area decomposition

Difficulty rating: 2840

Small hint:

Two fold creases meet at the circumcenter of the triangle formed by

P

and the corresponding two vertices

Big hint:

The fold-point locus is the intersection of the disks with diameters

AB

and

BC

Solution:

The creases for two vertices meet at the circumcenter of the triangle formed with

P.

This intersection lies off the paper exactly when the angle at

P

is obtuse, so the fold-point locus is the intersection of the three diameter disks for

AB,

BC,

and

CA.

The

CA

disk contains the entire right triangle, leaving the intersection of the

AB

and

BC

disks.

Here

BC=\sqrt{72^2-36^2}=36\sqrt3.

The two relevant radii are

18

and

18\sqrt3,

and their lens consists of circular segments with central angles

120^\circ

and

60^\circ.

Its area is

\begin{aligned}&\left(\frac\pi3\cdot18^2\right.\\&\qquad\left.-\frac12\cdot18^2\sin120^\circ\right)\\&+\left(\frac\pi6(18\sqrt3)^2\right.\\&\qquad\left.-\frac12(18\sqrt3)^2\sin60^\circ\right)\\&=270\pi-324\sqrt3.\end{aligned}

Thus

q+r+s

equals

270+324+3=597.

1994 AIME Problems

Answer: 63

Difficulty rating: 1640

Small hint:

Big hint:

Solution:

Answer: 312

Difficulty rating: 2170

Small hint:

Big hint:

Solution:

Answer: 561

Difficulty rating: 1900

Small hint:

Big hint:

Solution:

Answer: 312

Difficulty rating: 1980

Small hint:

Big hint:

Solution:

Answer: 103

Difficulty rating: 2110

Small hint:

Big hint:

Solution:

Answer: 660

Difficulty rating: 2350

Small hint:

Big hint:

Solution:

Answer: 72

Difficulty rating: 2350

Small hint:

Big hint:

Solution:

Answer: 315

Difficulty rating: 1940

Small hint:

Big hint:

Solution:

Answer: 394

Difficulty rating: 2460

Small hint:

Big hint:

Solution:

Answer: 450

Difficulty rating: 2270

Small hint:

Big hint:

Solution:

Answer: 465

Difficulty rating: 2270

Small hint:

Big hint:

Solution:

Answer: 702

Difficulty rating: 1900

Small hint:

Big hint:

Solution:

Answer: 850

Difficulty rating: 2650

Small hint:

Big hint:

Solution:

Answer: 71

Difficulty rating: 2790

Small hint:

Big hint:

Solution:

Answer: 597

Difficulty rating: 2840

Small hint:

Big hint:

Solution: