Question

Para enteros no negativos $a$ y $b$ con $a + b \le 6,$ sea $T(a, b) = \binom{6}{a}\binom{6}{b}\binom{6}{a+b}.$ Sea $S$ la suma de todos los $T(a, b),$ donde $a$ y $b$ son enteros no negativos con $a + b \le 6.$ Halla el residuo cuando $S$ se divide entre $1000.$

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.$

Respuesta

Solución:

Por la simetría $\binom{6}{a+b} = \binom{6}{6-(a+b)},$ sustituir $c = 6 - a - b$ convierte la suma en $S = \sum_{a+b+c=6} \binom{6}{a}\binom{6}{b}\binom{6}{c}.$

Cada término cuenta las formas de elegir $a$ elementos de un conjunto de $6$ elementos, $b$ de un segundo, y $c$ de un tercero. Sumado sobre todos los $a + b + c = 6,$ esto cuenta cada forma de elegir $6$ elementos del conjunto combinado de $18$ elementos, así que $S = \binom{18}{6} = 18564.$

El residuo al dividir entre $1000$ es $564.$

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 Problema 7

Solución:

El Problema 7 en otros años