2004 AIME I Problem 12

Attempt Problem 12 of the 2004 AIME I below, then check your answer against the professionally curated solution from LIVE by Po-Shen Loh. You can also try the full timed exam, view all 2004 AIME I solutions, or check the answer key.

All problems are used with official legal permission of the Mathematical Association of America (MAA).

12.

Let S\mathcal{S} be the set of ordered pairs (x,y)(x, y) such that 0<x≤1,0 \lt x \le 1, 0<y≤1,0 \lt y \le 1, and ⌊log⁡2(1x)⌋\left\lfloor \log_2\left(\frac{1}{x}\right) \right\rfloor and ⌊log⁡5(1y)⌋\left\lfloor \log_5\left(\frac{1}{y}\right) \right\rfloor are both even. Given that the area of the graph of S\mathcal{S} is mn,\frac{m}{n}, where mm and nn are relatively prime positive integers, find m+n.m + n. The notation ⌊z⌋\lfloor z \rfloor denotes the greatest integer that is less than or equal to z.z.

Answer: 14
Concepts:floor and ceiling functionslogarithmgeometric sequence
Difficulty rating: 2840
Small Hint:

⌊log⁡2(1x)⌋=2k\lfloor \log_2(\frac{1}{x}) \rfloor = 2k exactly when 2−2k−1<x≤2−2k2^{-2k-1} \lt x \le 2^{-2k}

Big Hint:

The region is a product of a set of xx-intervals and a set of yy-intervals; sum each set of lengths as a geometric series and multiply

Solution:

For 0<x≤1,0 \lt x \le 1, the condition ⌊log⁡2(1x)⌋=2k\lfloor \log_2(\frac{1}{x}) \rfloor = 2k (for an integer k≥0k \ge 0) means 2k≤log⁡2(1x)<2k+1,2k \le \log_2(\frac{1}{x}) \lt 2k + 1, i.e. x∈(2−2k−1,2−2k].x \in \left(2^{-2k-1}, 2^{-2k}\right]. These intervals have total length ∑k≥02−2k−1=121−14=23.\sum_{k \ge 0} 2^{-2k-1} = \frac{\frac{1}{2}}{1 - \frac{1}{4}} = \frac{2}{3}. Similarly, ⌊log⁡5(1y)⌋\lfloor \log_5(\frac{1}{y}) \rfloor is even for y∈(5−2k−1,5−2k],y \in \left(5^{-2k-1}, 5^{-2k}\right], intervals of total length ∑k≥045⋅25−k=451−125=56.\sum_{k \ge 0} \frac{4}{5} \cdot 25^{-k} = \frac{\frac{4}{5}}{1 - \frac{1}{25}} = \frac{5}{6}.

The graph of S\mathcal{S} is the product of these two sets, so its area is 23⋅56=59,\frac{2}{3} \cdot \frac{5}{6} = \frac{5}{9}, and m+n=5+9=14.m + n = 5 + 9 = 14.

Problem 11#11
Full Exam

Problem 12 in Other Years