Definimos un $k$-clan como un conjunto de $k$ personas tales que cuaesquiera dos personas se conocen entre s\'i. En una fiesta se cumple que cualesquiera dos $3$-clanes tienen al menos una persona en com\'un y no hay 5-clanes. Demuestra que se pueden escoger dos personas, de manera que si se saca a estas dos personas de la fiesta ya no quedan 3-clanes.
viernes, 28 de agosto de 2015
Suscribirse a:
Comentarios de la entrada (Atom)
4 comentarios:
Recuerdo que ya habia hecho este problema antes, solo era ver muchos casitos de como pueden estar organizados las personas, viendolo como una grafica, creo que me daria flojerla explicar todo eso jaja, tal vez luego lo comente}
Ya lo había visto
Supongamos primero que hay un 4-clan formado por $A$, $B$, $C$ y $D$. Si los únicos 3-clanes son los contenidos en este 4-clan, ya acabamos. De lo contrario hay algún 3-clan que contiene a lo más a dos de las personas de este 4-clan, pero claramente no puede contener a exactamente una (pues contradiría la condición de que dos 3-clanes tienen a alguien en común). Sin pérdida de generalidad este 3-clan está formado por $A$. $B$ y $E$. Si quitar $A$ y $B$ no basta, entonces hay un 3-clan que no contiene ni a $A$ ni a $B$, entonces debe contener a $C$ y a $D$. Sea $F$ el otro miembro de este clan, entonces los 3-clanes $A, B, E$ y $C, D, F$ no tienen miembros en común, contradicción.
Ahora supongamos que no hay 4-clanes y sea $A, B, C$ un 3-clan. Si quitar a $A$ y $B$ no basta, entonces hay un 3-clan que no contiene a $A$ ni a $B$, y entonces debe contener a $C$. Sea $C, D, E$ este clan. Ahora, si quitar a $C$ y $A$ no basta, entonces hay un 3-clan que no contiene a $A$ ni $C$. Por el 3-clan $A, B, C$, debe contener a $B$, y por el 3-clan $C, D, E$ debe contener a $D$ o a $E$. Esto impica que $B$ conoce a $D$ o $E$. Si $B$ conociera a $D$ y a $E$, entonces $B, C, D, E$ formarían un 3-clan, imposible, Entonces $B$ solo conoce a 1, digamos que conoce a $E$. Análogamente $A$ conoce a alguno, y no puede ser $E$ pues entonces $A, C, E, B$ sería un 3-clan, entonces conoce a $D$.
Ahora, si quitar $A$ y $C$ no basta, entonces hay un 3-clan que no los contiene. Por el 3-clan $A, B, C$ debe contener a $B$, y por el 3-clan $A, C, D$ debe contener a $D$. Entonces $B$ y $D$ se conocen, contradicción.
Yo no estoy seguro si ya lo había visto... pero igual mi solución:
Nota, los números representan vertices de la gráfica que se construye con las condiciones del problema. Las personas son vertices y la amistad es una arista entre ellos. Como siempre en matemáticas, amistad es mutua (pero no siempre en la vida real).
Caso 1: Supongamos que ha un $k_4$ los con los vertices $1,2,3,4.$ Veamos que es necesario quitar dos vértices de ese $k_4$ si se quitara solo 1, queda un $K_3$ en la sub-gráfica; pero también es suficiente para que no haya $K_3$.
De manera similar, todo $K_3$ en la gráfica no contenido en $(1, 2, 3, 4)$ tiene que interceptar a $(1, 2, 3, 4)$ es dos vertices para interceptar a los cuatro $K_3$ que están contenidos.
Por lo tanto, si hay un $K_3$ que no está contenido en $(1, 2, 3, 4)$ es S.P.G. $(3, 4, 5)$ luego se puede perforar todo $K_3$ con los vértices 3 y 4. Suponiendo que hubiera una $K_3$ que no tiene ninguno de los vertices ${3, 4}$ entonces tendría el vértice 5 -por tener intersección no vacía con $(3, 4, 5)$- y también tendría ambos vertices 1 y 2, como ya se había mostrado arriba. Luego $(1, 2, 3, 4, 5)$ es un $K_5$ en la gráfica, cosa que no es posible por hipótesis.
Caso 2: No hay ningún $K_4$ pero hay un $K_4/e$ es decir un $K_4$ sin una arista. SPG están las aristas $(1,2), (1,3) (1,4) (2,3) (2,4)$ pero no la $(3, 4)$. Luego si hubiera un $K_3$ que no tiene ninguno de {3, 4} entonces tendría a los vertices 1 y 3, para tener intersección no vacía con $(1, 2, 3)$ y $(1, 2, 4)$ pero entonces estaríamos en el caso 1.
Caso 3: no hay dos $K_3$ que compartan dos vertices.
si hay solamente un $K_3$ es claro. S.P.G. están $(1, 2, 3)$ y $(1, 4, 5)$ luego si hubiera un $K_3$ que no contiene a 1, entonces estarían alguno de {2,3} y alguno de {4,5} en ese $K_3$, en cualquier caso se completa un $K_4/e$ y estaríamos en el caso 2.
Publicar un comentario