2005 AMC 12A Problem 23

Question

Two distinct numbers

a

and

b

are chosen randomly from the set

\{2, 2^2, 2^3, \ldots, 2^{25}\}.

What is the probability that

\log_a b

is an integer?

\dfrac{2}{25}

\dfrac{31}{300}

\dfrac{13}{100}

\dfrac{7}{50}

\dfrac{1}{2}

Write

a = 2^j

and

b = 2^k,

so

\log_a b = \dfrac{k}{j}

For each

j,

count the multiples of

j

among

1, \ldots, 25

other than

j

itself, namely

\left\lfloor \tfrac{25}{j} \right\rfloor - 1

Let

a = 2^j

and

b = 2^k.

Then

\log_a b = \dfrac{k}{j},

which is an integer exactly when

k

is a multiple of

j.

For each

j,

the number of valid

k \ne j

in

\{1, \ldots, 25\}

is

\left\lfloor \tfrac{25}{j} \right\rfloor - 1.

Summing over

j

gives

\begin{aligned} &24 + 11 + 7 + 5 + 4 + 3 + 2 \\ &\quad {}+ 2 + 4 \cdot 1 = 62 \end{aligned}

ordered pairs

(a, b).

Since there are

25 \cdot 24 = 600

ordered pairs of distinct elements, the probability is

\dfrac{62}{600} = \dfrac{31}{300}.

Thus, the correct answer is B.

Problem 23 in other years