2017 AIME I Problems/Problem 7

Problem 7

For nonnegative integers $a$ and $b$ with $a + b \leq 6$ , let $T(a, b) = \binom{6}{a} \binom{6}{b} \binom{6}{a + b}$ . Let $S$ denote the sum of all $T(a, b)$ , where $a$ and $b$ are nonnegative integers with $a + b \leq 6$ . Find the remainder when $S$ is divided by $1000$ .

Solution

Let $c=6-(a+b)$ , and note that $\binom{6}{a + b}=\binom{6}{c}$ . The problem thus asks for the sum $\binom{6}{a} \binom{6}{b} \binom{6}{c}$ over all $a,b,c$ such that $a+b+c=6$ . Consider an array of 18 dots, with 3 columns of 6 dots each. The desired expression counts the total number of ways to select 6 dots by considering each column separately. However, this must be equal to $\binom{18}{6}=18564$ . Therefore, the answer is $\boxed{564}$ .

-rocketscience

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

Page

Toolbox

Search

2017 AIME I Problems/Problem 7

Problem 7

Solution

See Also