[justus0jonas]

Mit Computerhilfe haben zwei deutsche Forscher ein mit Sudoku verwandtes Rätsel geknackt: Sie verteilten vier Farben über eine quadratische Fläche bestehend aus 17 mal 17 Feldern. Dabei durfte kein Rechteck mit vier gleichfarbigen Eckpunkten entstehen.

Lösung des Vierfarbenrätsels: Drei Ecken dürft ihr bilden - SPIEGEL ONLINE - Nachrichten - Wissenschaft

Meiner Meinung nach - zumindest auf den ersten Blick - sind im Beitrag einige quantitative Fehler enthalten, oder? So beträgt die Anzahl der zu untersuchenden Rechtecke nicht (17 über 2)^2, denn durch die freie Wählbarkeit der - OE - horizontalen Grundseite mit (17 über 2) Möglichkeiten ist bereits die Länge der vertikalen Seite festgelegt, da es sich um Quadrate handeln soll - die Zahl der zu untersuchenden Rechtecke müsste demnach kleiner sein.

[phboerker]

Das Problem ist unzureichend definiert: "Bei einem beliebig ausgewählten Rechteck aus diesem 17x17-Quadrat, zum Beispiel einem der Größe vier mal fünf Felder, dürfen die vier Eckpunkte nicht sämtlich von derselben Farbe sein"

Ein solches "beliebiges Rechteck" kann ich für die 18x18 Lösung leicht präsentieren:

Matherätsel geknackt: Verrücktes Sudoku mit vier Farben - SPIEGEL ONLINE - Nachrichten - Wissenschaft

Man betrachte die gelb-orangen Farbpunkte an den Koordinaten (5, 12), (4, 13), (8,15) und (7,16). Wenn das kein Rechteck mit gleichfarbigen Eckpunkten ist, weiß ich auch nicht. Das Problem oder vielmehr seine Lösung ist also auf Rechtecke, die parallele Kanten zu dem Feld aufweisen, beschränkt.

[heikoprasse]

Meiner Meinung nach - zumindest auf den ersten Blick - sind im Beitrag einige quantitative Fehler enthalten, oder? So beträgt die Anzahl der zu untersuchenden Rechtecke nicht (17 über 2)^2, denn durch die freie Wählbarkeit der - OE - horizontalen Grundseite mit (17 über 2) Möglichkeiten ist bereits die Länge der vertikalen Seite festgelegt, da es sich um Quadrate handeln soll - die Zahl der zu untersuchenden Rechtecke müsste demnach kleiner sein.

Ich verstehe Sie nicht ganz - gehen Sie jetzt von der Bildung von allgemeinen Rechtecken oder von Quadraten aus? Beides wird in ihrem Kommentar sogar im gleichen Satz angenommen.
Jedenfalls sollen laut Artikel + Bebilderung ausdrücklich allgemeine Rechtecke gebildet werden, und damit ist die vertikale Seite keineswegs durch die Wahl der horizontalen festgelegt.
Quadratisch ist nur die Grundfläche (17*17), auf der die Rechtecke gewählt werden, das Quadrat findet sich nur in der Quadrierung des Binomialkeffizienten wieder.

[horstma]

Ich bin zwar kein Mathematiker, hatte aber im Rahmen meines E-Technik-Studiums zumindest ein paar Semester Vorlesungen. Was ich mich frage: Warum ist es nicht möglich, die Bedingungen für die Lösung in ein irgendwie geartetes Gleichungssystem zu packen? Natürlich wäre dieses Gleichungssystem sehr groß. Vermutlich eine Gleichung für jedes Rechteck, das in den 17er oder 18er Würfel passt, und die ausdrückt, daß die 4 Eckpunkte keine gleichen Werte aufweisen. Die Lösung dieses Systems würde zwar auch vermutlich sehr umfangreich sein, aber es wäre ein systematischer Ansatz, der nicht auf probieren beruht. Vielleicht kann ein Mathematiker dazu etwas sagen.

[swenlechte]

Im Original ist die Aufgabe diesbezueglich zureichend definiert.

Das Problem ist unzureichend definiert: "Bei einem beliebig ausgewählten Rechteck aus diesem 17x17-Quadrat, zum Beispiel einem der Größe vier mal fünf Felder, dürfen die vier Eckpunkte nicht sämtlich von derselben Farbe sein"

Ein solches "beliebiges Rechteck" kann ich für die 18x18 Lösung leicht präsentieren:

Matherätsel geknackt: Verrücktes Sudoku mit vier Farben - SPIEGEL ONLINE - Nachrichten - Wissenschaft

Man betrachte die gelb-orangen Farbpunkte an den Koordinaten (5, 12), (4, 13), (8,15) und (7,16). Wenn das kein Rechteck mit gleichfarbigen Eckpunkten ist, weiß ich auch nicht. Das Problem oder vielmehr seine Lösung ist also auf Rechtecke, die parallele Kanten zu dem Feld aufweisen, beschränkt.

[Pat-Riot]

Meiner Meinung nach - zumindest auf den ersten Blick - sind im Beitrag einige quantitative Fehler enthalten, oder? So beträgt die Anzahl der zu untersuchenden Rechtecke nicht (17 über 2)^2, denn durch die freie Wählbarkeit der - OE - horizontalen Grundseite mit (17 über 2) Möglichkeiten ist bereits die Länge der vertikalen Seite festgelegt, da es sich um Quadrate handeln soll - die Zahl der zu untersuchenden Rechtecke müsste demnach kleiner sein.

Quadrate sind stets Rechtecke. Umgekehrt nur in bestimmten Fällen.

[genie_der_genies]

Im Original ist die Aufgabe diesbezueglich zureichend definiert.

wieso gibt es keine Lösung für 19x19 oder grösser ?
Das wäre doch nun wirklich mal interessant zu wissen ...

[nikto]

Ich bin zwar kein Mathematiker, hatte aber im Rahmen meines E-Technik-Studiums zumindest ein paar Semester Vorlesungen. Was ich mich frage: Warum ist es nicht möglich, die Bedingungen für die Lösung in ein irgendwie geartetes Gleichungssystem zu packen?

Das wäre ein Gleichungssystem mit 189 Variablen und 110.976 Gleichungen. Dadurch hätte man auch nichts gewonnen. Ich gehe davon aus, dass das einer der ersten Ansätze war, da es für solche Probleme ausgefeilte Algorithmen gibt.

wieso gibt es keine Lösung für 19x19 oder grösser ?
Das wäre doch nun wirklich mal interessant zu wissen ...

Das folgt aus den bekannten aussagen zu OBS4. Schau dir dazu doch die Aufgabenstellung an: Computational Complexity: The 17x17 challenge. Worth $289.00. This is not a joke.

[solarforscher]

wieso gibt es keine Lösung für 19x19 oder grösser ?
Das wäre doch nun wirklich mal interessant zu wissen ...

Es kommen wohl zu viele neue Möglichkeiten hinzu die Rechtecke zu bilden als Färbungsmöglichkeiten. Beispielsweise hat die 19x19 Fläche vier 18x18 Untermengen. Wenn es eine Lösung zur 19x19 Fläche gäbe muss es mindestens vier verschiedene (a, b, c, d) 18x18 Lösungen geben würde ich mal annehmen. Wenn es eine weitere 19x19 Lösung gäbe würde die vermutlich aus (teilweise) neuen 18x18 Lösungen bestehen.
Ist natürlich noch kein mathematischer Beweise, aber intuitiv ist verständlich dass sich mit größer werdendem n bei nxn die Anzahl der Lösungen deutlich reduziert und bei 19x19 ist wohl Schluss.

Dennoch wäre der korrekte Beweis mal interessant zu sehen.