1988 AIME — Problems & Online Timed Exam

1.

One commercially available ten-button lock may be opened by depressing—in any order—the correct five buttons. One sample has

\{1,2,3,6,9\}

as its combination. Suppose that these locks are redesigned so that sets of as many as nine buttons or as few as one button could serve as combinations. How many additional combinations would this allow?

Answer

Answer: 770

Concepts:combinations subsets complementary counting

Difficulty rating: 1630

Small hint:

Count all nonempty proper subsets of the ten buttons

Big hint:

Subtract the five-button combinations that the original design already allowed

Solution:

The redesigned lock permits every nonempty subset except the full set, giving

2^{10}-2=1022

combinations. The original lock permits

\binom{10}{5}=252.

Thus the number of additional combinations is

1022-252=770.

2.

For any positive integer

k,

let

f_1(k)

denote the square of the sum of the digits of

k.

For

n\geq2,

let

f_n(k)=f_1(f_{n-1}(k)).

Find

f_{1988}(11).

Answer

Answer: 169

Concepts:digits recursion pattern recognition

Difficulty rating: 1690

Small hint:

Compute the first several iterates until a value repeats

Big hint:

After the transient values, the sequence alternates between two numbers

Solution:

The iterates begin

4,

16,

49,

169,

256,

followed by

169,

256,

\ldots.

Thus from the fourth iterate onward, even indices give

169

and odd indices give

256.

Since

1988

is even,

f_{1988}(11)=169.

3.

Find

(\log_2 x)^2

if

\log_2(\log_8 x)=\log_8(\log_2 x).

Answer

Answer: 27

Concepts:logarithm substitution algebraic manipulation

Difficulty rating: 1860

Small hint:

Set

y=\log_2x

and rewrite every base-

8

logarithm in base

2

Big hint:

Solve the resulting linear equation for

\log_2 y

Solution:

Put

y=\log_2x\gt0.

Since

\log_8x=\frac{y}{3},

the equation becomes

\log_2(\frac{y}{3})=\frac13\log_2y.

Hence

\frac23\log_2y=\log_23,

so

y=3^{\frac{3}{2}}=3\sqrt3.

Therefore

(\log_2x)^2=y^2=27.

4.

Suppose that

|x_i|\lt1

for

i=1,

2,

\ldots,

n.

Suppose further that

\begin{aligned}&|x_1|+|x_2|+\cdots+|x_n|\\&=19+\bigl|x_1+x_2\\&\qquad+\cdots+x_n\bigr|.\end{aligned}

What is the smallest possible value of

n?

Answer

Answer: 20

Concepts:absolute value inequality extremal argument

Difficulty rating: 1920

Small hint:

Let

P

be the sum of the positive terms and

N

the sum of the absolute values of the negative terms

Big hint:

The left side minus the final absolute value equals

2\min(P,N)

Solution:

Let

P

be the sum of the positive

x_i

and

N

the sum of the absolute values of the negative

x_i.

Then

\begin{aligned}P+N-|P-N|&=2\min(P,N)\\&=19,\end{aligned}

so both

P

and

N

are at least

9.5.

Because every

|x_i|\lt1,

each sign requires at least

10

terms, giving

n\geq20.

Equality is attainable with ten terms equal to

0.95

and ten equal to

-0.95,

so the minimum is

20.

5.

Let

\frac{m}{n},

in lowest terms, be the probability that a randomly chosen positive divisor of

10^{99}

is an integer multiple of

10^{88}.

Find

m+n.

Answer

Answer: 634

Concepts:factor counting basic probability prime factorization

Difficulty rating: 1770

Small hint:

Write every divisor as

2^a5^b

Big hint:

Count exponent pairs with

a\geq88

and

b\geq88

and reduce the resulting probability

Solution:

Every divisor is

2^a5^b

with

0\leq a\leq99

and

0\leq b\leq99,

so there are

100^2=10000

divisors. A multiple of

10^{88}

requires

88\leq a\leq99

and

88\leq b\leq99,

giving

12^2=144

divisors. The probability is

\frac{144}{10000}=\frac{9}{625},

and

m+n=9+625=634.

6.

It is possible to place positive integers into the vacant twenty-one squares of the

5\times5

square shown below so that the numbers in each row and column form arithmetic sequences. Find the number that must occupy the vacant square marked by the asterisk

(*).

Answer

Answer: 142

Concepts:arithmetic sequence pattern recognition system of equations

Difficulty rating: 2030

Small hint:

Index the rows and columns from

0

through

4

Big hint:

A grid whose rows and columns are arithmetic has the form

A+Bi+Cj+Dij

Solution:

Index rows and columns from

0

to

4.

The row and column conditions give the general entry

A+Bi+Cj+Dij.

The four shown values yield

\begin{aligned}A+4B&=0,\\A+B+C+D&=74,\\A+2B+4C+8D&=186,\\A+3B+2C+6D&=103.\end{aligned}

Solving gives

A=52,

B=-13,

C=30,

and

D=5.

The asterisk is at

(i,j)=(0,3),

so its value is

A+3C=52+90=142.

7.

In triangle

ABC,

\tan\angle CAB=\frac{22}{7},

and the altitude from

A

divides

BC

into segments of length

3

and

17.

What is the area of triangle

ABC?

Answer

Answer: 110

Concepts:triangle area trigonometry vector

Difficulty rating: 1870

Small hint:

Let the altitude have length

h

and place its foot at the origin

Big hint:

Use cross product over dot product to express the tangent of the angle between the two side vectors

Solution:

Let the altitude length be

h.

From

A,

vectors to the endpoints of

BC

may be taken as

(-3,-h)

and

(17,-h).

Therefore

\tan\angle CAB=\frac{20h}{h^2-51}=\frac{22}{7}.

Thus

11h^2-70h-561=0,

whose positive root is

h=11.

Since

BC=3+17=20,

the area is

\frac12(20)(11)=110.

8.

The function

f,

defined on the set of ordered pairs of positive integers, satisfies the following properties:

\begin{gathered}f(x,x)=x,\\f(x,y)=f(y,x),\\(x+y)f(x,y)=yf(x,x+y).\end{gathered}

Calculate

f(14,52).

Answer

Answer: 364

Concepts:functional equation greatest common divisor least common multiple

Difficulty rating: 2270

Small hint:

Apply the third property to

(x,y-x)

when

y\gt x

Big hint:

Compare the resulting subtraction rule with the same rule for

\operatorname{lcm}(x,y)

Solution:

For

y\gt x,

the third property applied to

(x,y-x)

gives

f(x,y)=\frac{y}{y-x}f(x,y-x).

The least common multiple obeys the identical relation, because

\gcd(x,y)=\gcd(x,y-x).

Hence the quotient

\frac{f(x,y)}{\operatorname{lcm}(x,y)}

is unchanged by each subtraction step of the Euclidean algorithm. On the diagonal it equals

\frac{f(g,g)}{g}=1,

so

f(x,y)=\operatorname{lcm}(x,y).

Therefore

\begin{aligned}f(14,52)&=\frac{14\cdot52}{\gcd(14,52)}\\&=364.\end{aligned}

9.

Find the smallest positive integer whose cube ends in

888.

Answer

Answer: 192

Concepts:modular arithmetic units digit quadratic

Difficulty rating: 1880

Small hint:

The units digit forces the number to have the form

10a+2

Big hint:

Reduce

(10a+2)^3\equiv888\pmod{1000}

first modulo

125

Solution:

Write the number as

10a+2.

Expanding the required congruence modulo

125

and dividing by

5

gives

20a^2-a-1\equiv0\pmod{25}.

Reducing first modulo

5

gives

a\equiv4\pmod5;

substituting

a=4+5b

then gives

b\equiv3\pmod5.

Thus

a\equiv19\pmod{25},

and the smallest candidate is

10(19)+2=192.

It is even, so its cube is also

0\pmod8,

and indeed

192^3=7{,}077{,}888.

10.

A convex polyhedron has for its faces

12

squares,

8

regular hexagons, and

6

regular octagons. At each vertex of the polyhedron one square, one hexagon, and one octagon meet. How many segments joining vertices of the polyhedron lie in the interior of the polyhedron rather than along an edge or a face?

Answer

Answer: 840

Concepts:polyhedron double counting combinations

Difficulty rating: 2170

Small hint:

Double-count face-vertex and face-edge incidences to find

V

and

E

Big hint:

Count all vertex pairs, then subtract pairs lying together on a face, correcting the double count of edges

Solution:

The total number of face-vertex incidences is

12(4)+8(6)+6(8)=144.

Three faces meet at each vertex, so

V=48.

The same sum counts each edge twice, so

E=72.

There are

\binom{48}{2}=1128

vertex pairs. Summing pairs on faces gives

12\binom42+8\binom62+6\binom82=360.

Every edge was counted twice in this sum and every other same-face pair once, so the number of distinct boundary pairs is

360-E=288.

Hence

1128-288=840

joining segments lie in the interior.

11.

Let

w_1,

w_2,

\ldots,

w_n

be complex numbers. A line

L

in the complex plane is called a mean line for the points

w_1,

w_2,

\ldots,

w_n

if

L

contains points (complex numbers)

z_1,

z_2,

\ldots,

z_n

such that

\sum_{k=1}^n(z_k-w_k)=0.

For the numbers

w_1=32+170i,

w_2=-7+64i,

w_3=-9+200i,

w_4=1+27i,

and

w_5=-14+43i,

there is a unique mean line with

y

-intercept

3.

Find the slope of this mean line.

Answer

Answer: 163

Concepts:complex number centroid slope

Difficulty rating: 1970

Small hint:

Average the equation

\sum(z_k-w_k)=0

Big hint:

A mean line is exactly a line through the centroid of the given points

Solution:

The condition says that the average of the

z_k

equals the average of the

w_k.

Since all

z_k

lie on

L,

their average lies on

L;

conversely, any line through the average works by taking all

z_k

equal to that point. The centroid satisfies

\begin{aligned}\bar x&=\frac{32-7-9+1-14}{5}=\frac35,\\\bar y&=\frac{170+64+200+27+43}{5}\\&=\frac{504}{5}.\end{aligned}

The line through this point and

(0,3)

has slope

\frac{\bigl(\frac{504}{5}-3\bigr)}{\frac35}=163.

12.

Let

P

be an interior point of triangle

ABC

and extend lines from the vertices through

P

to the opposite sides. Let

a,

b,

c,

and

d

denote the lengths of the segments indicated in the figure. Find the product

abc

if

a+b+c=43

and

d=3.

Answer

Answer: 441

Concepts:mass points ratio and proportion symmetry (algebra)

Difficulty rating: 2380

Small hint:

Express the three barycentric coordinates of

P

using the ratios

a:d,

b:d,

c:d

Big hint:

Use

\frac3{a+3}+\frac3{b+3}+\frac3{c+3}=1

and expand symmetrically

Solution:

Along the cevian from

A,

the barycentric coordinate at

A

is

\frac{d}{a+d},

and similarly at the other vertices. Since the three coordinates sum to

1

and

d=3,

\frac3{a+3}+\frac3{b+3}+\frac3{c+3}=1.

Put

s_1=a+b+c=43,

s_2=ab+bc+ca,

and

s_3=abc.

Clearing denominators gives

\begin{aligned}3(s_2+6s_1+27)&=s_3+3s_2\\&\quad+9s_1+27.\end{aligned}

Therefore

s_3=9s_1+54,

so

s_3=9(43)+54=441.

13.

Find

a

if

a

and

b

are integers such that

x^2-x-1

is a factor of

ax^{17}+bx^{16}+1.

Answer

Answer: 987

Concepts:polynomial Fibonacci system of equations

Difficulty rating: 2380

Small hint:

Modulo

x^2-x-1,

powers satisfy

x^n=F_nx+F_{n-1}

Big hint:

Set both coefficients of the linear remainder equal to zero and use Cassini’s identity

Solution:

Modulo

x^2-x-1,

the relation

x^2=x+1

gives

x^n=F_nx+F_{n-1}.

Hence the remainder is

\begin{aligned}r(x)={}&(1597a+987b)x\\&+(987a+610b+1).\end{aligned}

Both coefficients must vanish. The determinant of the coefficient matrix is

1597(610)-987^2=1

by Cassini’s identity. Cramer’s rule then gives

a=987.

14.

Let

C

be the graph of

xy=1,

and denote by

C^*

the reflection of

C

in the line

y=2x.

Let the equation of

C^*

be written in the form

12x^2+bxy+cy^2+d=0.

Find the product

bc.

Answer

Answer: 84

Concepts:reflection (geometry)transformation hyperbola

Difficulty rating: 2170

Small hint:

Find the reflection matrix for the line spanned by

(1,2)

Big hint:

Because reflection is its own inverse, substitute the reflected coordinates into

uv=1

Solution:

Reflection in the line spanned by

(1,2)

has matrix

\frac15\begin{pmatrix}-3&4\\4&3\end{pmatrix}.

Thus a point

(x,y)

on

C^*

came from

u=\frac{-3x+4y}{5}

and

v=\frac{4x+3y}{5}

on

C.

Substituting

uv=1

gives

-12x^2+7xy+12y^2-25=0,

or

12x^2-7xy-12y^2+25=0.

Hence

b=-7,

c=-12,

and

bc=84.

15.

In an office at various times during the day, the boss gives the secretary a letter to type, each time putting the letter on top of the pile in the secretary’s in-box. When there is time, the secretary takes the top letter off the pile and types it. There are nine letters to be typed during the day, and the boss delivers them in the order

1,

2,

3,

4,

5,

6,

7,

8,

9.

While leaving for lunch, the secretary tells a colleague that letter

8

has already been typed, but says nothing else about the morning’s typing. The colleague wonders which of the nine letters remain to be typed after lunch and in what order they will be typed. Based upon the above information, how many such after-lunch typing orders are possible? (That there are no letters left to be typed is one of the possibilities.)

Answer

Answer: 704

Concepts:arrangements with restrictions subsets multiplication principle

Difficulty rating: 2520

Small hint:

After

8

has been typed, any remaining letters among

1,\ldots,7

must later be typed in decreasing order

Big hint:

Separate the cases according to whether

9

was typed before lunch or remains to be inserted into the later order

Solution:

Any subset of

1,\ldots,7

can remain in the stack after

8

has been typed, and those remaining letters must later be typed in decreasing order. If

9

was already typed, choosing that subset gives

2^7=128

possible orders.

If

9

remains, choose

k

of the seven smaller letters and insert

9

into any of the

k+1

positions in their decreasing order. This gives

\begin{aligned}\sum_{k=0}^7\binom7k(k+1)&=7\cdot2^6+2^7\\&=576.\end{aligned}

Every such order can be realized by suitable morning choices, so the total is

128+576=704.

1988 AIME Problems

Answer: 770

Difficulty rating: 1630

Small hint:

Big hint:

Solution:

Answer: 169

Difficulty rating: 1690

Small hint:

Big hint:

Solution:

Answer: 27

Difficulty rating: 1860

Small hint:

Big hint:

Solution:

Answer: 20

Difficulty rating: 1920

Small hint:

Big hint:

Solution:

Answer: 634

Difficulty rating: 1770

Small hint:

Big hint:

Solution:

Answer: 142

Difficulty rating: 2030

Small hint:

Big hint:

Solution:

Answer: 110

Difficulty rating: 1870

Small hint:

Big hint:

Solution:

Answer: 364

Difficulty rating: 2270

Small hint:

Big hint:

Solution:

Answer: 192

Difficulty rating: 1880

Small hint:

Big hint:

Solution:

Answer: 840

Difficulty rating: 2170

Small hint:

Big hint:

Solution:

Answer: 163

Difficulty rating: 1970

Small hint:

Big hint:

Solution:

Answer: 441

Difficulty rating: 2380

Small hint:

Big hint:

Solution:

Answer: 987

Difficulty rating: 2380

Small hint:

Big hint:

Solution:

Answer: 84

Difficulty rating: 2170

Small hint:

Big hint:

Solution:

Answer: 704

Difficulty rating: 2520

Small hint:

Big hint:

Solution: