AMC 10 · 2005 · #23

Grade 11 probability

Archetype Small-Domain Constrained Search └ Sub-archetype Factor / Divisibility Constraint

logarithm-propertiesexponentsprobability-basicfloor-function convert-to-algebrasystematic-enumeration ↑ Prerequisites: logarithm-propertiesexponentsprobability-basic

📏 Long solution 💡 3 insights

Problem

Two different numbers are picked at random from the first twenty-five powers of two. Find the probability that the logarithm of one to the base of the other is a whole number.

Pick an answer.

(A)

$\frac{2}{25}$

(B)

$\frac{31}{300}$

(C)

$\frac{13}{100}$

(D)

$\frac{7}{50}$

(E)

$\frac{1}{2}$

How to solve

Strategy Introduce a Variable

Every number in the pool is a power of 2, so naming the exponents replaces 25 enormous numbers with the plain list 1 through 25. A logarithm between two powers of the same base is just a ratio of exponents, so the whole probability question turns into a divisibility count on small numbers, which a systematic table handles. A second organisation of the same count then checks the total.

1STEP 1

Name the exponents

Every number is a power, so the problem is really about exponents.

a = 2^x, b = 2^y, x, y ∈ {1, 2, …, 25}, x ≠ y

2STEP 2

Turn the logarithm into an equation

The logarithm becomes an equation between those exponents.

(2^x)^z = 2^y ⟹ 2^xz = 2^y ⟹ xz = y

3STEP 3

Read it as divisibility

That reads as plain divisibility among small whole numbers.

z = y/x is an integer ⇔ x ∣ y

4STEP 4

Count multiples for each x

For each base, counting its multiples and dropping itself gives a short table.

#{ y : x ∣ y, 1 ≤ y ≤ 25, y ≠ x } = ⌊ 25/x ⌋ - 1

5STEP 5

Add up the table

Adding the table gives 62 favourable ordered pairs.

Σ_x=1¹²(⌊ 25/x ⌋ - 1) = 24 + 11 + 7 + 5 + 4 + 3 + 2 + 2 + 1 + 1 + 1 + 1 = 62

6STEP 6

Count all the pairs

The ordered total is 600.

25 · 24 = 600

7STEP 7

Divide and reduce

Reducing gives 31/300, choice (B).

P = 62/600 = 31/300

Answer

31/300

Recount the favourable pairs from the other end. Instead of asking how many multiples each x has, ask how many divisors each y has. The number of ordered pairs (x, y) with x ∣ y and both between 1 and 25, allowing x = y, is Σ_y=1²⁵ d(y) where d(y) counts divisors: 1+2+2+3+2+4+2+4+3+4+2+6+2+4+4+5+2+6+2+6+4+4+2+8+3 = 87. Removing the 25 pairs with x = y leaves 87 - 25 = 62, matching the table exactly. The size is sensible too: 31/300 ≈ 0.103, roughly one pair in ten, which fits the fact that 24 of the 62 good pairs already come from a = 2 alone. Finally, the ordered reading is the right one, since a and b are named separately and log_a b is not the same as log_b a.

💡Key takeaway

When everything in sight is a power of the same number, stop looking at the numbers and look at their exponents.

Name the exponents
Turn the logarithm into an equation
Read it as divisibility
Count multiples for each x
Add up the table
Count all the pairs
Divide and reduce