42.EL CONGRESO INTERNACIONAL( Concurso de problemas)
|
42.EL CONGRESO INTERNACIONAL( Concurso de problemas) |
|
|
A un Congreso Internacional asisten 1000 delegados de diversos países. Cada uno de ellos habla varios idiomas. Se sabe que si formamos grupos, cualesquiera, de tres delegados entre ellos se pueden entender(uno de ellos hace eventualmente de interprete de los otros dos). Demostrar que se pueden alojar a los mil delegados en habitaciones de dos personas, de manera que entre ellas se comuniquen. Si en vez de 1000 personas hay 5000 personas. ¿ Se podría demostrar? HA PASADO CASI UN AÑO DESDE QUE ESTA SECCIÓN COMENZÓ A CAMINAR. LA COMISIÓN DE DivulgaMAT QUIERE ANIMAROS A PARTICIPAR EN EL " CONCURSO DE PROBLEMAS". DE MOMENTO OS PLANTEAMOS DOS RETOS MATEMATICOS( Uno de nivel A y el otro de Nivel B). PODEÍS MANDAR VUESTRAS SOLUCCIONES A LA SIGUIENTE DIRECCIÓN: Esta dirección electrónica esta protegida contra spambots. Es necesario activar Javascript para visualizarla SE ADMITIRÁN LAS SOLUCCIONES HASTA EL DÍA 15 de MAYO de 2005 ENTRE TODAS LAS PERSONAS QUE RESUELVAN BIEN DICHOS RETOS(SE VALORARÁ LA ORIGINALIDAD, ELEGANCIA Y PLANTEAMIENTO DE LA SOLUCCIÓN) SE SORTEARÁN DOS LIBROS SOBRE DIVULGACIÓN MATEMÁTICA. ! ÁNIMO!
La respuesta es que sí, tanto para 1000 congresistas como para 5000. Centrémonos en un grupo de cuatro. Llamémoslos A, B, C y D. No son nombres muy originales, pero algo facilitarán la tarea. Supongamos que en el trío formado por A, B y C, quienes se entiendan sean al menos la pareja formada por A y B y la compuesta por B y C. Si no es así, los reordenamos y renombramos para que ocurra. Escojamos ahora el trío formado por A, C y D. Pueden darse tres casos: 1.-Al menos se entienden las parejas formadas por A y C y por C y D. Entonces, alojamos en una habitación a A y B y en otra a C y D. 2.-Al menos se entienden las parejas formadas por A y D y por C y D. Entonces, alojamos en una habitación a A y B y en otra a C y D. 3.-Al menos se entienden las parejas formadas por A y C y por A y D. Entonces, alojamos en una habitación a B y C y en otra a A y D. Hemos demostrado que para cualquier grupo de cuatro es posible; luego para cualquier múltiplo de cuatro también. Por lo tanto, la hipótesis es válida tanto para 1000 como para 5000 congresistas. Esta solución ha sido aportada por D. Alberto Castaño Domínguez SEGUNDA SOLUCIÓN Si planteamos el problema con un grafo: cada delegado es un vértice, y unimos 2 vértices con una arista si los delegados correspondientes se entienden directamente, nos queda un grafo con 1000 vértices (suponemos que si una persona entiende un idioma habla ese idioma, luego si una persona entiende el idioma del otro le puede hablar también en su idioma, y por tanto las dos personas se entienden. Entonces las aristas son no dirigidas). Por las condiciones que nos dan, cada grupo de 3 vértices está unido por al menos 2 aristas, ya que ó las 3 personas se entienden directamente 2 a 2, ó una entiende a las otras 2 y entonces puede hacer de intérprete. Con esa condición lo que hay que ver es si existe un emparejamiento en el grafo, es decir, 500 aristas en la que están los 1000 vértices, porque así se les puede emparejar en las habitaciones consiguiendo que se entiendan. Lo demostramos en general por inducción para todo grafo con n vértices, n par mayor ó igual que 4, por lo que el resultado será cierto para n=1000 y para 5000. Si n=4, en el grafo de 4 vértices cada grupo de 3 tiene al menos 2 aristas que lo une. Si disponemos los vértices como un cuadrado y cogemos todos menos el de arriba a la derecha, sabemos que ese grupo de 3 vértices tiene al menos 2 aristas que lo une. Si tiene 2, entonces cogiendo otro grupo con los 2 no adyacentes (los no unidos por una arista) y el de arriba a la derecha, sabemos que hay al menos 2 aristas que lo une, que irán de los 2 vértices no adyacentes al de arriba a la derecha, y entonces se puede emparejar al de arriba a la derecha con uno de los no adyacentes, y al otro de los no adyacentes con el que queda. Si los 3 iniciales tienen 3 aristas que les unen se forma un triángulo entre ellos, y entonces formando otro grupo con 2 vértices cualquiera del triángulo y el de arriba a la derecha, como hay al menos 2 aristas que lo une, hay al menos una arista de uno de los vértices del triángulo al de arriba a la derecha. Emparejamos entonces a estos por un lado, y a los otros 2 vértices del triángulo por el otro. Lo suponemos cierto para grafos de m vértices, con m comprendido entre 4 y n,con m par.( no pudiendo alcanzar n) Para grafos de n vértices, n par, si cogemos un grupo de 3 vértices hay al menos 2 aristas que lo une. Entonces, si cogemos 2 de estos 3 vértices que sean adyacentes y los quitamos del grafo, nos queda un grafo de n-2 vértices en el que cada grupo de 3 vértices tiene al menos 2 aristas que lo une, luego existe un emparejamiento de estos n-2 vértices (inducción) que, unido a la arista que une a los 2 vértices que hemos quitado, da un emparejamiento de los n vértices. Esta solución ha sido aportada por D.Javier Rodrigo . |