miércoles, 13 de abril de 2011

Un reloj de dos colores o el Teorema de Bolzano discreto

Pues ya se ha publicado la solución al 4º Desafío Matemáticos que se publican en El País con motivo del centenario de la Real Sociedad Matemática Española.

El problema lo han titulado Un reloj de dos colores y ha sido propuesto por una estudiante de doctorado de la Universidad Politécnica de Cataluña, Elisa Lorenzo García. Dado un reloj, coloreamos de rojo 6 de sus números y de azul los otros 6; el problema consiste en demostrar que, independientemente de la coloración, siempre podremos encontrar una recta que a cada lado deje 3 números rojos y 3 números azules.




La solución propuesta es la misma que, con posterioridad a mi envío, se me ocurrió. Y consiste, básicamente, en aplicar una especie de Teorema de Bolzano discreto. En otras palabras, para pasar de a (donde ) con pasos de longitud ó , necesariamente en algún momento habremos de pasar por el . Pero mirad el vídeo de la solución




De todas formas, como ya os he dicho antes, esta solución se me ocurrió cuando ya había enviado otra solución más elaborada y basada en la casuística. En ella, lo primero que hacemos es darnos cuenta que en realidad buscamos 6 números consecutivos entre los que haya 3 rojos y 3 azules. A continuación os dejo la solución que envié.

Vamos a dividir la solución en 6 casos: vamos a fijarnos en las cadenas de números del reloj del mismo color.

  • Caso 1: No podemos encontrar más de 1 número consecutivo del mismo color.
    En este caso, la única opción es que los colores sean alternativos (Rojo, Azul, Rojo, Azul...). De hecho, sólo hay 2 coloraciones posibles: O bien los Pares son Rojos y los Impares Azulos o viceversa. Así, cualesquiera 6 números consecutivos contendrían 3 rojos y 3 azules.
  • Caso 2: No podemos encontrar más de 2 números consecutivos del mismo color.
    Podemos suponer que somos capaces de encontrar 2 números consecutivos del mismo color, Rojo por ejemplo (si no es así, estamos en el caso anterior y ya estaría resuelto). Como no hay cadenas de 3 números del mismo color, antes y después de esos 2 rojos debe haber azules, es decir, tendremos la siguiente configuración A-R-R-A. Veamos 3 subcasos:
    • SubCaso a) Si antes de esa configuración hay un AZUL, tendremos A-A-R-R-A, y como no puede haber 3 consecutivos del mismo color, antes de esta configuración debe haber un Rojo, luego tendremos R-A-A-R-R-A. Y ya tendríamos 6 números consecutivos 3 de ellos rojos y 3 de ellos azules.
    • SubCaso b) Si después de esa configuración hay un AZUL, repetimos el proceso anterior y obtendríamos A-R-R-A-A-R.
    • SubCaso c) Si no ocurre ninguno de los dos subcasos anteriores, es poruqe la configuración es: R-A-R-R-A-R. Veamos ahora otros 3 subcasos:
      • SubSubCaso i) Antes de esta configuración hay un Azul: A-R-A-R-R-A-R. Los 6 primeros números de esta configuración cumplen lo pedido.
      • SubSubCaso ii) Después de esta configuración hay un Azul: R-A-R-R-A-R-A. Los 6 últimos números de ella cumplen lo pedido.
      • SubSubCaso iii) Antes y Después de esta configuración hay Rojos: R-R-A-R-R-A-R-R. Como ya tenemos los 6 rojos, eso fuerza a que los 4 azules que quedan estén juntos... lo que no es posible, ya que no hay más de 2 números consecutivos del mismo color.
  • Caso 3: No podemos encontrar más de 3 números consecutivos del mismo color.
    Como antes, podemos suponer que somos capaces de encontrar 3 números consecutivos del mismo color (si no, estaríamos en alguno de los casos anteriores). Pongamos, de nuevo, que tenemos 3 rojos consecutivos. Como no puede haber 4 consecutivos, antes y después de ellos, habrá núemros azules: A-R-R-R-A.
    Si antes (o después) de esta configuración hay un Azul, entonces ya tendríamos los 6 números consecutivos 3 rojos y 3 azules (AARRRA ó ARRRAA).
    Supongamos, entonces que antes y después hay rojos: R-A-R-R-R-A-R. Como sólo nos queda 1 rojo que colocar, seguro que Antes o Después de esta configuración hay 2 azules seguidos (supongamos que es Antes): A-A-R-A-R-R-... estos 6 números consecutivos ya piden lo pedido.
  • Caso 4: No podemos encontrar más de 4 números consecutivos del mismo color.
    Como en casos anteriores, podemos suiponer que tenemos 4 rojos, por ejemplo y que antes y después de ellos hay, al menos, un azul: A-R-R-R-R-A.
    Si antes (o después) de esta configuración hay 2 azules seguidos, ya tendríamos los 6 números consecutivos: (A-A-A-R-R-R-r-a ó a-r-R-R-R-A-A-A).
    Antes (o después) de esta configuración no pueden encontrarse 2 rojos, ya que entonces nos encontraríamos con 5 azules seguidos, lo que es imposible en este caso.
    Por lo tanto, la única opción que nos queda por ver es la siguiente R-A-R-R-R-R-A-R. Pero en este caso, ya sólo quedan números azules, así que antes de esta configuración, seguro que ha 2 azules A-A-R-A-R-R-r-r-a-r y los 6 primeros números de ésta son lso que buscábamos.
  • Caso 5: No podemos encontrar más de 5 números consecutivos del mismo color.
    Como antes, suponemos que tenemos 5 rojos consecutivos precedidos y sucedidos por sendos azules: A-R-R-R-R-R-A. Como sólo queda 1 azul po colocar, seguro que o bien Antes o bien Después de la configuración podré encontrar 2 azules seguidos (A-A-A-R-R-R-r-r-a si es antes o bien a-r-r-R-R-R-A-A-A si es después). En cualqueir caso, encontramos los 6 números consecutivos (los 6 primeros si es antes, los 6 últimos si es después).
  • Caso 6: No podemos encontrar más de 6 números consecutivos del mismo color.
    Si encvontramos 6 consecutivos, es que todos los azules están juntos y todos los rojos también. Así, seguro que encontramos 3 azules justo antes de 3 rojos A-A-A-R-R-R o vicecersa.
En fin, no es ni de lejos una solución elegante ni original ni nada de eso, pero es la que envié. En mi descargo debo decir que desde el jueves hasta prácticamente el sábado estuve con fiebre.
    Tito Eliatron Dixit

    PD: Esta entrada va a formar parte de la Edición 2.3 del Carnaval de Matemáticas cuyo anfitrión es el blog Los Matemáticos no son Gente Seria

    2 comentarios:

    1. Mi solución, a mitad de camino entre la bruta y la elegante:
      Sea un reloj coloreado arbitrariamente según las reglas.
      Tomemos la recta que separa los números {1,...6} y {7,...12}.Tendremos en cada grupo de números únicamente los siguientes casos:
      1. 3 de cada color en cada grupo. En este caso nuestra recta cumple el requisito deseado.FIN
      2. 2 de color y 4 de otro en un grupo, y 4 del pri
      3. 6 de un color en un grupo y 6 de otro color en el otro grupo. En este caso desplazamos la recta 3 posiciones y tendremos una recta que cumplirá la condición que buscamos. FIN

      Sólo falta discutir el caso 2 para resolver el problema. Cuando desplazamos la recta un lugar pueden suceder:
      2.1 Que en cada grupo salga y entre un mismo color con lo que no varía la proporción 4-2/2-4
      2.2 Que en cada grupo entre un color diferente al que sale, con lo que pasaríamos a tener un caso tipo 1 o 3 y obtendríamos la recta buscada.

      Por último nos damos cuenta que el caso 2.1 solamente se podrá dar como máximo en 4 desplazamientos de la recta inicial, ya que si en 4 ocasiones entra y sale un mismo color los 2 últimos elementos respectivos de los primeros grupos serán de distinto color por la proporción 4-2/2-4. Por tantodesplazando la recta inicial a los sumo 5 posiciones tendremos la recta deseada.
      q.e.d.
      Saludos @Gluino79

      ResponderEliminar
    2. Ahora que releo mi solución me comí unos cuantos casos... que malo es trasnoschar!!

      @Gluino79

      ResponderEliminar

    Si no comentas, Gauss se comerá una integral.
    Y, por favor, respeta a todos con tus opiniones.

    Related Posts Plugin for WordPress, Blogger...