Das Vierfarbenproblem

Neue Idee

Die Nachteile des sturen Hochzählens können wir umgehen, indem wir die Lösung schrittweise aufbauen.

	Wir färben das erste Land grün und lassen die übrigen Länder zunächst ungefärbt. Das entspricht dem Tachostand 0*****.
	Jetzt versuchen wir, das zweite Land zu färben. Der erste Tachostand, für den das geht, ist 01****.

Im Vergleich zum vorigen Verfahren haben wir jetzt 256 Versuche überschlagen. Nun versuchen wir, die dritte Stelle im Tacho zu belegen, also das Land 3 zu färben und so weiter.

Wir arbeiten uns also schrittweise von links nach rechts vor, indem wir ein Land nach dem nächsten mit einer erlaubten Farbe belegen.

Reihenfolge für Test der Farben

Für jedes neue Land, das wir färben wollen, probieren wir zuerst die Farbe grün (Ziffer 0), dann blau (Ziffer 1), dann rot (Ziffer 2) und zuletzt gelb (Ziffer 3).

a)	Welche der folgenden Karten lassen sich mit nur drei Farben kolorieren ?

b)	Kann man die Deutschlandkarte der Startseite mit nur drei Farben kolorieren ?

a)	Ordne folgenden Karten jeweils den entsprechenden Tachostand zu.
0 = grün 1 = blau 2 = rot 3 = gelb
b)	Welchen Färbungszustand beschreiben folgende Tachostände ?

c)	Wieviele Färbungszustände hat eine Karte mit zehn Ländern ?
d)	Wieviele Färbungszustände hat eine Karte mit zehn Ländern, wenn man sechs verschiedene Farben zuläßt ?

a)	Es gibt keine Frucht, die mit dem Buchstaben D beginnt.
b)	Der Term $\frac{1}{x^{2}-4}$ ist für alle reellen Zahlen x definiert.
c)	Für alle natürlichen Zahlen k ist $\displaystyle 2^{(2^k)} + 1$ eine Primzahl.
d)	Mädchen sind doof. (Schwierig)