Question

Halla el número de familias de $16$ subconjuntos distintos de $\{1, 2, 3, 4, 5\}$ con la propiedad de que, para cualesquiera dos subconjuntos $X$ y $Y$ de la familia, $X \cap Y \neq \emptyset.$

Find the number of collections of $16$ distinct subsets of $\{1, 2, 3, 4, 5\}$ with the property that for any two subsets $X$ and $Y$ in the collection, $X \cap Y \neq \emptyset.$

Respuesta

Solución:

Los $32$ subconjuntos se dividen en $16$ pares complementarios $\{X, X^{\mathsf{c}}\},$ y ninguna familia puede contener ambos miembros de un par (son disjuntos). Por tanto, una familia de $16$ subconjuntos que se cortan dos a dos debe contener exactamente un miembro de cada par; en particular contiene $\{1,2,3,4,5\}$ y no $\emptyset.$

Si se elige algún conjunto unitario $\{x\},$ todo miembro debe cortar a $\{x\},$ es decir, contener $x.$ Exactamente un conjunto de cada par complementario contiene $x,$ así que la familia debe ser exactamente los $16$ subconjuntos que contienen $x:$ esto da $5$ familias. En caso contrario no se elige ningún conjunto unitario, así que los cinco conjuntos de $4$ elementos están en la familia. Dos subconjuntos cualesquiera de $3$ elementos de un conjunto de $5$ elementos se cortan, un conjunto de $4$ elementos es disjunto solo de su complemento, y un conjunto elegido de $2$ elementos y un conjunto elegido de $3$ elementos son disjuntos solo si son complementarios, lo cual no puede darse con ambos elegidos. Así que la única condición que queda es que los conjuntos elegidos de $2$ elementos se corten dos a dos.

Viendo los conjuntos de $2$ elementos como aristas de $K_5,$ una familia de aristas que se cortan dos a dos, o bien tiene todas las aristas pasando por un vértice común, o bien es un triángulo. El número de tales familias de aristas es: la familia vacía ( $1$ ), los triángulos ( $\binom{5}{3} = 10$ ), y las familias no vacías dentro de una estrella, $5(2^4 - 1) - 10 = 65$ (restando las $10$ aristas simples contadas en sus dos extremos). Eso da $1 + 10 + 65 = 76$ familias, para un total de $5 + 76 = 81.$

The $32$ subsets split into $16$ complementary pairs $\{X, X^{\mathsf{c}}\},$ and no collection can contain both members of a pair (they are disjoint). A collection of $16$ pairwise-intersecting subsets must therefore contain exactly one member of every pair; in particular it contains $\{1,2,3,4,5\}$ and not $\emptyset.$

If some singleton $\{x\}$ is chosen, every member must meet $\{x\},$ i.e. contain $x.$ Exactly one set in each complementary pair contains $x,$ so the collection must be exactly the $16$ subsets containing $x:$ this gives $5$ collections. Otherwise no singleton is chosen, so all five $4$ -element sets are in the collection. Any two $3$ -element subsets of a $5$ -element set intersect, a $4$ -element set is disjoint only from its complement, and a chosen $2$ -element set and a chosen $3$ -element set are disjoint only if they are complements, which cannot both be chosen. So the only remaining condition is that the chosen $2$ -element sets pairwise intersect.

Viewing $2$ -element sets as edges of $K_5,$ a pairwise-intersecting collection of edges either has all edges through one common vertex or is a triangle. The number of such edge families is: the empty family ( $1$ ), triangles ( $\binom{5}{3} = 10$ ), and nonempty families within a star, $5(2^4 - 1) - 10 = 65$ (subtracting the $10$ single edges counted at both endpoints). That is $1 + 10 + 65 = 76$ collections, for a total of $5 + 76 = 81.$

2023 AIME II Problema 11

Solución:

El Problema 11 en otros años