Question

Sea $S$ el conjunto $\{1, 2, 3, \ldots, 10\}.$ Sea $n$ el número de conjuntos formados por dos subconjuntos disjuntos no vacíos de $S.$ (Dos conjuntos son disjuntos si no tienen elementos en común.) Halla el residuo obtenido cuando $n$ se divide entre $1000.$

Let $S$ be the set $\{1, 2, 3, \ldots, 10\}.$ Let $n$ be the number of sets of two non-empty disjoint subsets of $S.$ (Disjoint sets are defined as sets that have no common elements.) Find the remainder obtained when $n$ is divided by $1000.$

Respuesta

Respuesta: 501

Conceptos:subconjuntos principio de multiplicación inclusión-exclusión

Nivel de dificultad: 2500

Pista pequeña:

Construye un par ordenado $(A, B)$ de subconjuntos disjuntos enviando cada uno de los $10$ elementos a $A,$ a $B,$ o a ninguno

Build an ordered pair $(A, B)$ of disjoint subsets by sending each of the $10$ elements to $A,$ to $B,$ or to neither

Pista grande:

Resta mediante inclusión-exclusión los pares en los que $A$ o $B$ está vacío; luego divide entre $2$ para obtener pares no ordenados

Subtract the pairs where $A$ or $B$ is empty by inclusion-exclusion, then divide by $2$ to make the pairs unordered

Solución:

Primero cuenta los pares ordenados $(A, B)$ de subconjuntos disjuntos: cada uno de los $10$ elementos va en $A,$ en $B,$ o en ninguno, para $3^{10}$ pares. Entre estos, $2^{10}$ tienen $A$ vacío y $2^{10}$ tienen $B$ vacío, con el par $(\varnothing, \varnothing)$ contado en ambos, así que $3^{10} - 2 \cdot 2^{10} + 1 = 57002$ pares ordenados tienen ambos subconjuntos no vacíos.

Los subconjuntos disjuntos no vacíos nunca son iguales, así que cada conjunto $\{A, B\}$ se cuenta dos veces, dando $n = \frac{57002}{2} = 28501.$ El residuo módulo $1000$ es $501.$

Count ordered pairs $(A, B)$ of disjoint subsets first: each of the $10$ elements goes in $A,$ in $B,$ or in neither, for $3^{10}$ pairs. Among these, $2^{10}$ have $A$ empty and $2^{10}$ have $B$ empty, with the pair $(\varnothing, \varnothing)$ counted in both, so $3^{10} - 2 \cdot 2^{10} + 1 = 57002$ ordered pairs have both subsets non-empty.

Disjoint non-empty subsets are never equal, so each set $\{A, B\}$ is counted twice, giving $n = \frac{57002}{2} = 28501.$ The remainder mod $1000$ is $501.$

2002 AIME II Problema 9

Respuesta: 501

Nivel de dificultad: 2500

Pista pequeña:

Pista grande:

Solución:

El Problema 9 en otros años