Un triángulo de tres colores

Enunciado

Como siempre con este tipo de problemas, debemos empezar trabajando con casos concretos y sencillos, para avanzar hacia una generalización.

Si tenemos tres puntos, cada uno de un color, y cada uno conectado con dos, está claro que están totalmente conectados, por lo que está claro que forman un triángulo de tres colores.

Supongamos que tenemos seis puntos, pintados a pares de colores. Cada punto está unido con tres de distinto color, de forma que podemos garantizar que uno de los tres es del tercer color. Tomemos un punto cualquiera. Dos de sus uniones serán con un color común, supongamos que es el color A, y otro será con el color B. Éste último punto estará unido a algún punto de color A, ya que está unido a tres puntos, y no todos pueden ser de color C. Como el primer punto está unido a los dos de color A, también está unido a éste, por lo que forman un triángulo.

Vamos al tercer ejemplo, que puede ser el más complicado y el que aclare el método general. Tenemos nueve puntos, tres de cada color, y todos están unidos a cuatro de distinto color. Si uno de ellos está unido a tres del mismo color, repetiríamos el razonamiento anterior, pero puede ocurrir que ninguno está unido a tres de un mismo color. En ese caso, todos estarán unidos a dos de un color y dos de otro. Tomemos un punto P de color C, unido a dos A y dos B. Supongamos que Q es uno de los puntos de color B unido a P. Puesto que está unido a dos de color A, y sólo hay tres, uno de los de color A que está unido a P también estará unido a Q, ya que cada uno está unido a dos (y dos y dos es mayor que 3). Este punto forma un triángulo de tres colores junto a P y Q.

No sé si has entendido el razonamiento, pero la clave está en buscar el punto que más uniones de un mismo color tiene, para forzar la situación en uno de los puntos en minoría.

Vamos entonces con el caso general. Supongamos que tenemos 3n puntos, n de color azul, n de color blanco y n de color negro. Todos ellos están unidos a exactamente n + 1 puntos de color distinto al suyo.

Supongamos que anotamos de cada punto la mayor cantidad de puntos de un mismo color que están unidos a él. Como hay un número finito de puntos, uno de estos alcanzará el máximo (puede que haya varios). Supongamos que P es un punto de color A unido a k puntos de color B, y no hay ningún punto unido a más de k puntos de otro color. Evidentemente, el número de puntos de color C unidos a P será n - k + 1, y será menor que k. Y mayor o igual a 1, por lo que al menos hay uno. Ahora, de los n - k + 1 puntos escogemos uno llamado Q.

El punto Q está unido a t puntos de color A, pero seguro que t será menor o igual que k. Y el número de puntos de color B al que estará unido será n - t + 1, que es mayor o igual que n - k + 1 por la misma razón. Ahora bien, n - t + 1 + k = n + 1 + (k - t), que es mayor o igual que n + 1, es decir, mayor que n. Por eso, hay un punto que está unido a la vez a P (k puntos) y a Q (n - t + 1 puntos). Ese punto forma con P y con Q un triángulo del tipo buscado.