Coloreando puntos

Enunciado

Es sencillo ver que por lo menos necesitamos 15 colores, ya que en una recta hay 15 puntos de corte, una por cada otra recta. Sin embargo, no es fácil ver que bastan esos 15 colores.

Empezamos por un ejemplo más sencillo. Si sólo tenemos dos rectas, sólo hay un punto, por lo que sólo es necesario un color (qué ejemplo más tonto).

Vamos a complicarlo más. Si tenemos tres rectas, se cortan en tres puntos. En principio, en cada recta hay sólo dos puntos, pero con dos colores no habría suficiente, pues el tercer punto está en las dos rectas. Hacen falta tres colores. Aquí vemos que con una cantidad impar de recta parece que la cosa no funciona bien.

Si usamos cuatro rectas, puesto que cada una corta a todas las demás, el número de puntos es de 6. En cada recta hay tres puntos de corte, y necesitamos, como mínimo, tres colores. Observamos que una vez que pintamos con los tres colores los puntos de una recta, otra de las rectas que pase puede usar los dos que son de distinto color a los que ha utilizado antes, y una tercera pasa por la primera y la segunda, de forma que bastará escoger el tercer color que no ha usado todavía. La cuarta recta se puede comprobar que pasa exactamente por tres puntos de distinto color. Observa que cada color se usa exactamente dos veces. Y también que cada vez que pintas un punto de un color, prohíbes que ningún otro punto de esa recta se vuelva a pintar de ese color, es como si los quitases. Y si quitas los cuatro puntos de las dos rectas, y el que has pintado, sólo queda otro, que es el otro que pintas del mismo color.

En realidad, basta ver esto como una tabla en la que aparecen los números de las rectas en filas y columnas, y en cada cruce aparece un número de color, de forma que no coinciden dos en la misma fila y en la misma columna, y que son simétricos (porque en realidad el punto que pertenece a dos rectas es el mismo, en la fila y en la columna). Esta circunstancia me recordó a un calendario de enfrentamientos deportivos, en los que un equipo se enfrenta a todos, y no hay una jornadas (colores) repetida en ninguno de los equipos (rectas). Hay un truco muy sencillo para hacer un calendario así.

Tomemos el primer color. Lo ponemos en el cruce de la primera con la última recta, la segunda con la tercera, y así sucesivamente. Ahora el segundo. Lo ponemos en la primera con la penúltima, la segunda con la antepenúltima y así sucesivamente. La que queda libre en medio, miramos dónde corta con la última, y también la pintamos de ese color. Para el tercer color, unimos primera con antepenúltima, segunda con la anterior de la antepenúltima, y así sucesivamente. La penúltima, la unimos con la última. Para el cuarto color, unimos primera con la anterior de la antepenúltima, la segunda con la anterior, y así. La del centro, la unimos a la última, y la antepenúltima, a la penúltima.

Si no lo has entendido, mira la tabla que pongo a continuación para los 16 colores, y verás como todo cuadra (fíjate, sobre todo, en la última fila y columna).

	15	14	13	12	11	10	9	8	7	6	5	4	3	2	1
15		13	12	11	10	9	8	7	6	5	4	3	2	1	14
14	13		11	10	9	8	7	6	5	4	3	2	1	15	12
13	12	11		9	8	7	6	5	4	3	2	1	15	14	10
12	11	10	9		7	6	5	4	3	2	1	15	14	13	8
11	10	9	8	7		5	4	3	2	1	15	14	13	12	6
10	9	8	7	6	5		3	2	1	15	14	13	12	11	4
9	8	7	6	5	4	3		1	15	14	13	12	11	10	2
8	7	6	5	4	3	2	1		14	13	12	11	10	9	15
7	6	5	4	3	2	1	15	14		12	11	10	9	8	13
6	5	4	3	2	1	15	14	13	12		10	9	8	7	11
5	4	3	2	1	15	14	13	12	11	10		8	7	6	9
4	3	2	1	15	14	13	12	11	10	9	8		6	5	7
3	2	1	15	14	13	12	11	10	9	8	7	6		4	5
2	1	15	14	13	12	11	10	9	8	7	6	5	4		3
1	14	12	10	8	6	4	2	15	13	11	9	7	5	3

Para quince rectas, o cualquier número impar, sin embargo, seguimos necesitando quince colores, ya que el número de cruces es 105, y si hubiese posibilidad de pintarlos con 14 colores, uno de ellos debería colorear a más de 7 colores (7*14 = 98), y no hay tantos pares de rectas distintos, es decir, una de las rectas debe pasar por dos intersecciones de un mismo color (piensa en los equipos y las jornadas, uno de los equipos debería jugar con dos rivales la misma jornada).