2009 AIME II Problem 11

Below is the professionally curated solution for Problem 11 of the 2009 AIME II, 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 of the real AMC 8, AMC 10, AMC 12, and AIME problems in our complete solution collection are used with official legal permission of the Mathematical Association of America (MAA).

Concepts:logarithmcounting integers in a rangecasework

Difficulty rating: 2990

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.

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 10Full ExamProblem 12

Problem 11 in Other Years