Question

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

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

Respuesta

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

Solución:

El Problema 9 en otros años