23: Mondrian

  • Hier hatte man schnell Gebiet 18 als verdächtig ausgemacht, da der "Nachbarring" (die Nachbarn bilden einen Ring um Gebiet 18) ungeradzahlige Anzahl hat (=5) und damit nicht abwechselnd koloriert werden kann.

    Da aber das ganze Gebiet die Fläche 19x11=209 hat, kann Gebiet 18 nicht die Antwort sein, da 209-4=205 nicht durch drei teilbar ist (4 ist die Fläche von Gebiet 18).

    Also ist das gesuchte Gebiet eines der Nachbargebiete und man stellt fest, dass von den Nachbarn lediglich Gebiet 7 infrage kommt 209-5=204.

    Damit war die Bedingung, dass die Farben außer schwarz jeweils die gleiche Fläche abdecken, sehr hilfreich.

  • Hier hatte man schnell Gebiet 18 als verdächtig ausgemacht, da der "Nachbarring" (die Nachbarn bilden einen Ring um Gebiet 18) ungeradzahlige Anzahl hat (=5) und damit nicht abwechselnd koloriert werden kann.


    Das haut als Logik nicht hin, denn dann wäre beispielsweise auch Gebiet 30 in gleicher Weise verdächtig (7 derartige "Nachbarn"). Man muss hier beachten, dass durch die Berührung nur in der Diagonale prinzipiell die Gebiete 18 und 6 gleich gefärbt sein dürfen. Somit wäre eine Färbung mit nur 3 Farben dort durchaus denkbar: 7+22, 17+19, 6+18


    Der Widerspruch kann sich also erst in größerem Kontext ergeben.

  • prinzipiell die Gebiete 18 und 6 gleich gefärbt sein dürfen

    Oha, hatte tatsächlich Gebiet 6 fälschlicherweise auch als Nachbarn interpretiert...:| Man kann die simple Idee offenbar nicht retten, da es so ein Gebiet mit echtem ungeradzahligem Nachbarring wohl nicht gibt... :rolleyes:    (doch zufällig stimmte die Lösung)

  • Ich hab einfach versucht, das Bild mit 3 Farben zu färben. Bei nur 3 Farben ist bei Punkten, an denen sich 3 (aber nicht 4, wegen Diagonalen) Gebiete berühren, sofort klar, dass sie alle unterschiedlich gefärbt werden müssen - in anderen Worten, wenn 2 Gebiete bereits gefärbt sind, ist die des dritten Gebietes auch klar. Also hab ich Gebiete 1 und 2 eingefärbt und sämtliche anderen Farben haben sich aus der Regel eindeutig ergeben: [IMG:https://i.imgur.com/tVGVrEP.png]

    Gebiete 6 und 7 sind die einzigen Nachbarsgebiete mit der gleichen Farbe, also muss eines der beiden Gebiete das schwarze sein. Und nur das Schwärzen von Gebiet 7 sorgt dafür, dass es in jeder der 3 Farben gleich viele Gebiete eingefärbt sind.

  • Es reicht auch schon, wenn man versucht, 6, 7, 11, 17, 18, 19 und 22 mit 3 Farben einzufärben. Hat 22 eine Farbe, müssen 11, 17, 18 und 19 abwechselnd die 2 anderen Farben haben. Es grenzt aber 6 an 11 und 17 und 7 an 18 und 19, sodass beide die Farbe von 22 haben müssen, aber beide sind Nachbarn, Widerspruch. Dabei ist 7 das einzige der Gebiete, dessen Größe kongruent zu 11*19 modulo 3 ist.

  • Bin ähnlich vorgegangen wie Blackheart, habe aber die unschöne Geometrie in einen Graphen überführt und diesen dann so eingefärbt, dass alle direkten Nachbarn unterschiedliche Farben haben. Startet man bei Feld 1 und 2 mit untershiedlichen Farben und färbt dann den Graphen durch, gibt es eindeutig bei Feld 7 einen Fehler -> dies muss das schwarze Feld sein.

    Der Hinweis das die gefärbten Gebiete gleich groß sind, ist völlig unerheblich und wäre nur nötig gewesen, wenn die Farbe von Gebiet 7 nicht mit der seiner Nachbarn 6 und 8 kollidiert wäre, also der Graph prinzipiell mit 3 Farben färbbar gewesen wäre.

  • Der Hinweis das die gefärbten Gebiete gleich groß sind, ist völlig unerheblich und wäre nur nötig gewesen, wenn die Farbe von Gebiet 7 nicht mit der seiner Nachbarn 6 und 8 kollidiert wäre, also der Graph prinzipiell mit 3 Farben färbbar gewesen wäre.


    Das ist definitiv falsch. Beispielsweise könnte man in Blackhearts verlinkter Grafik auch Gebiet 6 schwarz färben und hätte eine legitime Färbung (es gäbe auch noch andere Möglichkeiten, in dem von GraphZahl genannten kritischen Teilgraphen die Färbung so zu wählen, dass ein anderes Gebiet als 7 schwarz ist und der restliche Graph dreifärbbar ist). Ohne dass mit der Nebenbedinung der gleichen Größe der restlichen drei Färbungen sichergestellt wird, dass zwingend ein Gebiet mit 5 Feldern schwarz gefärbt sein muss, wäre die Sache also nicht eindeutig.

  • Es hat mich mal interessiert, welche Gebiete schwarz sein dürfen, wenn der Hinweis wegfällt: https://imgur.com/wYkgQOE.png

    Das sollten alle Möglichkeiten sein. Wenn man weiß, dass das schwarze Gebiet unter 6, 7, 11, 17, 18, 19 und 22 ist, weiß man damit, dass sich alles außer diesen 7 Gebieten in 3 Farben färben lässt. Legt man willkürlich zwei Farben für 1 und 2 fest, ergibt sich alles außer 5 bereits eindeutig. Gebiet 11 kann dann schwarz oder blau sein. Wenn es schwarz ist, ergibt sich alles eindeutig. Wenn es blau ist, ist Gebiet 5 gelb und Gebiet 6 kann dann noch rot oder schwarz sein, in beiden Fällen ergibt sich alles eindeutig (ist Gebiet 6 rot, ist Gebiet 7 schwarz.)

    Die möglichen schwarzen Gebiete ohne den Hinweis sind also 6, 7 und 11. Die Möglichkeit mit Gebiet 11 hatte auch Blackheart übersehen. Offenbar reicht es nicht aus, zu versuchen, das ganze Bild in 3 Farben zu färben, ohne vorher zu zeigen, dass ein bestimmter Teil davon auch wirklich in 3 Farben gefärbt werden muss.

  • 19*11=209

    209 lässt bei Division durch 3 den Rest 2. Da es keine Zweierfläche gibt, muss das schwarze Feld auf jeden Fall ein Fünferfläche sein.

    Somit beträgt der Flächeninhalt für alle drei Farben 68 Flächeneinheiten.

    Dieser Umstand macht die Aufgabe jetzt recht einfach. Man beginnt mit zwei benachbarten Feldern, die beide keine Fünferfelder sind und füllt sie mit zwei beliebigen Farben aus. (ich habe das Dreier- und das Viererfeld links oben ausgesucht).

    Die restlichen Farbbelegungen ergeben sich als "Zwangszüge" aus den Spielregeln.

    Es bleibt somit nur noch das Feld 7 übrig.

  • Naja, Zwangszüge gibt es dann erstmal nur für die Gebiete, die keine Größe von 5 haben - alle anderen könnten ja theoretisch auch schwarz sein. Wenn man sich aber mal die Gebiete markiert, die keine Größe von 5 haben und deshalb rot, blau oder gelb sein müssen, hat man recht allein stehend 1, 2, 3 und 33 und dann einen großen Klumpen aus 6, 11, 16, 17, 18, 19, 22 und 26. Wenn man dort geschickt zwei benachbarte Felder zum Anfang nimmt, ergeben sich durch Zwangszüge, dass 6, 18 und 19 drei verschiedene nicht-schwarze Farben haben müssen und deshalb 7 schwarz sein muss. Das ist wohl bisher die kürzeste Lösung, die zur 7 führt.

    Bild: https://imgur.com/696BzUl.png

  • Innerhalb der Felder 6, 11, 16, 17, 18, 19, 22 und 26 gibt es vier Dreiergruppen von Feldern, in denen jeweils genau eine der Farben rot, gelb

    oder blau vertreten sein muss: 6, 11, 17; 17, 18, 22; 18, 19, 22; und 11, 16, 26.

    Außerdem lässt sich erkennen, dass die Felder 17 und 19 dieselbe Farbe erhalten müssen, die Felder 6 und 22 tragen die zweite Farbe und Feld 18 die dritte, also muss Feld 7 schwarz sein.

  • Naja, Zwangszüge gibt es dann erstmal nur für die Gebiete, die keine Größe von 5 haben - alle anderen könnten ja theoretisch auch schwarz sein. Wenn man sich aber mal die Gebiete markiert, die keine Größe von 5 haben und deshalb rot, blau oder gelb sein müssen, hat man recht allein stehend 1, 2, 3 und 33 und dann einen großen Klumpen aus 6, 11, 16, 17, 18, 19, 22 und 26. Wenn man dort geschickt zwei benachbarte Felder zum Anfang nimmt, ergeben sich durch Zwangszüge, dass 6, 18 und 19 drei verschiedene nicht-schwarze Farben haben müssen und deshalb 7 schwarz sein muss. Das ist wohl bisher die kürzeste Lösung, die zur 7 führt.

    Bild: https://imgur.com/696BzUl.png

    "Zwangszug" bedeutet bei mir etwas anderes, denn ich wähle die Farbe "schwarz" erst dann, wenn es nicht mehr anders geht.

    Wenn ich also z.B. das Feld 1 gelb und das Feld 2 blau anmale, dann folgt (bei meiner "Schwarzvermeidung"), dass das Feld 10 rot sein muss, daraus, dass das Feld 13 gelb sein muss, usw. ....

    Ich gehe also genau andersrum als Mondrian vor. Er malt ja das schwarze Feld zuerst aus und ich entweder zum Schluss oder wenn es unterwegs nicht mehr anders geht.

  • Dann müsste aus 18 blau und 19 gelb (beide haben keine Größe von 5 und liegen nebeneinander, also kann man auch mit den beiden anfangen) aber auch folgen, dass 7 rot sein muss, oder?

    Dem ist, zunächst, so. Dann erhält man allerdings relativ schnell, nach vier weiteren Zügen, einen Widerspruch auf dem Feld 11 (es müsste sowohl blau als auch rot sein), denn dieses Sechserfeld kann nicht schwarz sein. Also kann das Feld 7 (das einzige bisher ausgemalte Fünferfeld) nicht rot sein, demnach muss es Schwarz sein.