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