Un problema de lógica acerca de la teoría de conjuntos

Question

En un grupo de n personas, los subgrupos con intereses comunes se forman (fútbol,tenis,mesas de billar). El número de subgrupos es igual a $2^{n-1}$. 3 subgrupos tienen en común un miembro. Demostrar que hay una persona que es miembro de todos los subgrupos.

la prueba por contradicción parece un buen ajuste aquí, pero me parece que no puede conseguir los detalles a la derecha.

Answer 1

Denota el conjunto por $S,$ y deje $X$ ser la colección de subconjuntos de a $S$ como se da en el problema. Primera nota de que $A\in X$ fib $A^{C}\notin X$ ya tenemos exactamente $1/2$ del número total de subconjuntos. De esto podemos deducir que si $A, B\in X,$ $A\cap B \in X,$ desde $(A\cap B)^{C} \cap A\cap B = \emptyset.$ Ahora, si $\{x\} \in X$ para algunos singleton, entonces estamos de inmediato hacer, así que supongo que esto no es cierto. A continuación, cada conjunto de la forma $S-\{x\}$ $X.$ Tomando la intersección de dos de estos le da un conjunto de la forma $S-\{x, y\},$ y claramente obtener todos estos conjuntos. Continuar de esta forma da que cada conjunto es de $X,$ una contradicción, así que hemos terminado.

Alternativamente, usted puede hacer esto mediante la inducción en la intersección de las $k$ conjuntos, con el caso base se $k=2$ demostrado anteriormente.

Answer 2

Dado un conjunto finito $N$ del tamaño de la $n$, vamos a $O_n$ ser una familia de subconjuntos de a $N$ de manera tal que ninguno de los tres elementos de la $O_n$ no tienen intersección vacía. Dado que el $|O_n| = 2^{n-1}$ desea mostrar que $\exists x \in N \forall o \in O_n : x \in o$.

Cuando se forme una $O_n$, el máximo número de subconjuntos de a $N$ que puede ser elegido de un tamaño específico $k$ es exactamente el número de opciones de las $N$ donde un elemento es fijo; esto es exactamente $\binom{n-1}{k-1}$. La fijación de una opción garantiza que todos los subconjuntos de tamaño $k$ obedecen a la exigencia en cualquiera de los tres subconjuntos de compartir un elemento.

Aviso que enumerar el máximo de opciones para cada una de las $k \le n$ forma una fila en el Triángulo de Pascal, y la suma de todos el máximo de la cuenta para cada una de las $k$ es igual a $2^{n-1}$. Por lo tanto, con el fin de formar una $O_n$ cuya cardinalidad es exactamente $2^{n-1}$, el número máximo de cada tamaño de $k$ subconjunto debe ser elegido. Esto incluye un singleton subconjunto (si no los únicos son los elegidos, luego de un juego debe ser elegido para alcanzar el tamaño adecuado, pero una opción más de cualquier otro tamaño subconjunto violaría el máximo para ese tamaño). Así, con el fin de $O_n$ para satisfacer el requisito de que ninguno de los tres subconjuntos de compartir un elemento, la fijación de elección en cada tamaño de $k$ subconjunto debe ser el elemento de $N$ en el singleton.

Por lo tanto, el singleton de elección es la $x$ que satisface $\exists x \in N \forall o \in O_n : x \in o$