Question

For nonnegative integers $a$ and $b$ with $a + b \le 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 \le 6.$ Find the remainder when $S$ is divided by $1000.$

Answer

Answer: 564

Concepts:combinations double counting

Difficulty rating: 2650

Solution:

By the symmetry $\binom{6}{a+b} = \binom{6}{6-(a+b)},$ substituting $c = 6 - a - b$ turns the sum into $S = \sum_{a+b+c=6} \binom{6}{a}\binom{6}{b}\binom{6}{c}.$

Each term counts the ways to choose $a$ elements from one $6$ -element set, $b$ from a second, and $c$ from a third. Summed over all $a + b + c = 6,$ this counts every way to choose $6$ elements from the combined $18$ -element set, so $S = \binom{18}{6} = 18564.$

The remainder upon division by $1000$ is $564.$

2017 AIME I Problem 7

Answer: 564

Difficulty rating: 2650

Solution:

Problem 7 in Other Years