2009 AIME II Problem 11

Attempt Problem 11 of the 2009 AIME II 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 2009 AIME II solutions, or check the answer key.

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

11.

For certain pairs (m,n)(m, n) of positive integers with m≥nm \ge n there are exactly 5050 distinct positive integers kk such that ∣log⁡m−log⁡k∣<log⁡n.|\log m - \log k| \lt \log n. Find the sum of all possible values of the product mn.mn.

Answer: 125
Concepts:logarithmcounting integers in a rangecasework
Difficulty rating: 2990
Small Hint:

The inequality says exactly that mn<k<mn\frac{m}{n} \lt k \lt mn

Big Hint:

Write m=nq+rm = nq + r with 0≤r<n;0 \le r \lt n; the count of such kk is mn−q−1=50,mn - q - 1 = 50, so q(n2−1)+nr=51q(n^2 - 1) + nr = 51 leaves only a few cases

Solution:

The inequality ∣log⁡m−log⁡k∣<log⁡n|\log m - \log k| \lt \log n is equivalent to mn<k<mn.\frac{m}{n} \lt k \lt mn. Write m=nq+rm = nq + r with 0≤r<n;0 \le r \lt n; since m≥n≥2m \ge n \ge 2 (for n=1n = 1 no kk works), q≥1.q \ge 1. The integers kk in the interval are q+1,q + 1, q+2,q + 2, …,\ldots, mn−1,mn - 1, so there are mn−q−1=50mn - q - 1 = 50 of them, that is, mn−q=51,mn - q = 51, or q(n2−1)+nr=51.q(n^2 - 1) + nr = 51.

For n≥8n \ge 8 the left side is at least 63,63, so 2≤n≤7.2 \le n \le 7. Checking each case, only n=2,n = 2, r=0,r = 0, q=17q = 17 (so m=34m = 34) and n=3,n = 3, r=1,r = 1, q=6q = 6 (so m=19m = 19) work. These give mn=68mn = 68 and mn=57;mn = 57; indeed 17<k<6817 \lt k \lt 68 and 193<k<57\frac{19}{3} \lt k \lt 57 each contain exactly 5050 integers.

The sum of all possible values of mnmn is 68+57=125.68 + 57 = 125.

Problem 10#10
Full Exam

Problem 11 in Other Years