Vorherige Aufgabe   Übersicht 2002   Nächste Aufgabe 

Lösungen der DENKmal-Knobelaufgaben

5. Aufgabe 2002

gestellt am 25. März 2002 in der Knobelecke von
Abenteuer Mathematik - die Welt des Knobelns

Vierfarbenproblem
(lässt sich auch auf Ostereier anwenden ;-))

  Aufgabe   Lösung 

Aufgabe

Das Vierfarbenproblem besteht darin, eine in Teilflächen unterteilte Fläche so einzufärben, dass keine der Teilflächen mit einer anderen Teilfläche gleicher Farbe ein Stück Rand gemeinsam hat. (Man denke etwa an das Einfärben einer politischen Landkarte.)
Die Mathematiker haben herausgeknobelt, dass vier Farben für jede beliebige Unterteilung ausreichen!

Abb.1
Abb. 1
Abb.2
Abb. 2

Die 20 Teilflächen im Kreis sollen dementsprechend mit den vier Farben Rot, Gelb, Grün und Blau eingefärbt werden, wobei einige Felder bereits eingefärbt sind.

Aufgaben (für Abb. 1 und Abb. 2)

  1. Gib jeweils eine mögliche Einfärbung an!
  2. Wie viele verschiedene Möglichkeiten der Einfärbung gibt es jeweils?
  3. Bei welcher/n Einfärbung(en) ist/sind jede der vier Farben in genau fünf Feldern vertreten?

(Die Lösung kann in Tabellenform angegeben werden, z.B. 1 ro, 2 ge, 3 gr usw.).

(eingesandt von Rolf Herrmann)

Lösung

Für Abb. 1 Für Abb. 2
Von den 20 Feldern sind 7 vorgefärbt:
A123481518








Von den 20 Feldern sind 6 vorgefärbt:
A12341517







Das Feldnbsp;5 hat drei Nachbarn mit verschiedenen Farben (Rot, Blau und Gelb) und wird grün gefärbt, weil es sonst an ein anderes Feld mit der selben Farbe grenzen würde. Anschließend ist das Feld 6 blau zu färben, weil dies die einzige Farbe ist, die unter seinen Nachbarn noch nicht vertreten ist.
Analog ergibt sich für das Feld 9 die Farbe Grün, daraus für 10 die Farbe Rot, für 11 Gelb und schließlich für 19 Grün.
B569101119







Das Feld 5 wird wegen seiner roten, blauen und gelben Nachbarfelder grün gefärbt. Danach bleibt für das Feld 6 wegen seiner roten, grünen und gelben Nachbarfelder die Farbe Blau.
B56



Danach sind noch zwei zusammen hängende Bereiche ungefärbt.
Für die Felder 7, 16 und 17 ergeben sich durch Probieren 3 verschiedene Färbungsmöglichkeiten:
C71617
C1


C2


C3


Für das Feld 7 gibt es erstmal zwei mögliche Färbungen: Gelb und Grün. Wäre es gelb, bliebe für Feld 6 nur Grün, für Feld 8 nur Blau und das Feld 9 könnte nicht gefärbt werden, weil alle vier Farben als Nachbarfarben vorkommen.
Also wird Feld 7 grün gefärbt und die Farben der Felder 8, 9, 10, 11, 16, 18 und 19 folgen daraus.
C7891011161819









In beiden Abbildungen haben die Felder 12, 13, 14 und 20 gleich gefärbte Außennachbarn. Sie können auf 5 verschiedene Weisen gefärbt werden:
D12131420
D1



D2



D3



D4



D5



  1. Eine der möglichen Einfärbungen ist diese (A, B, C1, D1):
    1234567891011121314151617181920





















  2. Die Färbungen der beiden Bereiche C und D können unabhängig voneinander kombiniert werden. Daraus ergeben sich 3*5 = 15 Färbungsmöglichkeiten.

  3. Alle Kombinationen aus A, B und C enthalten genau 4 blaue und 3 rote Felder. Es fehlen also 1 blaues und 2 rote Felder, was bei D2 erfüllt ist. Für die restlichen Felder können die Kombinationen C1 und C2 verwendet werden:
    1234567891011121314151617181920









































  1. Eine der möglichen Einfärbungen ist diese (A, B, C, D1):
    1234567891011121314151617181920





















  2. Aus jeder der 5 Färbungen des Bereiches D folgt eine erlaubte Gesamtfärbung. Es gibt also 5 Färbungsmöglichkeiten.

  3. Die Bereiche A, B und C enthalten zusammen 3 rote, 4 gelbe, 5 grüne und 4 blaue Felder. An jeweils 5 Feldern fehlen also 2 rote, 1 gelbes, keine grüne und 1 blaues Feld, was nur bei D2 zu finden ist.
    1234567891011121314151617181920