La comunidad de olímpicos, ex-olímpicos, entrenadores y seguidores de la Olimpiada en Chihuahua, wherever they are in the world.
Por supuesto cualquier olímpico mexicano (para que parar ahí, de todo el mundo pues), esta invitado a comentar.
sábado, 6 de octubre de 2012
Problema del día. Combinatoria (6 de octubre)
En una reunión hay $9$ personas. Si yo agarro a $3$ personas al azar, puedo estar seguro que de esos $3$, $2$ no se conocen entre si. Demostrar que hay un grupo de $4$ personas que no se conocen entre si.
tenemos que si en cada grupo de tres dos no se conocen entre si entonces llamemos $a,b,c$ a las personas tienes que S.P.D.G. $a$ no conoce a $b$ entonces $a$ conoce a $c$ y $b$ conoce a $c$ pero $c$ no debe de conocer a alguien y $b$ tambien pero tienes que si se quita hay dos casos que $b$ no cosca a $d$ o que $c$ no conosca a $d$ tomamos el primer caso y tienes que ya ni $a$ ni $b$ ni $d$ se conocen y quitamos a otro por lotanto ya quedo pero sitomamos el segundo caso te da que pasaria igual y por eso ya quedo
Voy a explicarlo con grafos, donde un vértice es una persona y una arista es que alguien conoce a otro. Ya que de cualesquiera $3$ personas, $2$ no se conocen, no se pueden formar triángulos. S.P.D.G. Tomamos el vértice $a$ y trazamos todas las aristas posibles. Ya que no se pueden formar triángulos, no se pueden formar más aristas. Y se formaría un grupo de $8$ personas que no se conocen entre si. Para no tener $4$ vértices que no se pueden unir, eliminamos todas las aristas excepto $3$. Es decir, un vértice tiene a lo más $3$ aristas. Si hicieramos que cada vértice tuviera $3$ aristas serían $27$ en total, pero sabemos que la suma de los ordenes en un grafo es par, por lo tanto no se puede. Entonces a lo más habrían $8$ vertices con $3$ aristas y uno con $2$ . Es decir, $13$ aristas. Vemos que la máxima cantidad de arisats que se pueden hacer entre los $9$ vértices son $36$ ; $\frac{n(n-1)}{2}=\frac{9(8)}{2}=36$ Entonces hay $23$ aristas que no se pueden "trazar" , las cuales representarían que alguien no conoce a otro. Entonces si con esas aristas se forma un cuadrilatero, representaría a un grupo de $4$ personas que no se conocen. Estoy intentando demostrar que con esas $23$ aristas, se formará al menos un cuadrilatero.
Vemos que en total se pueden hacer $\binom{9}{4}=126$ cuadrilateros. Pero me fijo que puedo cancelar los que ya no se pueden usar por cause de las aristas que ya tengo, por cada arista, se cancelan $\binom{7}{2}=21$ , que es elegir los otros dos vertices de los $7$ restantes. Entonces se quitan $13\times21=273$ pero le agrego $13\times12=156$ porque es cuando con cada una de las diagonales, ya habian dos puntos elegidos por las otras $12$ aristas. Entonces nos quedan $273-156=117$ posibles cuadrilateros que se pueden hacer.
En que le agrego $156$ me equivoque porque $4$ de esas aristas salen de alguno de los dos puntos del vértice. Entonces le quito $(11\times8)+(2\times7)=102$ ; esas de $2\times11$ es cuando tomo en cuenta el vertice con solo un arista. Entonces quedan $273-102=171$ . La verdad no estoy muy seguro de esto que dije con los cuadrilateros... pero luego lo revisare y concluire.
Supongamos que hay uno que conoce al menos a 4, digamos A conoce a B,C,D,E. Por la condición del problema, si tomamos por ejemplo A,B,C, como A conoce a B y a C, B y C no se conocen. Hacemos esto con todos los grupos de tres que incluyen a A y tenemos que B,C,D,E no se conocen entre sí. Entonces el otro caso es que todos conozcan a lo más a tres, entonces cada uno no conoce al menos a 5,... y eso es lo que llevo.
Si represento el problema con grafos los vertices seran personas y las aristas indicaran que dos personas se conocen.Como en cualesquiera 3 personas dos no se conocen, entonces en los grafos no es posible construir un triangulo, entonces es un grafo arbol y a lo mas tendra 8 aristas.Entonces si suponemos que no existen cuatropersonas que se no conocen entre si, entonces en cualesquierea 4 vertices que escojamos es decir un cuadrilatero, siempre puede haber una linea que una dos de los 4 vertices,aun no puedo usar muy bien el hecho de de a lo mas hay 8 aristas para llegar a una contradiccion;eso es lo que llevo.
Intento.- Sean las 9 personas, 9 puntos sobre una circunferencia, si trazamos todas las lineas posibles (las cuales son 1+2+3+...+8=36) tenemos que para que se cumplan las condiciones del problema, sean lineas "de desconocimiento" aquellas que conectan a 2 puntos que no se conocen, no se deben formar cuadriláteros cíclicos con sus diagonales con líneas "de desconocimiento", lo cual es lo que aun estoy tratando de demostrar.
Comence a representar el problema con grafos. Luego me fije en que no ibas a poder formar triangulos y que se supone que la maxima cantidad de aristas que podria haber es $48$. Saque que iban a ser 48 porque dice que si escogemos a 3 personas al azar habra al menos 2 que no se conozcan. Esto significa que de 3 posibles relaciones de conocerse entre si, a lo mas habra 2. Entonces la maxima cantidad de aristas sera 2 tercios de $8*9$. Hasta aqui es a donde llegue. Luego continuo
comenze a ver varios casitos con puros grafos y todos son arboles el A1 conoce al menos a dos de los otros por que lo dice el problema si intentamos que todos conozcan el mismo numero de personas entonces al final nos quedan que las ultimas del el arbol conoen solo a 2 y que son diferentes entre si y si cumple pero aun no termino lo intentare aun
tenemos que si en cada grupo de tres dos no se conocen entre si entonces llamemos $a,b,c$ a las personas tienes que S.P.D.G. $a$ no conoce a $b$ entonces $a$ conoce a $c$ y $b$ conoce a $c$ pero $c$ no debe de conocer a alguien y $b$ tambien pero tienes que si se quita hay dos casos que $b$ no cosca a $d$ o que $c$ no conosca a $d$ tomamos el primer caso y tienes que ya ni $a$ ni $b$ ni $d$ se conocen y quitamos a otro por lotanto ya quedo pero sitomamos el segundo caso te da que pasaria igual y por eso ya quedo
ResponderBorrarno me queda claro por que $c$ debe de no conocer a alguien
BorrarEste comentario ha sido eliminado por el autor.
ResponderBorrarVoy a explicarlo con grafos, donde un vértice es una persona y una arista es que alguien conoce a otro.
ResponderBorrarYa que de cualesquiera $3$ personas, $2$ no se conocen, no se pueden formar triángulos.
S.P.D.G. Tomamos el vértice $a$ y trazamos todas las aristas posibles. Ya que no se pueden formar triángulos, no se pueden formar más aristas. Y se formaría un grupo de $8$ personas que no se conocen entre si.
Para no tener $4$ vértices que no se pueden unir, eliminamos todas las aristas excepto $3$. Es decir, un vértice tiene a lo más $3$ aristas.
Si hicieramos que cada vértice tuviera $3$ aristas serían $27$ en total, pero sabemos que la suma de los ordenes en un grafo es par, por lo tanto no se puede.
Entonces a lo más habrían $8$ vertices con $3$ aristas y uno con $2$ . Es decir, $13$ aristas.
Vemos que la máxima cantidad de arisats que se pueden hacer entre los $9$ vértices son $36$ ; $\frac{n(n-1)}{2}=\frac{9(8)}{2}=36$
Entonces hay $23$ aristas que no se pueden "trazar" , las cuales representarían que alguien no conoce a otro. Entonces si con esas aristas se forma un cuadrilatero, representaría a un grupo de $4$ personas que no se conocen.
Estoy intentando demostrar que con esas $23$ aristas, se formará al menos un cuadrilatero.
creo que te complicas mucho la existencia, ¿que te parece si tomas una persona en particular y ver que pasa en ciertos casos?
BorrarVemos que en total se pueden hacer $\binom{9}{4}=126$ cuadrilateros.
ResponderBorrarPero me fijo que puedo cancelar los que ya no se pueden usar por cause de las aristas que ya tengo, por cada arista, se cancelan $\binom{7}{2}=21$ , que es elegir los otros dos vertices de los $7$ restantes.
Entonces se quitan $13\times21=273$ pero le agrego $13\times12=156$ porque es cuando con cada una de las diagonales, ya habian dos puntos elegidos por las otras $12$ aristas.
Entonces nos quedan $273-156=117$ posibles cuadrilateros que se pueden hacer.
En que le agrego $156$ me equivoque porque $4$ de esas aristas salen de alguno de los dos puntos del vértice. Entonces le quito $(11\times8)+(2\times7)=102$ ; esas de $2\times11$ es cuando tomo en cuenta el vertice con solo un arista. Entonces quedan $273-102=171$ .
ResponderBorrarLa verdad no estoy muy seguro de esto que dije con los cuadrilateros... pero luego lo revisare y concluire.
http://www.facebook.com/photo.php?fbid=432016836856384&set=a.218311488226921.55464.100001442144670&type=1&theater
ResponderBorrarpartir de que A, B, C se desconocen es un caso particular a menos de que me puedas asegurar que siempre existira un grupo asi
BorrarSupongamos que hay uno que conoce al menos a 4, digamos A conoce a B,C,D,E.
ResponderBorrarPor la condición del problema, si tomamos por ejemplo A,B,C, como A conoce a B y a C, B y C no se conocen. Hacemos esto con todos los grupos de tres que incluyen a A y tenemos que B,C,D,E no se conocen entre sí.
Entonces el otro caso es que todos conozcan a lo más a tres, entonces cada uno no conoce al menos a 5,... y eso es lo que llevo.
vaz bien chacon, podrias ver que pasa si A desconoce a 6 o mas personas o si A desconoce a 5 y que pasaria en estos casos
BorrarEste comentario ha sido eliminado por el autor.
ResponderBorrarSi represento el problema con grafos los vertices seran personas y las aristas indicaran que dos personas se conocen.Como en cualesquiera 3 personas dos no se conocen, entonces en los grafos no es posible construir un triangulo, entonces es un grafo arbol y a lo mas tendra 8 aristas.Entonces si suponemos que no existen cuatropersonas que se no conocen entre si, entonces en cualesquierea 4 vertices que escojamos es decir un cuadrilatero, siempre puede haber una linea que una dos de los 4 vertices,aun no puedo usar muy bien el hecho de de a lo mas hay 8 aristas para llegar a una contradiccion;eso es lo que llevo.
ResponderBorrartrata de ver la figura en 2 colores
BorrarIntento.-
ResponderBorrarSean las 9 personas, 9 puntos sobre una circunferencia, si trazamos todas las lineas posibles (las cuales son 1+2+3+...+8=36) tenemos que para que se cumplan las condiciones del problema, sean lineas "de desconocimiento" aquellas que conectan a 2 puntos que no se conocen, no se deben formar cuadriláteros cíclicos con sus diagonales con líneas "de desconocimiento", lo cual es lo que aun estoy tratando de demostrar.
y si tratas de ver casos en que el desconocimiento es mayor o menor
BorrarComence a representar el problema con grafos. Luego me fije en que no ibas a poder formar triangulos y que se supone que la maxima cantidad de aristas que podria haber es $48$. Saque que iban a ser 48 porque dice que si escogemos a 3 personas al azar habra al menos 2 que no se conozcan. Esto significa que de 3 posibles relaciones de conocerse entre si, a lo mas habra 2. Entonces la maxima cantidad de aristas sera 2 tercios de $8*9$. Hasta aqui es a donde llegue. Luego continuo
ResponderBorrares posible hacer triangulos si son de desconocimiento, y son solo 36 las posibles aristas
Borrarcomenze a ver varios casitos con puros grafos y todos son arboles
ResponderBorrarel A1 conoce al menos a dos de los otros por que lo dice el problema
si intentamos que todos conozcan el mismo numero de personas entonces al final nos quedan que las ultimas del el arbol conoen solo a 2 y que son diferentes entre si y si cumple pero aun no termino
lo intentare aun
no necesariamente todos conocen a la misma cantidad de gente
Borrar