Desafío 40+9: Los mensajeros


Escribe maito:

Una empresa tiene un servicio de mensajería entre sus seis oficinas de manera que todos los días conecta todas las oficinas entre sí. Este servicio lo cubre con dos mensajeros y se trata de demostrar que al final del día al menos uno de los mensajeros ha hecho todas las conexiones entre tres oficinas.
Con el tiempo la empresa abrió once oficinas más y contrató otro mensajero (cambiando las bicis por motocicletas), ¿se sigue cumpliendo que al final del día al menos uno de los mensajeros ha hecho todas las conexiones entre tres oficinas?
Por ejemplo en la figura 1 vemos que para 5 oficinas si es posible encontrar dos rutas en las que ningún mensajero ha conectado 3 oficinas entre sí.
En cambio en la figura 2, vemos que el mensajero de la moto roja ha conectado entre sí las oficinas 1 , 2 y 3.

Respuestas a desafiossanti@gmail.com antes del lunes a las 23:59.

51 comentarios

Archivado bajo OTROS

51 Respuestas a “Desafío 40+9: Los mensajeros

  1. José Luis

    Bah, es fácil, basta analizar 1.126 billones de casos.
    ¡Espera!, el texto dice ’11 oficinas más’, no 11 oficinas, eso hace 87.000 sextillones…

  2. jabon

    Maito, tiene buena pinta. Nos pondremos el fin de semana con ello.

  3. Superpanzeta

    Interpreto que las rutas de los repartidores deben ser continuas.
    Esto va a ser difícil. No se me ocurre ni cómo contar los casos…

    • JC

      Por ejemplo en la figura 1 el motorista azul hace la “ruta cerrada” 1-2-3-4-5-1, y el motorista rojo hace la “ruta cerrada” 1-3-5-2-4-1. Pero no sé si esto lo hemos de tomar como hipótesis del problema o no.

      • Superpanzeta

        No, cerradas, no. Sólo continuas.
        Hay una azul claro que no se cierra en el ejemplo 2.

        • Superpanzeta

          Bueno, la roja del ejemplo 2 tampoco se cierra. Empieza en 2 y acaba en 3, o al revés.
          Pero fijándome mejor veo que hay dos trayectorias azul claro:
          Una entre 1 y 6, y otra entre 4 y 5.
          Estas dos son discontinuas.
          Hey Maito, ¿cuantos motoristas hay en el ejemplo 2?
          Es decir, ¿se permiten las trayectorias discontinuas o no?

          • Maito

            Parece que no he sido muy claro en la exposición. En el primer caso 6 oficinas 2 mensajeros, en el segundo 17 oficinas 3 mensajeros. Se buscan rutas que conecten 3 oficinas entre sí por un mismo mensajero.
            Los mensajeros no tienen por que hacer rutas continuas.
            Esta semana os recomiendo que os olvidesis del excel y la programación.
            Y tener couidado con el hielo no se vaya a resbalar la moto.
            Espero que disfruteis.

          • Superpanzeta

            Vale, entendido. El enunciado está muy claro, y no descarta nada. Lo que me despistaba un poco son los ejemplos, que sí que (me parecía que) descartaban las trayectorias discontinuas.
            Reconocerás que no es muy lógico que un motorista se desplace de una oficina a otra para empezar una nueva ruta sin aprovechar el viaje, pero la geometría es así.
            Ahora no sé si es más fácil o más difícil.
            Me da la sensación de que más fácil. Pero aún no sé por qué.

  4. jabon

    Creo tener ya una respuesta, menos farragosa de lo que pensaba al ir por esa línea, pero me imagino que distante de la que será la oficial.
    Esperaré un poco a mandártela a ver si se me ocurre algo más original.

  5. Anónimo

    Me pierdo un poco. ¿La cuestion es demostrar que hagamos como hagamos la ruta al menos un mensajero ha hecho todas las rutas entre tres oficinas o demostrar que podemos encontrar al menos una ruta en la que un motorista ha hecho todas las rutas entre tres oficinas?.
    Por cierto, en la solución del desafio de pintura he dejado un comentario con el tema de las bases decimales que creo que soluciona el problema que le veía Pardillano, pero ya me diréis.

  6. Divagante

    Una cuestión. ¿Tenemos que demostrar que hagamos como hagamos las rutas encontraremos una moto que hace todas las rutas de tres oficinas o demostramos que podemos encontrar al menos una ruta donde uno de los motoristas haga todas las rutas de 3 oficinas?
    Volviendo a las bases decimales he dejado un comentario que aparentemente soluciona el problema que veía Pardillano a los coeficientes de las bases decimales.

    • Maito

      No entiendo muy bien la diferencia, pero me inclinaría más bien por la primera. Es decir, hagamos como hagamos las rutas siempre va a existir una entre tres oficinas efectuada por el mismo mensajero.

  7. jabon

    No sé si me he pegado una leche con la moto de Angel Nieto, pero como Maito nos ha picado a utilizar el excell…

    Para (12+1) motoristas, ¿hablaríamos de 16926797487 oficinas?

    Seguro que he resbalado en el hielo, pero así calentamos motores. Ron, ron, ron, ron.

    En cuanto a la respuesta, sigo con la misma. Algo más depurada, pero en la misma línea.

  8. Divagante

    Santi. 327 para 100.000. Tendrás preparada la botella de xampagne o de cava (catalán o valenciano)

    • jabon

      En efecto Divagante, se acercan los 100.000. Felicidades para Santi, porque creo que se conseguirán hoy.
      Por cierto, el supuesto es mucho más interesante de lo que aparenta ese sencillo enunciado.
      Hasta ahora no me he atrevido a dar ninguna pista porque lo consideré demasiado pronto. Bueno, la del número (12+1), pero esa sólo sirve si se resuelve antes. El método para demostrar, sería muy similar en ese supuesto; aunque pudiera no ser necesario recurrir a tantos números para que se cumpla.

  9. jabon

    Maito, he leído lo que me has comentado, y de paso he husmeado algo más. Me ha resultado interesante.
    En un archivo he llegado a encontrar incluso lo que sería la demostración, y es lo que es. Casi se me antoja difícil que exista otra vía distinta. Yo pensaba que saldrían varias, y no lo sé, no lo tengo tan claro, aunque todo puede ser.
    Llegué a pensar que la mía no sería la oficial, pero veo que sí. Naturalmente, no tan brillante.

  10. JC

    Creo que lo mejor es buscar una explicación gráfica, y no intentarlo con combinaciones o cosas por el estilo. Para mi la primera pregunta es más fácil (porque me parece más fácil 6 que 17).
    Así que papel, bolis de colores, y suerte.

  11. Maito

    Os veo poco animados, si no os gustan los mensajeros en moto probar con palomas mensajeras y anillas de colores.

    • Superpanzeta

      Yo estoy animado, no te preocupes.
      Lo tengo todo a punto. He contado todo lo que hace falta (con y sin combinatoria)… menos lo que hace falta.
      No sé si me falla el papel, los bolis de colores o la suerte, pero necesito un algoritmo que evite ciertas cosas (no quiero dar pistas) y no me sale.
      Conforme voy poniendo más puntos más difícil me resulta encontrar cierto máximo. De momento no veo ninguna regularidad, así que está claro que necesito una idea feliz para diseñar el algoritmo y poder contar con seguridad para decidir la respuesta.
      Sigo pensando.

      La de tonterías que hay que escribir para no dar pistas…
      Por cierto, viendo el “resultado” de 12+1 motoristas de Jabón la respuesta está clara, porque si no, Jabón no habría extrapolado a partir del número de motoristas. Supongo.

  12. Superpanzeta

    Ya sólo faltan 5 para 100000!

  13. Superpanzeta

    Ejem, estaría bien, pero eso de arriba no era un factorial. :)

  14. jabon

    Santi, Felicidades, pasaste ya de los 100.000.
    Superpan, esta vez creo que hay que olvidarse de algoritmos y pensar en algo más gráfico.
    Sacando el 6-2, el 17-3 se hace más fácil. Así que si vamos uniendo las pistas que van por ahí, se puede focalizar bastante la vía.

    Le he dado alguna vuelta más, y no encuentro ninguna otra forma para dar respuesta. Me imagino que con la misma idea habremos planteado variantes, cada uno. Maito ya me indicó que su respuesta va en la misma línea, sólo que debemos tener matices un poco diferentes.

    El problema está muy relacionado con uno que tiene que resultar muy conocido. Cuando lo leí (después de indagar, tras el comentario que me hizo Maito) me resultó muy curioso. No lo comento, porque si no es como dar ya la respuesta, porque lo he visto en la red con la solución incluida.

  15. ¡Muchas gracias a todos!
    Si me dicen cuando empecé con esto que iba a llegar a las 100000 visitas… increíble. Esta semana como sea sacaré un rato para el problema.

  16. atjgp

    Me suena mucho a números de Ramsey

  17. jabon

    Un chiste que me acabo de inventar.
    Jaimito está intentando resolver un problema en la pizarra, y cuando ve que ya no hay manera, le dice a la señorita:
    – Es que no sé lo que hay que hacer
    La profesora le contesta:
    – DI-VI-DIR
    Jaimito, ya contento, dice:
    – ¡VIDIR¡

    • Superpanzeta

      Muy bien, ya puedes dejar la medicación.
      (Es broma).
      Ya veo que te aburres. A mí se me acaba el tiempo, y ya casi me he rendido. Tu chiste me pilla escribiendo un mensaje a Maito a ver si voy bien o no, así que bien podría decir VIDIR yo también.
      ¿Alguna pista subliminal de esas tuyas?

      Eh… ¿el chiste no será un pista? O_o

      • jabon

        Superpan, si es chiste es muy malo, si es pista ya no sé si es buena

        • Superpanzeta

          Caray que subjuntivo estás.

          • jabon

            Con el permiso de Maito, que ya han pasado más de 48 horas, ¿Te atreves a probar si el enunciado sirve para cuatro moteros y 66 oficinas?

          • Superpanzeta

            Pues no ,señorita. XD
            La verdad es que no. Si supera hacer eso, sabría hacer el de 3 y 17, o el de 13 y el número gigante ese que pusiste.
            Resolver (por decir algo) los pequeños a lo bruto no me ha servido de nada.

            Tengo todas las cantidades contadas, pero no veo la relación…
            A ver si fijándome en todos esos números veo la luz.

            Gracias de todas formas. No creo que tenga tiempo de gastar más papel, pero seguiré pensando.

  18. jabon

    Me voy a ir a tapear, espero que a la vuelta ya lo tengas resuelto. A Maito, sé que le gustará que lo acertemos todos, y hayamos pasado un rato agradable. Para mí esa es la filosofía. Por eso sé que me perdonará si apunto un dato más.
    Si ya sabes que 5 moteros van a 327 oficinas, y todo el resto que ya hemos comentado. ¿Cabe la posibilidad de que entre todos esos datos pueda existir un nexo en común?

  19. Maito

    Jabon os está dando pistas de como se podría ir complicando el problema según aumentan los mensajeros, esto se debería interpretar como que si lo sñe soluciona para un número menor entonces lo se solucionar para el siguiente. Es decir es un algoritmo para ver cual sería el siguiente nivel de complejidad, no es un algoritmo para resolver el primero, para ese hay una idea feliz, que seguro entre todos los amigos logramos inspirarla.

  20. JC

    La clave está en resolver el caso 6-2 (6 puntos y 2 colores). Lo que hay que demostrar es que es imposible conectar todas entre sí sin que al menos se forme 1 “triángulo” monocolor.
    Realmente al menos se forman 2, por ejemplo en la figura 2 tenemos el triángulo rojo 1-2-3 y el triángulo azul 1-4-5.
    Pero esto último no es una pista, porque es más fácil demostrar que al menos se forma 1 “triángulo” monocolor que demostrar que al menos se forman 2. Creo que la “idea feliz” para demostrar que al menos se forman 2 es más complicada que la idea para demostrar que al menos se forma 1.

  21. Superpanzeta

    Haciendo trampa con el sr. S., he encontrado la relación entre los números, y de ahí el teorema del sr. R., y la relación con las palomas, y la solución.
    Es impresionante lo cerca que estaba. Si hubiera buscado en la red las palabras exactas con que había formulado mi intento incompleto, habría encontrado la misma página. Exactamente al misma terminología. Parece como si la hubiera redactado yo…
    Es una pena que no haya visto la idea feliz. Otra vez será.

    • Maito

      Es lo malo de internet, es este caso se puede ver la solución exacta. Una lástima SupenPanZ, pues lo habías planteado muy bien matemáticamente, aunque en este caso hay un camino sencillo. Para los que sigais intentándolo os sugiero que no usqueis en internet y os fijñeis en las pistas dadas hasta ahora.

      • Superpanzeta

        No he querido estudiarlo. Me dejo la lectura detallada para el martes.
        De momento, sólo tengo tengo la demostración del caso 2,6 (no sé si es la “sencilla” o no).
        Aún no sé cómo se generaliza al resto de los casos.
        Seguiré pensando a ver que se me ocurre.

  22. Divagante

    No se por donde meterle mano. Ni siquiera se me ocurre por donde empezar a buscar en internet (cosa que tampoco pienso hacer). Si mañana no se me ocurre nada el martes veré la solucion.

  23. jabon

    Divagante, piensa en el caso 6-2.
    Olvídate de números de combinatoria y ponte a dibujar. Es como mejor se ve. Intenta que no ocurra y verás que sí. Compara.
    Si no quieres gastar papel y tinta, el Paint es un buen recurso.
    La idea es relativamente simple. Una vez que la saques (la idea, no otra cosa) el siguiente paso es relativamente fácil, y los siguientes salen solos.

    • Superpanzeta

      Pues a mí el paso final al 3,17 no me gusta nada. Me da la sensación de que lo estoy haciendo más difícil de la cuenta.
      El desafío no es que sea relativamente fácil, es que no es fácil. Y lo dice uno que ha manchado más de una docena de folios por las dos caras.

      • jabon

        Superpan, no sé cómo habrás probado el primer paso, pero el segundo se basaría prácticamente en lo
        mismo, si el anterior lo haces de una forma concreta. Y el siguiente igual.

        • Superpanzeta

          Sí, ya lo tengo, gracias. Me vino la inspiración en la cama.
          Había empezado bien y luego me había liado a explorar todas las posibilidades. Qué tonto soy.

  24. Nada, no hay manera. Llegados a este punto querría explicar un poco mis ausencias. Resulta que la familia va a aumentar en breve, hasta ahí normal. Resulta también que la mamá de la criatura, que será una niña, está a reposo por algunos problemillas derivados de su estado. Si a eso le añadimos que no contamos con nadie que nos eche un cable, comprenderéis que mi vida en este momento se divide entre trabajar, hacer comidas, limpiar, cuidar a la familia… y cuando me queda un ratito no tengo cuerpo ni neuronas para retos.
    Dicho esto, estoy encantado de que sigáis manteniendo el blog activo y por supuesto seguiré publicando y gestionando todo lo que me queráis enviar. Sigo pensando que alguna de estas semanas podré participar, pero la realidad es muy cabezota…

    • Superpanzeta

      Yo pensaba que estabas de exámenes o algo así, pero esto es mucho mejor. ¡Una niña!
      ¡¡¡Enhorabuena!!!

      No te preocupes, la familia es lo primero. Cuida de la mamá.
      ¡Y recuerdos también a Gaizka!

      P.D. No la llaméis Hipatia, que ya está cogido…

    • Sebas

      Enhorabuena!!!!!!
      Tu a lo tuyo que es lo primero

  25. jabon

    Me sumo a la enhorabuena. Esto sí que es una noticia buena.
    Esperemos que estos dos últimos casos sean sólo un brote, y no podamos
    hablar de epidemia en el blog.
    Gaizka, también para tí.

  26. Superpanzeta

    Para Divagante:
    Puede que sea tarde, pero igual te sirve de algo.
    No cometas el mismo error que yo poniéndote a contar todo lo contable.
    Por ejemplo, mi línea de investigación pasó por contar cuántos triángulos había, cuántas líneas, a cuántos triángulos pertenecía cada línea, cuántos triángulos convergen en cada vértice (cosas de esas), y finalmente, cuántas líneas podía trazar cada mensajero. Esperaba relacionar de alguna manera estas cantidades para averiguar si el número mínimo de líneas trazado por el repartidor más trabajador superaba alguna relación entre las cosas que había contado.
    Pero no. Todavía no sé por qué, pero el número de líneas o de triángulos no sirve de nada. Estoy casi seguro de que debe haber alguna demostración basada en el número de líneas, pero no se me ha ocurrido nada, y lo que encontré en la red no lo usa para nada.
    Lo fastidioso es que es mucho más simple.

    En fin, lo dicho. No te sientas mal si te rindes.
    Yo debería haberlo hecho.

Responder

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión / Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión / Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión / Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión / Cambiar )

Conectando a %s