Quantité minimale de couleurs empêchant un sous-triangle équilatéral uniformément coloré

dans le Bundeswettberweb Infomatik 2010/2011, il y avait un problème intéressant:

Pour fixe , trouver un k minimal et une carte φ : { ( i , j ) | i ≤ j ≤ n } → { 1 , … , k } , de sorte qu'il n'y a pas de triple ( i , j ) , ( i + l , j ) , ( i + l , j + l ) avec φ ( $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)$

À savoir, nous recherchons la quantité minimale de couleurs pour un triangle, de sorte qu'il n'y ait pas de sous-triangle équilatéral de couleur uniforme (l'image suivante montre une coloration invalide car les sommets en surbrillance forment un sous-triangle équilatéral de couleur uniforme):

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

En fait, ils ont demandé un raisonnablement petit pour n = 1000 et dans la solution (écrite en allemand), ils ont noté qu'une approche gourmande donne une coloration à 27 couleurs pour n = 1000 , qui peut être réduite à $k$$n=1000$$27$$n=1000$$15$ en randomisant les couleurs jusqu'à ce qu'un une solution valide est trouvée.

Je m'intéresse aux solutions exactes (pour les petits ). La solution dit que le retour arrière donne 2 couleurs suffisantes pour n ∈ { 2 , 3 , 4 } et 3 sont suffisantes pour 5 ≤ n ≤ 17 , où le retour arrière est déjà très lent pour n = $n$$2$$n\in\{2,3,4\}$$3$$5\leq n \leq 17$$n=17$ .

J'ai d'abord essayé d'utiliser une formulation ILP et Gurobi pour obtenir des résultats pour , mais c'était trop lent (déjà pour n = 17 ). Ensuite, j'ai utilisé un solveur SAT , car j'ai remarqué qu'il existe une formulation simple en tant qu'instance SAT.$n>17$$n=17$

Avec cette approche, j'ai pu générer une solution avec couleurs pour n = 18 en 10 minutes:$3$$n=18$$10$

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

Mais décider si couleurs suffisent pour n = 19 c'est déjà trop lent. Existe-t-il une approche différente qui donne des solutions exactes pour n ≥ 19 ? Nous ne pouvons certainement pas nous attendre à un algorithme polynomial.$3$$n=19$$n \geq 19$

Juste un commentaire étendu:

Vous pouvez jeter un œil à l'approche utilisée par Steinbach et Posthoff pour trouver la quadri -coloration d'une grille 18x18 (et 12x21) sans rectangles monochromes :

Bernd Steinbach et Christian Posthoff, solution de la dernière grille quadrangulaire ouverte sans rectangle, un problème à valeurs multiples extrêmement complexe . Dans les actes du 43e Symposium international IEEE 2013 sur la logique à valeurs multiples (ISMVL '13)

$c$$n \times m$

Juste une remarque: j'ai passé des semaines de cycles CPU sur le problème de coloration monochrome sans rectangle, mais je suis parti d'un mauvais résultat partiel (une mauvaise analyse précédente qui limitait le nombre de sous-configurations 1 couleur possibles) et j'ai utilisé le solveur de contraintes STP ; vous pouvez obtenir de grandes améliorations si vous ajoutez des contraintes qui cassent les symétries (par exemple un ordre sur la coloration d'un côté du triangle) et essayez de faire une analyse des configurations possibles en utilisant seulement 1 couleur.

EDIT: c'est le résultat d'un programme STP pour n = 19 (~ 1 min.)

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

$n=19$$n=23$

$n=22$

Un grand merci à Marzio pour avoir généré l'image et pour m'avoir informé du problème! :-)