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
    Related Posts Plugin for WordPress, Blogger...