UN RELOJ DE DOS COLORES

Veamos aunque un poco tarde el reto de esta semana:

Elisa Lorenzo García, estudiante de doctorado de la Universidad Politécnica de Cataluña, plantea el cuarto desafío matemático de EL PAÍS. Envía tu solución al correo problemamatematicas@elpais.es hasta las 00.00 horas del martes 12 de abril. 

Nota: Para evitar confusiones y permitir también la participación de los lectores sordos, incluimos aquí el enunciado del problema por escrito.

Se considera un reloj con sus 12 números en torno a una circunferencia: 1, 2, ..., 12. Se pintan de azul o rojo cada uno de los 12 números de modo que haya seis pintados de azul y seis de rojo. El problema consiste en demostrar, que, independientemente del orden en que se hayan pintado, siempre existirá una posible recta que divida al reloj por la mitad, dejando en cada lado seis números, tres pintados de rojo y tres pintados de azul.

SOLUCIÓN:

La solución enviada (buena o mala) se publicará una vez finalice el plazo de envío. No obstante comentar una serie de cuestiones.

En primer lugar que ha sido el problema de los cuatro que más me ha costado resolver, pues en principio se puede abordar de un montón de formas diferentes, de las cuales yo he abordado casi todas, vemos:

a) En un principio pensé que se podría asimilar el reloj a un grafo, y que quizás podríamos crear dos cadenas, una con cada color, aplicando el "Método de la Cadena" propuesto por Lee y Preparata en 1978. Demostrando que la intersección de dos cadenas siempre forma una recta. Pero reconozco que no he sido capaz.

b) A continuación con la misma idea de representar el problema por medio de grafos, me acordé de la Teoría de Ramsey, y su Teorema de la Amistad. En este caso también tenemos un grafo hamiltoniano K6,6, y mediante el Teorema de Kuratowski, pasar a un grafo K3,3 y aplicar Ramsey. Pero también me resultaba bastante complicado.

c) También como no he intentado resolverlo por Bolzano, intentando aplicar su Teorema, para matemática discreta, aunque sabemos que sólo es válido para funciones continuas. El problema se puede resolver de forma general (para 2n números, n de cada color). Si partiendo de una distribución cualquiera y de una recta cualquiera, en uno de los lados tienes un nº de números de cada color, ¿cuantos números de cada color habrá al otro lado de la recta?. ¿Se puede asegurar entonces que hay una posición de la recta en la cual se cumple el enunciado?. De hecho he realizado una demostración, pero he de reconocer que no estaba seguro de que no contuviera un error.

d) Por supuesto lo intente por combinatoria, pero resultaba aún más complicado. Aunque al final creo haber encontrado una posible solución aplicando el Principio del Palomar. Pero aún así no me convencía del todo.

e) Aplique simetrías y geometría, dividiendo la circunferencia en 4 cuadrantes, pero salían demasiados casos (aunque al final creo haber descubierto que sólo existen 10 distintos, salvo simetrías y reflexiones)

f) He leído que hay quién lo ha demostrado aplicando la versión discreta del Teorema de Borsuk-Ulam en dimensión 1, pero me sigue pareciendo complicar las cosas.

e)  Al final he hecho una mezcla de alguna de las cosas anteriores y me ha salido algo bastantes sencillo. Aunque también se me ocurrió hacerlo por sucesiones, etc.

SOLUCIÓN ENVIADA:

Dividimos el Reloj en dos partes iguales con una recta aleatoria $$r$$. En cada una de las partes tendremos 6 números. Llamamos $$S$$ a una de las partes e $$I$$ a la otra. Así mismo llamamos $$R$$ al número de números de color rojo de $$S$$ y $$R_1$$ al número de números de color rojo de $$I$$. Igualmente llamamos $$A$$ al número de números de color Azul de $$S$$ y $$A_1$$ al número de números de color azul de $$I$$.

Se cumple que:

$$A+R=6$$

$$A_1+R_1=6$$

$$A+A_1=6$$

$$R+R_1=6$$

En $$S$$ encontraremos una distribución del tipo $$A-R$$, teniendo en $$I$$ una distribución complementaria $$A_1-R_1$$ para poder cumplir las ecuaciones anteriores. Veamos la siguiente tabla:

$$\boxed{\begin{matrix}{A-R}&{A_1-R_1}\\{6-0}&{0-6}\\{5-1}&{1-5}\\{4-2}&{2-4}\\{3-3}&{3-3}\\{2-4}&{4-2}\\{1-5}&{5-1}\\{0-6}&{6-0}\end{matrix}}$$

Consideremos ahora girar la recta $$r$$ un ángulo de 30º, y pasar de $$S$$ a $$S_1$$ (lo que equivale a girar la recta un número del reloj). Donde $$S\cap S_1=\textrm {5 elementos}$$. Entonces en $$S_1$$ podemos tener dos casos:

A) Que obtengamos la misma distribución (si al girar obtenemos un número del mismo color que el que hemos perdido. Ejemplo: si tengo  4-2, y al girar perdemos 1 rojo, pero por el otro lado ganamos 1 rojo, seguimos teniendo 4-2).

B) Que obtengamos la distribución inmediatamente superior o inmediatamente inferior (si al girar conseguimos un número de un color distinto al que perdemos. Ejemplo: si tengo 4-2, y al girar gano 1 azul y pierdo 1 rojo, paso a 5-1; pero si gano 1 rojo y pierdo 1 azul paso a 3-3).

Ahora bien si giramos $$r$$ 180º, entonces pasamos de $$S$$ a $$I$$, puesto que sabemos que $$I$$ tiene distribución complementaria a $$S$$, y pasaremos de las distribución $$A-R$$ a la distribución $$A_1-R_1$$.

Bien si tenemos una distribución tipo 3-3 no tendremos que hacer nada, pues es la distribución buscada. 

Si por el contrario tenemos cualquiera de las otras distribuciones, con sólo girar 6 veces en un mismo sentido (180º) hemos comprobado que pasamos de una distribución a su complementaria, por lo que como en cada giro de 30º sólo  podemos tener uno de los casos anteriores (o la misma distribución o la inmediatamente superior o inferior), obligatoriamente pasaremos por la distribución 3-3 buscada. 

NOTA: Podemos asegurar que como mínimo existe una recta que divide a la circunferencia en 2 partes con tres números pintados de rojo y tres números pintados de azul. Pero puede existir más de una recta. De hecho podemos tener hasta 12 rectas que será el caso en que los números pares estén de un color y los impares de otro, elijamos la recta que elijamos  tendremos dos mitades que cumplen la condición. Cuanto más mezclados estén los números más rectas existirán.

NOTA 2: Una vez encontrada la recta adecuada con distribución 3-3, siempre podremos dibujar dos triángulos que unan cada uno de los números del mismo color, un triángulo de color rojo,  cuyos vértices son los números de color rojo, y un triángulo de color azul, cuyos vértices son de color azul. Por combinatoria sabemos que:  

$$C_n^p=\displaystyle\binom{n}{p}=\frac{n!}{(n-p)!\cdot{p!}}$$

Vamos a ver cuántos triángulos distintos podemos cosntruir con una de las semicircunferencias:

$$C_6^3=\displaystyle\binom{6}{3}=\frac{6!}{(6-3)!\cdot{3!}}=20$$

Luego existen sólo 20 posibles triángulos distintos, es decir existen sólo 20 soluciones distintas para cada color (y sólo 10 si no tenemos en cuenta el color, sino que simplemente ambos triángulos son de dos colores diferentes, ya que al dibujar uno de los triángulos, necesariamente quedará definido el segundo triángulo con los tres vértices que quedan, triángulo que a su vez será otra de las soluciones buscadas). Todas las demás soluciones serán simetrías o reflexiones de las vistas. Veamos las 10 soluciones posibles ($$x$$ representa un color y $$\circ{}$$ él otro color):

$$\boxed{\begin{matrix}{\circ{}}&{\circ{}}&{x}&{x}&{x}&{\circ{}}\\{\circ{}}&{x}&{\circ{}}&{x}&{x}&{\circ{}}\\{\circ{}}&{x}&{x}&{\circ{}}&{x}&{\circ{}}\\{\circ{}}&{x}&{x}&{x}&{\circ{}}&{\circ{}}\\{x}&{\circ{}}&{\circ{}}&{x}&{x}&{\circ{}}\\{x}&{\circ{}}&{x}&{\circ{}}&{x}&{\circ{}}\\{x}&{\circ{}}&{x}&{x}&{\circ{}}&{\circ{}}\\{x}&{x}&{\circ{}}&{\circ{}}&{x}&{\circ{}}\\{x}&{x}&{\circ{}}&{x}&{\circ{}}&{\circ{}}\\{x}&{x}&{x}&{\circ{}}&{\circ{}}&{\circ{}}\end{matrix}}$$

SOLUCIÓN DE "EL PAÍS": Siempre hay una Recta

Publicado por Gogely the Great