AMC 10 · 2017 · #20

Grade 11 probability
Archetype Geometric Probability by Area └ Sub-archetype Uniform Draws to Favorable Region
floor-functionlogarithm-propertiesgeometric-probabilitygeometric-series-infinite identify-subproblemspattern-recognition ↑ Prerequisites: floor-functiongeometric-series-infinite
📏 Medium solution 💡 3 insights
Problem
Two numbers x and y are picked independently at random from the open interval between 0 and 1, with every point equally likely. For each number, take its logarithm base 2 and round down to the nearest integer. Find the probability that the two rounded-down values come out equal.

Pick an answer.

(A)
$\frac{1}{8}$
(B)
$\frac{1}{6}$
(C)
$\frac{1}{4}$
(D)
$\frac{1}{3}$
(E)
$\frac{1}{2}$
How to solve
Strategy Identify Subproblems

The rounded-down base-2 logarithm is not really a logarithm question. It is a labelling question: it tells you which halving band of (0,1) a number sits in, the bands being [1/2,1), [1/4,1/2), [1/8,1/4), and so on. So 'the two labels agree' means 'both numbers landed in the same band'. That splits one probability question into one small question per band, each easy because a uniform pick lands in a piece with probability equal to its length and the two picks are independent. There are infinitely many bands, but their probabilities shrink by a fixed factor, so the pieces recombine as a geometric series.

1STEP 1

Turn the floor into an interval

Each floor value names one interval.

⌊ log₂ x ⌋ = -k ⇔ -k ≤ log₂ x ＜ -k+1 ⇔ 1/2^k ≤ x ＜ 1/(2^k-1)
2STEP 2

A band's probability is its length

An interval's probability is its length.

P(⌊ log₂ x ⌋ = -k) = 1/(2^k-1) - 1/2^k = 1/2^k, Σ_k=1^∞ 1/2^k = 1
3STEP 3

Both numbers in the same band

Both landing in one interval is the length squared.

P(⌊ log₂ x ⌋ = ⌊ log₂ y ⌋ = -k) = (1/2^k)² = 1/4^k
4STEP 4

Add the non-overlapping band cases

The intervals do not overlap, so they simply add.

P = Σ_k=1^∞ 1/4^k = 1/4 + 1/16 + 1/64 + …
5STEP 5

Sum the infinite geometric series

The infinite geometric sum is one third.

Σ_k=1^∞ 1/4^k = a/(1-r) = 1/4/(1-1/4) = 1/3
Answer
1/3
The four choices can be squeezed out without trusting the series. The single biggest case, both numbers in [1/2,1), already contributes 1/4, and later bands add more, so the answer is strictly larger than 1/4, ruling out 1/8, 1/6, and 1/4. On the other side, matching labels forces x and y into the same half of (0,1), and the chance of that is 1/4 + 1/4 = 1/2; but landing in the same lower half is not yet a match, so the answer is strictly less than 1/2. That leaves 1/3 as the only survivor, matching the computed value. A simulation of two million random pairs gives about 0.3331, right on 1/3.
💡Key takeaway

Rounding down a base-2 logarithm just labels which halving band a number fell into, so 'same label' is a staircase of squares with areas 1/4, 1/16, 1/64, … that add up to 1/3.

  • Turn the floor into an interval
  • A band's probability is its length
  • Both numbers in the same band
  • Add the non-overlapping band cases
  • Sum the infinite geometric series

More like this

Same archetype — closest grade level first.