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

Respuesta: 750

Conceptos:conteo complementario biyección subconjuntos

Nivel de dificultad: 2300

Pista pequeña:

Cuenta el complemento: los subconjuntos de cinco elementos sin dos números consecutivos

Count the complement: five-element subsets with no two consecutive numbers

Pista grande:

Restar $0,$ $1,$ $2,$ $3,$ $4$ a los cinco números en orden creciente hace corresponder los subconjuntos sin dos consecutivos de $\{1, \ldots, 14\}$ con subconjuntos arbitrarios de $\{1, \ldots, 10\}$

Subtracting $0,$ $1,$ $2,$ $3,$ $4$ from the five numbers in increasing order matches no-two-consecutive subsets of $\{1, \ldots, 14\}$ with arbitrary subsets of $\{1, \ldots, 10\}$

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 esta correspondencia 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

Respuesta: 750

Nivel de dificultad: 2300

Pista pequeña:

Pista grande:

Solución:

El Problema 6 en otros años