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

Pista pequeña:

Si $|\mathcal{A}| = k,$ entonces $|\mathcal{B}| = 12 - k,$ y las condiciones obligan a $k \in \mathcal{B}$ y $12 - k \in \mathcal{A}.$

If $|\mathcal{A}| = k,$ then $|\mathcal{B}| = 12 - k,$ and the conditions force $k \in \mathcal{B}$ and $12 - k \in \mathcal{A}$

Pista grande:

Para cada $k \ne 6,$ elige los $k - 1$ elementos restantes de $\mathcal{A}$ entre los $10$ números sin asignar. El caso $k = 6$ falla porque $6$ tendría que estar en ambos conjuntos.

For each $k \ne 6,$ choose the remaining $k - 1$ elements of $\mathcal{A}$ from the $10$ unassigned numbers. The case $k = 6$ fails because $6$ would have to lie in both sets.

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

Pista pequeña:

Pista grande:

Solución:

El Problema 8 en otros años