A una fiesta asisten ocho personas. Se cuenta con cuatro mesas para acomodar a los invitados; en cada mesa debe haber exactamente dos personas. Se sabe que para cada persona $P$ en la fiesta hay a lo más tres invitados que son enemigos de $P$ (ser enemigo es mutuo). Demuestra que es posible acomodar a las personas en las cuatro mesas de tal forma que no haya enemigos en la misma mesa.
viernes, 13 de mayo de 2011
Problema del día (Centros)
Ayer no se podía postear por alguna razón, pero hoy si les dejo un problema:
Suscribirse a:
Comentarios de la entrada (Atom)
14 comentarios:
Llamemos a una pareja de enemigos una pareja mala, a una pareja de amigos una buena, a un acomodo que cumpla las condiciones del problema uno bueno, y a un acomodo con al menos una pareja mala un acomodo malo. Transformamos el problema a gráficas, con los vértices representando personas y aristas que son enemigos (pareja mala). Hay a lo más 8*3/2 = 12 parejas malas. Si hay x parejas malas, con x < 12, agrego 12-x aristas tal que aún se satisfaga la condición del problema. (Es fácil ver que esto es posible. Lo explicaré más a detalle en el último párrafo).
Uso el principio de inclusión exclusión.
CASO I. 1 PAREJA.
Hay 12 aristas, y para cada una hay 6!/2!2!2!3! = 15 apareamientos (acomodos) incluyéndola. Así, en éste caso hay 180 acomodos.
CASO II: 2 PAREJAS.
Para cada par de parejas que no comparten vértices, hay 3 acomodos incluyéndolas (4!/2!2!2!). Pero para cada arista, hay al menos 7 aristas que no comparten vértices con ella (pues hay a lo más 3+3-1 = 5 aristas que sí lo hacen). Así, en éste caso hay 12*7*3/2 = 126 apareamientos (al menos).
CASO III: 3 y 4 PAREJAS.
Resulta más fácil juntar éstos casos y contar el número de acomodos con 3 parejas malas y una buena. Para casa pareja buena, si borras sus vértices, hay 6 aristas en la gráfica resultante (pues se borraron 3+3-0 aristas y había 12), por lo que hay 2 maneras a lo más de aparear los vértices tal que queden puras parejas malas. El caso da que hay a lo más 16*2 = 32 acomodos aquí (pues hay 16 parejas buenas).
Pero hay un total de 8!/2!2!2!4! = 105 acomodos posibles. Así, como hay a lo más 180-126+32=86 acomodos malos, y 86<105, habrá al menos uno bueno.
Si hay x parejas malas, con x < 12, puedo agregar 12-x aristas tal que aún se satisfaga la condición del problema. Si el nuevo acomodo cumple, claramente el viejo lo hará. Veré por qué puedo hacer esto. Hago “inducción”, pero para abajo. Si x=11, entonces me falta agregar una arista, que solamente es imposible cuando los grados de los vértices son 3, 3, 3, 3, 3, 3, 3, 1. Analizaremos este caso después. Ahora bien, si x<11, claramente le podemos agregar una arista, pues si no, los grados de los vértices serían 3, 3, 3, 3, 3, 3, 3, 1 y x=11, contradicción.
Hagamos las mismas cuentas pero con la gráfica 3, 3, 3, 3, 3, 3, 3, 1. En el caso 1 da 11*15=165. En el caso 2 da 11*6*3/2=99. El último caso si cambia algo. Si la arista que nos agarramos era la que salía del vértice de grado 1, habrá 8 aristas en la gráfica restante, y ahí podría haber 3 acomodos malos, más es fácil ver que no 4 (podemos darnos la libertad de que haya 7, incluso). Los demás casos son 2 acomodos malos a lo más. Así que el caso 3 da 1*3+16*2=35. Así que hay a lo más 165-99+35=101 acomodos malos, pero hay 105 acomodos, y así debe haber al menos uno bueno.
Q.E.D.
Tomemos $G$ la gráfica tal que sus vértices son las personas en la fiesta y una arista entre los vértices $A$ y $B$ simboliza que son amigos (definimos a los amigos como aquellos que no son enemigos). Queremos un emparejamiento perfecto para acabar el problema. Entonces, al principio $\deg(P)\geq 5$ para toda persona $P$ en $G$. Entonces, quitamos cualquier par de amigos, luego nos queda una gráfica $H$ con $6$ personas y $\deg(P)\geq 3$ para toda persona $P$ en $H$ (ya que quitamos dos personas de $G$). Ahora, si $H$ es bipartita, acabamos por el teorema del matrimonio ya que $\deg(P)\geq 3$. Si no, entonces existe un ciclo de longitud impar en $H$, que puede incluir $3$ ó $5$ vértices. Tomemos dicho ciclo. Si el ciclo es de longitud 5, tomemos el punto $X$ fuera del ciclo; como $\deg(X)\geq 3$, es claro por principio de las casillas que $X$ es amigo con al menos dos vértices consecutivos en el ciclo, por lo que existe un ciclo de longitud $3$. Ahora, tomemos el ciclo de longitud $3$. Sean $A,B,C$ los vértices fuera del ciclo. Entonces, si $A,B,C$ son enemigos dos a dos, como $\deg(P)\geq 3$ para cualquier $P$, todos los puntos del ciclo de longitud 3 son amigos con cada uno de $A,B,C$, y aquí es claro el emparejamiento perfecto. Si entre $A,B,C$ hay al menos un par de amigos, entonces quitamos ese par, y nos queda una gráfica $J$ con 4 vértices tales que $\deg(P)\geq 1$ para toda $P$ en $J$. Como no quitamos ninguna arista del ciclo de longitud 3, éste sobrevive en $J$, y como el punto $Y$ fuera del ciclo está conectado con al menos uno de los vértices del ciclo, es claro el emparejamiento.
Perdón pero no entendí como obtuviste $deg(P) \geq 5$ al principio
Hmm...cierto, no puedo suponer que $deg(P)\geq 5$...es $deg(P)\geq 4$. Creo que tendré que modificar mi solución o hacer una nueva...
Es conocido que como cada persona tiene a lo más $3$ enemigos, entonces podemos dividir a estas personas en $2$ grupos de modo que cada persona tenga a lo más un enemigo en el grupo.
Entonces tenemos opciones de grupos de tamaño $(4, 4)$, $(3, 5)$, $(2, 6)$.
Si es de $(4, 4)$ acabamos, las sentamos por parejas a las personas.
Si es de $(3, 5)$ entonces en el grupo de $3$, hay $2$ personas que no son enemigas, así que las sentamos juntas, y la otra persona tiene un no enemigo en el grupo de $5$, así que lo sentamos con ese. Y como en el grupo de $5$ personas quedan $4$, donde a lo más hay $2$ enemistades podemos sentarlas de la manera deseada.
Si es de $(2, 6)$ entonces los del grupo de $2$ tienen al menos $2$ enemistades en el grupo de $6$, así que para cada persona del grupo de $2$, la podemos juntar con una de las $6-4=2$ personas que forzosamente no son enemigas de ninguno de los $2$. Y quedan $4$ personas con a lo más $2$ enemistades, que si se pueden separar en $2$ grupos de $2$ personas y acabamos.
NOTA: Cuando quedan $2$ personas con a lo más $2$ enemistades, si se pueden separar, digamos que $A, B$ son enemigos y $C, D$ son enemigos. Entonces los sentamos de la siguiente manera: $(A, C)$ y $(B, D)$.
Perdón pero, ¿como sacaste lo que podías dividir en dos grupos? Qué interesante resultado.
Es un problema del engel, si mal no recuerdo, el 3er ejemplo del libro, y más general, no solo para $8$ personas, si no para $n$ personas.
Adán, creo que hay un problema con tu último caso. ¿Por qué dices que cada persona del grupo de 2 tiene al menos 2 enemigos en el otro grupo? Supongo que querías decir "a lo más". Pero aún así, esto no siempre es cierto. Puede ser que esas dos personas tengan tres enemigos en el otro grupo y que entre ellos no sean enemigos, por ejemplo.
Juan, no entiendo esa parte en la que dices que puedes agregar aristas hasta que la gráfica tenga 12 aristas exactamente. De hecho, esto no es cierto. Considera una gráfica con vértices $\{1,2,3,4,5,6,7,8\}$ y que tenga las siguientes aristas $\{12,23,34,45,56,61,14,25,36,78\}$. Esa gráfica tiene 10 aristas y no le puedes agragar más de tal forma que se siga cumpliendo $\delta (v)\leq3$.
Esperaré a que alguien acabe bien su solución para dar una distinta.
Pero si no puedes agregar más es porque todas las de grado $\le$ 2 están conectadas todas entre sí (si no agregas una allí), y porque son de grado $\le$ 2 entonces nada más hay una o dos o 0. El 0 lo analizé. El 1 también (el 3, 3, 3, 3, 3, 3, 3, 1). Falta el dos (3, 3, 3, 3, 3, 3, 1, 1) (3, 3, 3, 3, 3, 3, 2, 2). Lo que se me ocurré es ir quitándole vertices a las gráficas y luego reconstruirlas. Quedarán como 6 grafos (supongo) y esos casos los haces. O también puedes contar con PIE.
Pues mejor intenta hacer el problema suponiendo que la gráfica tiene 12 o menos aristas y no 12 exactamente.
Cierto, ya vi mi error, estaba suponiendo que necesariamente las $2$ personas del grupo de $2$ eran enemigas. Si no lo son, claramente las podemos sentar a ellas en una mesa. En el otro grupo de $6$ tenemos que también cada persona tiene a lo más $1$ enemigo en ese grupo de $6$, así que a esas personas siempre las podemos distribuir en las $3$ mesas restantes. Creo que ese era el caso que faltaba.
Me salió una solución pero es bastante talachuda, así que pondré los casos y los argumentos importantes (la talacha sale con argumentos simples de casillas)
Primero tomamos la gráfica $G$ con $8$ personas en la que las aristas simbolizan amistad y los vértices personas. Entonces $\deg(P)\geq 4$ para toda persona $P$. Si encontramos algún grupo de $4$ personas tal que entre ellas no hay amistades, podemos construir claramente un emparejamiento. Si no, esto implica que $G$ no es bipartita, luego hay al menos un ciclo de longitud impar. Es fácil demostrar que siempre hay un ciclo de $3$ vértices (que haya uno con $5$ ó $7$ vértices implica que hay uno de $3$ (haciendo cosas con casillas). De aquí, hacemos los siguientes casos (una vez que completamos los casos, podemos suponer que no pasan al analizar los demás casos)
1-Hay dos ciclos ajenos de longitud $3$ en $G$.
2-Existen vértices $A,B,C,D,E,F$ en $G$ tales que tales que $A,B,C$ son amigos dos a dos y $D,C,B$ son amigos dos a dos, y $E$ y $F$ son amigos con $B$ y $C$ (ambos) pero no con $A$ ni con $D$.
Ahora, quitamos un par de amigos que no pertenezca al ciclo de longitud $3$, luego queda una gráfica $H$ donde $\deg(P)\geq 2$ para toda $P$ en $H$. Podemos suponer aquí que un vértice del ciclo está conectado con uno fuera (porque descartamos el caso 1). Sean $A,B,C$ los vértices del ciclo y $D$ un vértice fuera conectado con el ciclo, digamos con $A$, y $E,F$ los demás vértices. Luego hacemos los siguientes casos en $H$:
3-$E$ es amigo de $F$
4-s.p.g. $E$ es amigo de $D$ pero no de $F$
5- $A,B,C$ son amigos dos a dos y $D,C,B$ son amigos dos a dos, y $E$ y $F$ (cada uno) son amigos de cualesquiera dos vértices del ciclo (pero no ambos con $B$ y $C$, ya que ya habíamos descartado esta posibilidad del caso 2).
Pueden pedirme que les aclare cualquiera de los casos.
Publicar un comentario