Solución Desafío 49: Los mensajeros


Escribe Maito:

Creo que este desafío ha resultado ser menos intuitivo de lo que me
parecía, sólo se han recibido 7 respuestas correctas, el primero
Pardillano seguido de Jabón el cual lo explica muy gráficamente, JC
aporta además la demostración de que en realidad hay dos triángulos
monocolor, Jesús Chus nos presenta una solución muy entretenida y
completamos la lista con  Jose Luis (una vez que abandonó el Excel),
Angel (el conciso) y SuperPanZ, que casi redescubre y demuestra la
Teoría de Ramsey el sólito.
Aunque el logro del fin de semana es que el blog de Santi ha
conseguido el disco de platino al alcanzar las 100.000 visitas con el
que podrá obsequiar a su futura retoña. Doble enhorabuena.

En la solución al problema vamos a ir aplicando recurrentemente el
principio del palomar.
Consideremos uno de los vértices de un hexágono, por ejemplo el 1, con
él se relacionan los otros cinco formando cinco segmentos y al menos
tres de ellos deben ser del mismo color, supongamos que son rojos los
segmentos entre el 1 y los vértices 2, 3 y 4.
Si alguno de los segmentos entre estos tres vértices fuese rojo, por
ejemplo el formado por el 2 y el 3, entonces el triángulo formado por
los vértices 1, 2 y 3 sería rojo.
Si ninguno de los segmentos entre estos tres vértices fuese rojo,
entonces el triángulo formado por los vértices 2, 3 y 4 sería azul.
Luego siempre existe un triángulo de un solo color.

Vamos ahora con el polígono de 17 lados coloreado de rojo, azul y
verde. Nos volvemos a fijar en el vértice 1, como de el parten 16
segmentos y tenemos tres colores, al menos hay un color del que se han
pintado 6 segmentos, pongamos que es el rojo y que los segmentos son
con los vértices 2, 3, 4, 5, 6 y 7.
Si alguno de los segmentos entre estos seis vértices es rojo, por
ejemplo, el 2-3, entonces, el triángulo formando por los vértices 1, 2
y 3 sería rojo.
En caso contrario los seis vértices 2, 3, 4, 5, 6 y 7 están unidos por
segmentos de color azul y verde, y como hemos demostrado en el
apartado anterior, debe haber por lo tanto al menos un triángulo de un
solo color (azul o verde).

Si queréis profundizar sobre este tema podéis empezar por la wiki
Teoría de Ramsey y tirar del hilo. En este desafío hemos demostrado el
valor de dos números de Ramsey R(3; 3) = 6 y  R(3; 3; 3) = 17
Y como apuntaba Jabon, si queremos escalar el problema, podemos
obtener fácilmente los números de oficinas (R) en función del número
de mensajeros (n) mediante la fórmula
Rn+1=n * (Rn – 1) + 2 empezando en el caso trivial de R1= 3
Una vez más ha sido un placer compartir vuestras aportaciones para
hacer los desafíos mejor de lo que originalmente planteamos.

Un saludo
Jose Luis

ARCHIVOS:

D49 Jabon
D49 JC
D49 Jesús Chus
D49 Jose Luis
D49 Pardillano
D49 Superpanzeta
D49 Ángel 

El jueves alcanzamos los 50 con Gerardo.

Saludos.

9 comentarios

Archivado bajo OTROS

9 Respuestas a “Solución Desafío 49: Los mensajeros

  1. Superpanzeta

    Qué susto:
    Números de Ramsey->Teorema de Ramsey->Aritmética de Peano->Teorema de Incompletitud de Gödel->Teorema de Paris-Harrington

    Por un momento había leído Paris Hilton.

    Bromas aparte, enhorabuena, Maito. Menudo desafío…
    Da miedo asomarse a las profundidades.

  2. Divagante

    Muy bonito. Viendo ahora la solucion estuve muy cerca de verla de casualidad, pero me quedé eso, solo cerca.

    Enhorabuena.

  3. jabon

    A raíz del comentario de Maito, descubrí el Teorema de la amistad. Muy interesante.

  4. JC

    Superpanzeta, el camino que abandonaste de “contar todo lo contable” creo que también es válido, para saber exactamente cuantos triángulos bicolor se forman (y por tanto cuantos monocolor), si contamos las líneas rojas que salen de cada vértice, y tenemos en cuenta que el número de ángulos bicolor es justo el doble que el número de triángulos bicolor.
    Y así usamos excel también.
    Lo puedes ver a partir de la página 5 del pdf…
    https://docs.google.com/open?id=1c1ZxLGp1DZchF1nt1ku3MMSBp7Z32bolDw3zGZS33FSofi-u11ZTkDvmBlXs

    • Superpanzeta

      Impresionante.
      h(spz) = h(betún)
      (SuperPanZ a la altura del betún)
      Cuando pueda le echo un vistazo. Espero entenderlo todo.
      Gracias por todo.

    • Superpanzeta

      Se entiende todo muy bien. Me gusta mucho.
      Se nota que tienes la mente mucho más despejada que uno que yo me sé…
      Es cierto. Contar todo lo contable también lleva a la demostración (algo que yo no fui capaz de hacer), pero hay que reconocer que la demostración original gana por goleada en sencillez, y es francamente más bonita.
      Buen trabajo, en cualquier caso.

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