2010 AIME II Problem 3

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

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

3.

Let KK be the product of all factors (ba)(b - a) (not necessarily distinct) where aa and bb are integers satisfying 1a<b20.1 \le a \lt b \le 20. Find the greatest positive integer nn such that 2n2^n divides K.K.

Answer: 150
Concepts:prime factorizationcounting pairs
Difficulty rating: 2230
Solution:

For each value v=ba,v = b - a, the pairs (a,b)=(1,v+1),(a, b) = (1, v+1), (2,v+2),(2, v+2), ,\ldots, (20v,20)(20-v, 20) show that vv occurs exactly 20v20 - v times, so K=v=119v20v.K = \prod_{v=1}^{19} v^{20-v}. The exponent of 22 in KK is therefore v(20v)e(v),\sum_v (20 - v)\,e(v), where e(v)e(v) is the exponent of 22 in v.v.

Only even vv contribute: v=2,6,10,14,18v = 2, 6, 10, 14, 18 give e=1;e = 1; v=4,12v = 4, 12 give e=2;e = 2; v=8v = 8 gives e=3;e = 3; and v=16v = 16 gives e=4.e = 4. The total is 18+162+14+123+10+82+6+44+2=150, \begin{aligned} &18 + 16 \cdot 2 + 14 + 12 \cdot 3 \\ &\quad {}+ 10 + 8 \cdot 2 + 6 + 4 \cdot 4 + 2 \\ &= 150, \end{aligned} so n=150.n = 150.

← Problem 2#2
Full Exam

Problem 3 in Other Years