2010 AIME II Problem 3

Below is the professionally curated solution for Problem 3 of the 2010 AIME II, 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 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:prime factorizationcounting pairs

Difficulty rating: 2230

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.

Solution:

For each value v=ba,v = b - a, the pairs (a,b)=(1,v+1),(2,v+2),,(20v,20)(a, b) = (1, v+1), (2, v+2), \ldots, (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,18 + 16 \cdot 2 + 14 + 12 \cdot 3 + 10 + 8 \cdot 2 + 6 + 4 \cdot 4 + 2 = 150, so n=150.n = 150.

← Problem 2Full ExamProblem 4

Problem 3 in Other Years