Question

Halle el número de subconjuntos de $\{1, 2, 3, 4, 5, 6, 7, 8\}$ que no son subconjuntos ni de $\{1, 2, 3, 4, 5\}$ ni de $\{4, 5, 6, 7, 8\}.$

Find the number of subsets of $\{1, 2, 3, 4, 5, 6, 7, 8\}$ that are subsets of neither $\{1, 2, 3, 4, 5\}$ nor $\{4, 5, 6, 7, 8\}.$

Respuesta

Respuesta: 196

Conceptos:subconjuntos inclusión-exclusión

Nivel de dificultad: 1890

Pista pequeña:

Cuente el complemento: los subconjuntos que están completamente dentro de $\{1,2,3,4,5\}$ o completamente dentro de $\{4,5,6,7,8\}$

Count the complement: subsets that lie entirely inside $\{1,2,3,4,5\}$ or entirely inside $\{4,5,6,7,8\}$

Pista grande:

Por inclusión-exclusión, la superposición consiste en los subconjuntos de $\{4, 5\},$ así que reste $2^5 + 2^5 - 2^2$ de $2^8$

By inclusion-exclusion, the overlap consists of the subsets of $\{4, 5\},$ so subtract $2^5 + 2^5 - 2^2$ from $2^8$

Solución:

En total hay $2^8 = 256$ subconjuntos. Los que hay que excluir son los contenidos en $\{1,2,3,4,5\}$ (hay $2^5 = 32$ ) o contenidos en $\{4,5,6,7,8\}$ (otros $32$ ). Un subconjunto de ambos es exactamente un subconjunto de la intersección $\{4, 5\},$ y hay $2^2 = 4$ de esos.

Por inclusión-exclusión, $32 + 32 - 4 = 60$ subconjuntos fallan, así que $256 - 60 = 196$ subconjuntos tienen la propiedad requerida.

There are $2^8 = 256$ subsets in all. The ones to exclude are those contained in $\{1,2,3,4,5\}$ (there are $2^5 = 32$ ) or contained in $\{4,5,6,7,8\}$ (another $32$ ). A subset of both is exactly a subset of the intersection $\{4, 5\},$ and there are $2^2 = 4$ of those.

By inclusion-exclusion, $32 + 32 - 4 = 60$ subsets fail, so $256 - 60 = 196$ subsets have the required property.

2017 AIME II Problema 1

Respuesta: 196

Nivel de dificultad: 1890

Pista pequeña:

Pista grande:

Solución:

El Problema 1 en otros años