Interesante y complicado problema este que ha planteado William Gasarch y que vi en Bit-Player vía reddit. A quien lo resuelva le esperan 17² dólares de premio y la fama eterna.
El problema genérico consiste en colorear todos los puntos de un rectángulo en n por m con cierto número de colores, sin que en su interior aparezcan rectángulos virtuales con las cuatro esquinas del mismo color (de aspecto vertical y diagonal, sin contar los inclinados). En algunos casos concretos se sabe que por ejemplo hasta los cuadrados de 16×16 es posible hacero empleando tan solo cuatro colores (como el de arriba, que mide 15×15), pero tambíen se sabe que para los de 18×18 es imposible limitándose sólo a cuatro colores (como le sucede a este de abajo, de 16×16).
El reto consiste en encontrar un cuadrado de 17×17 que pueda ser coloreado con cuatro colores sin que en su interior haya rectángulos con las cuatro esquinas del mismo color, o demostrar por qué es imposible que exista.
En la anotación de Bit-Player se explica por qué el problema dista de ser trivial: las pruebas por fuerza bruta no son suficientes porque habría que revisar 4289 casos, así que se necesita una combinación de ingenio para reducir muchos casos a un número más razonable, de forma matemáticamente demostrable, y luego probablemente comprobarlos todos uno por uno.
