Cantidad mínima de colores que previenen un subtriángulo equilátero de color uniforme

En el Bundeswettberweb Infomatik 2010/2011, hubo un problema interesante:

Para fijo , encuentre un mínimo y un mapa , de modo que no haya triple con .k φ : { ( i , j ) | i ≤ j ≤ n } → { 1 , … , k } ( i , j ) , ( i + l , j ) , ( i + l , j + l ) φ ( i , j ) = φ ( i + l $n$$k$$\varphi: \{(i,j)|i\leq j \leq n\}\rightarrow \{1,\ldots,k\}$$(i,j),(i+l,j),(i+l,j+l)$$\varphi(i,j)=\varphi(i+l,j)=\varphi(i+l,j+l)$

Es decir, estamos buscando la cantidad mínima de colores para un triángulo, de modo que no haya un subtriángulo equilátero de color uniforme (la siguiente imagen muestra una coloración no válida ya que los vértices resaltados forman un subtriángulo equilátero de color uniforme):

$\ \ \ ~~~~~~~~~~~~~~~~~~~~~~~~~~~$

De hecho, pidieron una razonablemente pequeña para y en la solución (escrita en alemán) notaron que un enfoque codicioso produce una coloración con colores para , que puede reducirse a aleatorizando colores hasta que Se encuentra una solución válida.$k$$n=1000$$27$$n=1000$$15$

Estoy interesado en soluciones exactas (para menor ). La solución dice que el retroceso produce que colores son suficientes para y son suficientes para , donde el retroceso ya es realmente lento para .$n$$2$$n\in\{2,3,4\}$$3$$5\leq n \leq 17$$n=17$

Primero intenté usar una formulación de ILP y Gurobi para obtener algunos resultados para , pero fue demasiado lento (ya para ). Luego usé un solucionador SAT , porque noté que hay una formulación directa como una instancia SAT.$n>17$$n=17$

Con ese enfoque pude generar una solución con colores para en minutos:$3$$n=18$$10$

$\ \ \ ~~~~~~~~~~~~~~~~~~~~~~~~~~~$

Pero para decidir si colores son suficientes para ya es demasiado lento. ¿Hay algún enfoque diferente que brinde soluciones exactas para ? Ciertamente, no podemos esperar un algoritmo polinomial.n = 19 n ≥ $3$$n=19$$n \geq 19$

Solo un comentario extendido:

Puede echar un vistazo al enfoque utilizado por Steinbach y Posthoff para encontrar el color 4 de una cuadrícula de 18x18 (y 12x21) sin rectángulos monocromáticos :

Bernd Steinbach y Christian Posthoff, solución de la última cuadrícula abierta libre de rectángulos de cuatro colores, un problema extremadamente complejo de valores múltiples . En las Actas del 43º Simposio Internacional IEEE 2013 sobre lógica de valores múltiples (ISMVL '13)

$c$$n \times m$

Solo una nota al margen: pasé semanas de ciclos de CPU en el problema monocromático de 4 colores sin rectángulo, pero comencé con un resultado parcial incorrecto (un análisis previo incorrecto que restringió el número de posibles subconfiguraciones de 1 color) y utilicé el solucionador de restricciones STP ; puede lograr grandes mejoras si agrega restricciones que rompen las simetrías (por ejemplo, un orden en el color de un lado del triángulo) e intenta hacer un análisis de las configuraciones posibles usando solo 1 color.

EDITAR: este es el resultado de un programa STP para n = 19 (~ 1 min.)

$n \leq 22$$n=22$$n=23$$n=23$$n=23$

$n=19$$n=23$

$n=22$

¡Muchas gracias a Marzio por generar la imagen y por informarme sobre el problema! :-)