PUERTA | Puerta TI 2005 | Pregunta 33

Sea A un conjunto de n elementos. Sea C una colección de subconjuntos distintos de A tal que para cualesquiera dos subconjuntos S ₁ y S ₂ en C, S ₁ ⊂ S ₂ o S ₂ ⊂ S ₁ . ¿Cuál es la cardinalidad máxima de C?

 
(A) n
(B) n + 1
(C) 2 ^(n-1) + 1
(D) n!

Respuesta: (B)
Explicación: Sea n=2 A = {1, 2}
Todos los subconjuntos formados por A son: – {}, {1}, {2}, {1,2}.
C es una colección de subconjuntos distintos tales que para cualquier S1, S2 o S1⊂S2 o S2⊂S1.
Entonces, para C, {} conjunto nulo se puede incluir siempre ya que es nulo. conjunto es un subconjunto de todo conjunto.
Podemos elegir uno de {1} o {2}, se puede incluir {1,2} para maximizar la cardinalidad.
Entonces, aquí 1) Si se elige {1}, entonces C = {}, {1}, {1,2} aquí cada conjunto es un subconjunto de otro.
2) Si se elige {2} entonces C = {}, {2}, {1,2} aquí también cada conjunto es subconjunto de otro.

Entonces, la respuesta debería ser 2 pero también incluye un conjunto vacío, por lo tanto, la cardinalidad máxima de C es 3.

Esta solución es aportada por Anil Saikrishna Devarasetty .

Enfoque alternativo:
la descripción del conjunto C en la pregunta en realidad significa que C es un conjunto total ordenado, por lo que cada subconjunto de A en C debe tener un tamaño diferente, ya que |A| = n, junto con el conjunto vacío, hay n + 1 conjuntos posibles en C, por lo que la máxima cardinalidad de C es n + 1.

Esta solución es aportada por Zhang Xichu .

Cuestionario de esta pregunta