Question

Sea $m$ el número de subconjuntos de cinco elementos que se pueden elegir del conjunto de los primeros $14$ números naturales de modo que al menos dos de los cinco números sean consecutivos. Halla el residuo cuando $m$ se divide entre $1000.$

Let $m$ be the number of five-element subsets that can be chosen from the set of the first $14$ natural numbers so that at least two of the five numbers are consecutive. Find the remainder when $m$ is divided by $1000.$

Respuesta

Solución:

Cuenta el complemento: subconjuntos $a_1 \lt a_2 \lt a_3 \lt a_4 \lt a_5$ sin dos consecutivos. Al poner $b_i = a_i - (i - 1)$ cada subconjunto de este tipo se convierte en cinco números distintos $b_1 \lt b_2 \lt \cdots \lt b_5$ en $\{1, \ldots, 10\},$ y este mapeo es reversible, así que hay $\binom{10}{5} = 252$ subconjuntos sin dos números consecutivos.

Por lo tanto $m = \binom{14}{5} - \binom{10}{5}$ $= 2002 - 252 = 1750,$ y el residuo al dividir entre $1000$ es $750.$

Count the complement: subsets $a_1 \lt a_2 \lt a_3 \lt a_4 \lt a_5$ with no two consecutive. Setting $b_i = a_i - (i - 1)$ turns each such subset into five distinct numbers $b_1 \lt b_2 \lt \cdots \lt b_5$ in $\{1, \ldots, 10\},$ and this map is reversible, so there are $\binom{10}{5} = 252$ subsets with no two consecutive numbers.

Therefore $m = \binom{14}{5} - \binom{10}{5}$ $= 2002 - 252 = 1750,$ and the remainder upon division by $1000$ is $750.$

2009 AIME II Problema 6

Solución:

El Problema 6 en otros años