Das Vierfarbenproblem

Beim erschöpfenden Durchsuchen sind wir bisher immer so vorgegangen:

erst färben, dann prüfen

"Färbe die ganze Karte erst vollständig ein und prüfe anschließend, ob die Kolorierung gültig oder ungültig ist."

Die Reihenfolge, in der wir versuchen, die Karte einzufärben, ist durch den Tachometer festgelegt. Betrachten wir noch einmal die vorherige Karte.

nochmal die Karte mit sechs Ländern

Nach Drücken des Reset-Knopfes wird der Tachostand auf 000000 gesetzt und dann (mit "weiter") stur hochgezählt.

Wir können Folgendes beobachten:

Alle Tachostände, die mit 00 beginnen, führen auf eine ungültige Einfärbung, weil Land 1 und Land 2 benachbart sind.
Das Verfahren probiert also alle Tachostände der Form 00**** durch, obwohl klar ist, dass keiner dieser Tachostände eine Lösung sein kann.
Der erste Tachostand, ab dem eine korrekte Einfärbung erst wieder möglich ist, muss die Form 01**** haben. Um von Tachostand 000000 zu Tachostand 010000 kommen, müsste man 256 mal auf die Taste "weiter" klicken.

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)