(#86) Los 100 duendecillos.
En un bosque del país de los duendes, viven 100 duendecillos. No todos son amigos de todos. Incluso puede que haya alguno que no tiene ningún amigo. Únicamente puede decirse que si un duendecillo es amigo de otro, éste también lo es de aquél (cosa normal, por otra parte).
A estos duendecillos puede vérseles elegantemente ataviados con un bonito manto de doble vuelta. Por un lado es blanco y por el otro negro. Cada cual luce su manto con el color que le apetece. Pero hete aquí que el caprichoso rey de este país, que por cierto no utiliza ese manto, ha dictado un decreto según el cual los duendes habrán de hacer lo siguiente.
Cada día, sucesivamente, un duende visitará a todos sus amigos (sólo a sus amigos). Tras ello, si el número de amigos que lucen el manto de color diferente al suyo es mayor que el de los que lo lucen del mismo color, el duendecillo habrá de dar la vuelta a su manto. Al día siguiente otro duende hará lo mismo, de modo que en 100 días todos los duendes habrán realizado una visita a sus amigos. Cumplidos estos 100 días, las rondas de visitas comienzan de nuevo por el primer duendecillo que las inició.
El rey ha decidido que las rondas de visitas continúen hasta que:
  • a) Todos los duendecillos acaben con el manto del mismo color, o
  • b) ninguno de los duendecillos haya de dar vuelta a su manto, porque no son mayoría los amigos que lo lucen de color diferente.
    ¿Acabarán todos duendecillos luciendo sus mantos del mismo color?
    ¿Están condenados eternamente a realizar las rondas de visitas ordenadas por el caprichoso rey?.
    Nota "Ante la incertidumbre provocada por el decreto del rey, los duendecillos han recurrido a uno de ellos, famoso por su afición a las matemáticas. Éste, tras un ¡breve! análisis de la situación les ha tranquilizado asegurándoles que el capricho del rey no les supone una condena eterna. Y que, por otra parte, la coquetería de los duendecillos no está amenazada, pues lo más probable es que no todos acaben con el manto del mismo color (aunque esto último no se lo ha podido asegurar)".

  • mano_dSolución de José H. Nieto
    La respuesta a la primera pregunta es "NO NECESARIAMENTE". Basta por ejemplo que haya dos duendes sin amigos que usen mantos de distinto color: nada los hará cambiar. O que dos duendes sean amigos si y sólo si usan el manto del mismo color (y que haya por lo menos uno de cada color). En fin, hay muchas configuraciones estables que no son monocromáticas.

    La respuesta a la segunda pregunta es definitivamente "NO". Para probarlo definamos, para cada duende x,
    M(x) = {amigos de x que usan el manto del mismo color que x}
    D(x) = {amigos de x que usan el manto de color diferente al de x}

    Sea e(x) = #M(x) - #D(x) (# significa número de elementos)
    En otras palabras, la "estabilidad" e(x) de un duende x es la diferencia entre el número de sus amigos que usan el manto del mismo color que él y el número de sus amigos que usan el manto de diferente color que él.

    Finalmente definamos la "estabilidad global" E como la suma de las 100 cantidades e(x).
    Un duende x cambiará el color de su manto el día que le toca visitar a sus amigos, si y sólo si e(x) < 0 al comienzo del día. En ese caso si m = #M(x) y d = #D(x), cuando x dé vuelta su manto su estabilidad pasará de a d - m > 0, aumentando 2(d - m) unidades.
    En ese mismo instante la estabilidad de cada miembro de M(x) disminuirá en 2 unidades, y la de cada miembro de D(x) aumentará en 2 unidades. Por lo tanto la estabilidad global aumentará en

    2(d - m) - 2m + 2d = 4(d - m) unidades

    Ahora bien, la estabilidad global E no puede crecer indefinidamente, ya que e(x) 99 para todo x y en consecuencia E 9900. Por lo tanto el número de cambios de color debe ser finito, y llegará un momento a partir del cual no habrá más cambios.
    Saludos. José H. Nieto



    Recibida la solución y puesto en contacto con Martín, al fin y al cabo el problema era suyo, me pide que indicara lo siguiente. Y gustosamente ahí va.

    " Mi agradecimiento a algunos de los colaboradores más o menos asiduos de "La Gacetilla", de los cuales me consta que conocían la solución, y que por deferencia a la antigua amistad (virtual, por lo demás) que nos une, han guardado una loable discreción. Me refiero, concretamente a Ignacio Larrosa, Pablo Sussi, y, tal vez, José Carrión. A los tres quiero darles las gracias.
    Sé que conocman la solución, pues el problema fue propuesto, hace ahora más de un año, en la lista de "Snark".
    Mi único mérito fue aportar, en su momento, una solución, y darle una redaccisn más lírica con el fin de hacerlo más atractivo.
    Tal vez lo compliqué demasiado al elevar el número de duendecillos a 100 (en su redacción original eran doce, y además, enanos, no duendecillos).
    Saludos. Martín López"

    Y ahí va el razonamiento facilitado por Martín en su momento.

    Supongamos 5 duendecillos A, B, C, D y E. suponemos que los colores que lucen incialmente en su manto son BBNNB respectivamente. supongamos que A es amigo de B, C y D; B lo es de A y C; C lo es de A, B y D y D lo es de C y A. Supongamos que E no tiene amigos
    Representamos las relaciones de amistad mediante un grafo, en el que los enanos serán puntos y los amigos estarán unidos por una arista.
    Además, esa arista será azul si los dos amigos lucen su manto del mismo colo y roja si lo lucen de color diferente.

    Tras la visita del enano A a sus amigos encuentra (1) que dos de ellos llevan el manto de color diferente al suyo (el C y el D) y uno (el B) del mismo color. Por ello da vuelta a su manto. Pero al cambiar su manto de color todas las aristas que concurren en A (una por cada amigo suyo) cambian de color. Si antes concurrían dos rojas y una azul en A, ahora habrá dos azules y una roja. Las aristas que no concurren en A no cambian, pues corresponden a duendecillos que no son amigos de A. Como esto se hace cuando el número de rojas es mayor que el de azules, se deduce que el número total de rojas en el diagrama habrá disminuido. En cada visita, el número total de rojas disminuye (si el duende da vuelta al manto) o queda igual (si no da vuelta al manto). Luego una de dos:
      O el número de aristas rojas llega a ser cero, con lo cual todas las aristas serán azules y, por lo tanto ya ningún duendecillo habrá de dar vuelta a su manto
      O el núero de aristas rojas no disminuye más (porque ningún duendecillo se ve obligado a dar vuelta a su manto).
    En (2) el duendecillo B encuentra que sus amigos A y C llevan el manto de diferente color al suyo, por lo que da la vuelta a su manto y la situación queda como en (3). A partir de aquí tras las sucesivas visitas de los siguientes enanos ninguno dará vuelta a su manto.

    En cualquiera de los casos la conclusión es que llegará un momento en que los duendecillos ya no darán vuelta a su manto.
    Sin embargo, no puede asegurarse que todos los los duende acaben con el mismo color de manto. Basta considerar que el duendecillo E no cambia su manto de color nunca. No tiene amigos. Además podrían darse determinadas relaciones de amistad en las que habría grupos cerrados de amigos todos entre sí, que acabarían con sus mantos de un color y otros grupos igualmente cerrados de amigos que acabarían con sus mantos del otro color.


     
      (#86) Los 100 duendecillos