Question

Sea $N$ el número de pares ordenados de conjuntos no vacíos $\mathcal{A}$ y $\mathcal{B}$ que tienen las siguientes propiedades: • $\mathcal{A} \cup \mathcal{B}$ $\small = \{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12\},$ • $\mathcal{A} \cap \mathcal{B} = \emptyset,$ • el número de elementos de $\mathcal{A}$ no es un elemento de $\mathcal{A},$ • el número de elementos de $\mathcal{B}$ no es un elemento de $\mathcal{B}.$ Halla $N.$

Let $N$ be the number of ordered pairs of nonempty sets $\mathcal{A}$ and $\mathcal{B}$ that have the following properties: • $\mathcal{A} \cup \mathcal{B}$ $\small = \{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12\},$ • $\mathcal{A} \cap \mathcal{B} = \emptyset,$ • the number of elements of $\mathcal{A}$ is not an element of $\mathcal{A},$ • the number of elements of $\mathcal{B}$ is not an element of $\mathcal{B}.$ Find $N.$

Respuesta

Respuesta: 772

Conceptos:subconjuntos combinaciones conteo complementario

Nivel de dificultad: 2520

Solución:

Sea $k = |\mathcal{A}|,$ así $|\mathcal{B}| = 12 - k$ con $1 \le k \le 11.$ Como cada elemento está en exactamente un conjunto, $k \notin \mathcal{A}$ significa $k \in \mathcal{B},$ y $12 - k \notin \mathcal{B}$ significa $12 - k \in \mathcal{A}.$ Si $k = 6,$ entonces $6$ tendría que pertenecer a ambos conjuntos, lo cual es imposible, así que $k \ne 6.$

Para cada otro $k,$ los elementos $k$ y $12 - k$ ya están colocados, y los $k - 1$ elementos restantes de $\mathcal{A}$ se pueden elegir entre los otros $10$ números de $\binom{10}{k-1}$ maneras, y $\mathcal{B}$ toma el resto. Por tanto $\begin{aligned} N &= \sum_{k=1}^{11} \binom{10}{k-1} - \binom{10}{5} \\ &= 2^{10} - 252 = 772. \end{aligned}$

Let $k = |\mathcal{A}|,$ so $|\mathcal{B}| = 12 - k$ with $1 \le k \le 11.$ Since every element lies in exactly one set, $k \notin \mathcal{A}$ means $k \in \mathcal{B},$ and $12 - k \notin \mathcal{B}$ means $12 - k \in \mathcal{A}.$ If $k = 6,$ then $6$ would have to belong to both sets, which is impossible, so $k \ne 6.$

For each other $k,$ the elements $k$ and $12 - k$ are already placed, and the remaining $k - 1$ elements of $\mathcal{A}$ can be chosen from the other $10$ numbers in $\binom{10}{k-1}$ ways, with $\mathcal{B}$ taking the rest. Hence $\begin{aligned} N &= \sum_{k=1}^{11} \binom{10}{k-1} - \binom{10}{5} \\ &= 2^{10} - 252 = 772. \end{aligned}$

2010 AIME II Problema 8

Respuesta: 772

Nivel de dificultad: 2520

Solución:

El Problema 8 en otros años