Mindestmenge an Farben, die ein gleichseitiges, gleichmäßig gefärbtes Unterdreieck verhindert

In der Bundeswettberweb Infomatik 2010/2011 gab es ein interessantes Problem:

Finden Sie für festes ein Minimum k und eine Abbildung φ : { ( i , j ) | i ≤ j ≤ n } → { 1 , … , k } , so dass es kein Tripel ( i , j ) , ( i + l , j ) , ( i + l , j + l ) mit φ ( $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)$

Wir suchen nämlich nach der minimalen Menge an Farben für ein Dreieck, sodass es kein gleichförmiges gleichförmiges Unterdreieck gibt.

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

Tatsächlich fragten sie nach einem einigermaßen kleinen für n = 1000 und stellten in der Lösung fest, dass ein gieriger Ansatz eine Färbung mit 27 Farben für n = 1000 ergibt , die durch Randomisierung der Farben bis a auf 15 reduziert werden kann Es wurde eine gültige Lösung gefunden.$k$$n=1000$$27$$n=1000$$15$

Ich interessiere mich für exakte Lösungen (für kleinere ). Die Lösung sagt , dass Rückzieher ergeben , dass 2 Farben für ausreichend sind , n ∈ { 2 , 3 , 4 } und 3 sind für eine ausreichende 5 ≤ n ≤ 17 , wobei Rückzieher langsam für schon richtig sind n = 17 .$n$$2$$n\in\{2,3,4\}$$3$$5\leq n \leq 17$$n=17$

Zuerst habe ich versucht, eine ILP-Formulierung und Gurobi zu verwenden, um einige Ergebnisse für , aber es war zu langsam (bereits für n = 17 ). Dann habe ich einen SAT-Solver verwendet , weil mir aufgefallen ist, dass es eine einfache Formulierung als SAT-Instanz gibt.$n>17$$n=17$

Mit diesem Ansatz konnte ich innerhalb von 10 Minuten eine Lösung mit Farben für n = 18 generieren :$3$$n=18$$10$

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

Aber um zu entscheiden, ob Farben für n = 19 ausreichen , ist es schon zu langsam. Gibt es einen anderen Ansatz, der genaue Lösungen für n ≥ 19 liefert ? Natürlich können wir keinen Polynomalgorithmus erwarten.$3$$n=19$$n \geq 19$

Nur ein erweiterter Kommentar:

Schauen Sie sich die Vorgehensweise von Steinbach und Posthoff an, um die 4-farbige Darstellung eines 18x18- (und 12x21-) Rasters ohne monochromatische Rechtecke zu ermitteln :

Bernd Steinbach und Christian Posthoff, Lösung des letzten offenen, vierfarbigen, rechteckfreien Gitters, ein äußerst komplexes mehrwertiges Problem . In Proceedings of the 2013 IEEE 43. Internationales Symposium über mehrwertige Logik (ISMVL '13)

$c$$n \times m$

Nur eine Randnotiz: Ich habe wochenlang CPU-Zyklen mit dem einfarbigen, rechteckfreien 4-Farben-Problem verbracht, aber mit einem falschen Teilergebnis (einer falschen vorherigen Analyse, die die Anzahl der möglichen 1-Farben-Unterkonfigurationen einschränkte) begonnen und es verwendet der STP-Beschränkungslöser ; Sie können große Verbesserungen erzielen, wenn Sie Einschränkungen hinzufügen, die Symmetrien aufheben (z. B. eine Anordnung der Farbe einer Seite des Dreiecks), und versuchen, die möglichen Konfigurationen mit nur einer Farbe zu analysieren.

EDIT: Dies ist das Ergebnis eines STP-Programms für n = 19 (~ 1 min.)

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

$n=19$$n=23$

$n=22$

Vielen Dank an Marzio, der das Bild erstellt und mich über das Problem informiert hat! :-)