2010 AIME II Problems/Problem 3

Problem 3

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

Solution

In general, there are $20-n$ pairs of integers $(a, b)$ that differ by $n$ because we can make $b$ anyway from $n+1$ to $20$ and make $a$ $b-n$ .

Thus, the product is $(1^19)(2^18)\cdots(19^1)$ (some people may recognize it as $19!18!\cdots1!$ .)

When we count the number of factors of $2$ , we have 4 groups, factors that are divisible by $2$ at least once, twice, three times and four times.

Number that are divisible by $2$ at least once: $2, 4, \cdots, 18$

Exponent corresponding to each one of them $18, 16, \cdots 2$

Sum $=2+4+\cdots+18=\frac{(20)(9)}{2}=90$

Number that are divisible by $2$ at least twice: $4, 8, \cdots, 16$

Exponent corresponding to each one of them $16, 12, \cdots 4$

Sum $=4+8+\cdots+16=\frac{(20)(4)}{2}=40$

Number that are divisible by $2$ at least three times: $8,16$

Exponent corresponding to each one of them $12, 4$

Sum $=12+4=16$

Number that are divisible by $2$ at least four times: $16$

Exponent corresponding to each one of them $4$

Sum $=4$

summing all this we have $\boxed{150}$

2010 AIME II (Problems • Answer Key • Resources)
Preceded by Problem 2	Followed by Problem 4
1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15
All AIME Problems and Solutions

Page

Toolbox

Search

2010 AIME II Problems/Problem 3

Problem 3

Solution

See also