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 mnm \ge n there are exactly 5050 distinct positive integers kk such that logmlogk<logn.|\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
Solution:

The inequality logmlogk<logn|\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 0r<n;0 \le r \lt n; since mn2m \ge n \ge 2 (for n=1n = 1 no kk works), q1.q \ge 1. The integers kk in the interval are q+1,q+2,,mn1,q + 1, q + 2, \ldots, mn - 1, so there are mnq1=50mn - q - 1 = 50 of them, that is, mnq=51,mn - q = 51, or q(n21)+nr=51.q(n^2 - 1) + nr = 51.

For n8n \ge 8 the left side is at least 63,63, so 2n7.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