Von Farben und Landkarten
a29...
13.02.02 02:14
Mal was Einfaches: Wieviele verschiedene Farben benötigt man minimal, um eine beliebige Landkarte (ohne Meere) so einzufärben, daß nie zwei Länder mit gemeinsamer Grenze dieselbe Farbe haben?
29 Kommentare zu »Von Farben und Landkarten« Jetzt alle Antworten anzeigen
-
angenommen Deutschland hat die meisten Nachbarn: so Polen, Tschechei, Österreich, Schweiz, Frankreich, Belgien, Niederlande und Luxemburg. Das macht mit Deutschland zusammen 8 Länder. Also müssten auch 8 Farben ausreichen, da es kein anderes Land gäbe, welches mehr gemeinsame Grenzen mit anderen Ländern aufzuweisen hätte.
-
beo...
13.02.02 16:55
tja, eigentlich sollten ja streng genommen drei farben ausreichen... nämlich die drei grundfarben, alle anderen ergeben sich daraus ja - wer mir nun vorwirft, das sei nicht die aufgabenstellung, kann ich nur sagen, dass die Frage ja genau so lautet (wie viele farben man mindestens benötigt).
außerdem noch eine anmerkung: das verfahren, einfach die angrenzenden länder abzuzählen verstehe ich nicht so ganz, denn immerhin wird in der fragestellung nur allgemein von einer landkarte gesprochen (auch die gesamt welt passt auf eine weltkarte und genauso kontinente, etc) -
Mic...
13.02.02 22:18
Vier.
Dahinter liegt das sogenannte Vierfarbenproblem. Empirisch ist sehr lange bekannt, das sich eine Landkarte mit vier Farben einfärben lässt, aber der Beweis ist noch nicht gelungen. Wahrscheinlich handelt es sich dabei um ein Beispiel für die von Gödel bewiesene Unvollständigkeit des Mathematischen Kalküls. Alternativ auch Halteproblem der Turing Maschine.
Michael
-
Anonym 14.02.02 13:47
aehm...michael....ich will ja nich unwissend erscheinen, aber von deiner antwort habe ich jetzt hoechstens die haelfte verstanden.... ;) was ist ein Kalkuel? und was heisst empirisch????
ja, ich gebs zu, bin Total ungebildet...aber ich muss ja auch noch gar nich so viel wissen...weil, bin ja noch sooooo jung....*gg* -
Mic...
18.02.02 23:38
Hallo Kruemel,
sorry, wenn ich hier die Diskussion abgewürgt habe.... Empirisch? Durch Beobachtung, im Gegensatz zu analytisch oder deduktiv (aus logischen Schluss abgeleitet). Man weiß aus Erfahrung, das man mit vier Farben auskommt, kann es aber nicht beweisen (d.h., offenbar gibt es einen umstrittenen Beweis).
Mathematisches Kalkül? Grundsätzlich beruht zum Beispiel die Analysis auf ca. einem Dutzend sog. Axiomen, d.h. unbewiesenen Aussagen, u.a.
(1) a + b = b + a.
(2) a + (b + c) = (a + b) + c.
...
Man geht davon aus, das diese Sätze richtig sind, ohne das man sie beweisen kann. Sie sind quasi "gesetzt".
Ausgehend von diesen Axiomen lässt sich die restliche Analysis bis zu Differenzialgleichungen zwingend durch Beweise ableiten. D.h. in diesem Axiomensystem ist die gesamte Mathematik bereits definiert. Man nennt diese Mathematik (die eine von mehreren möglichen ist) das mathematische Kalkül.
Die zweite Betrachtungsweise ist, das die Mathematik mit ihren Symbolen eine Sprache ist (wie etwa Latein), mit der ich Sachverhalte ausdrücken kann.
Einfache axiomatische Systeme sind vollständig, d.h. ausgehend von dem Axiomen kann ich durch Beweise neue Sätze (=Aussagen) bilden. Im Allgemeinen kann ich das durch Umformungen und festen Schlussregeln machen, so das für diesen Vorgang keine Intelligenz notwendig ist, sondern es handelt sich um einen reinen syntaktischen (=mechanischen) Vorgang. Einfache aussagenlogische Axiomensysteme sind vollständig, d.h. ich kann genau alle wahren Sätze erzeugen (ich erzeuge alle wahren Sätze und keine falschen). Das gilt übrigens für jede beliebige Interpretation der Sätze.
Die Mathematik ist ein aussagenlogisches System 2ter Ordnung. Gödel hat bewiesen, das axiomatische Systeme höherer Ordnung (genauer gesagt: prädikatenlogische Systeme) unvollständig sind. D.h. es gibt (mathematische) Sätze, die richtig, und damit nicht widerlegbar, aber auch nicht beweisbar sind. Logischerweise kann ich für diese Sätze nicht nachweisen, ob sie zu den unbeweisbaren aber wahren gehören, denn dann hätte ich ja bewiesen, das sie richtig sind.
Dieser Beweis taucht analog in verschiedenen Stellen in der Mathematik auf. Alan Turing hat die sog. Turing Maschine definiert, sozusagen eine abstrakte Rechenmaschine. Die Churche These besagt, das alles, was berechenbar ist, auch Turing-berechenbar ist, d.h. von einer Turing Maschine berechnet werden kann. Die Turing Maschine hält, wenn sie etwas berechnet hat.
Das Halteproblem heißt, wenn die Turingmaschine hält, ist das Problem berechenbar. Das Problem eines Beweis für ein beweisbaren Satz ist durch eine Turingmaschine berechenbar, d.h. die Turingmaschine hält. Man kann allerdings nachwiesen, das es Turingmaschinen gibt, von denen ich nicht sagen kann, ob sie halten, das heißt es existieren unlösbare Probleme. Allerdings kann ich zu einem konkreten Problem im Allgemeinen nicht sagen, ob es lösbar ist. Eine vor allem philosophisch wichtige Erkenntnis.
Alles klar?
-
Cle...
22.02.02 15:12
Das sind ja alles ganz schöe Überlegungen, aber wie kommt Ihr auf Deutschland? Ich glaube die Antwort ist drei (gelb, blau und rot). Egal wie viele Grenzen da sind aus diesen Fraben kann man unendlich viele Frabtöne mischen.
Schließlich steht da es soll mal eine einfache Frage sein.
29 Kommentare zu »Von Farben und Landkarten« Jetzt alle Antworten anzeigen
Disclaimer: Erfahrungsberichte und andere Nutzerbeiträge sind subjektive Erfahrungen einzelner Personen und spiegeln nicht die Meinung der squeaker.net-Redaktion wieder. Beitrag melden.