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?

  1. runaway 13.02.02 07:52

    ..eigentlich gar nicht so viele....
    man nehme das Land, welches die meisten Nachbarn hat und zähle sie alle zusammen....die Anzahl dieser Länder bzw. Farben müssten demnach reichen, um alle Länder einzufärben..

    Antworten Melden
    (4.1/5)   4 Votes
  2. runaway 13.02.02 08:00

    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.

    Antworten Melden
    (4.2/5)   5 Votes
  3. Anj... 13.02.02 08:06

    Was ist mit Dänemark? ;-)

    Antworten Melden
    (4/5)   7 Votes
  4. Jan... 13.02.02 08:45

    Tschechien ;-) oder Èesko

    Antworten Melden
    (4.1/5)   4 Votes
  5. Jan... 13.02.02 08:46

    soll Cesko mit Häckchen oben heißen, komische Umwandlung durch das Sqeuaker-Programm

    Antworten Melden
    (4.1/5)   6 Votes
  6. a29... 13.02.02 12:48

    Warum sollten denn z.B. Polen und Belgien verschiedene Farben bekommen? Die haben doch keine gemeinsame Grenze.

    Antworten Melden
    (4/5)   7 Votes
  7. Anj... 13.02.02 20:35

    Du hast vollkommen recht. Es geht mit weniger Farben. Ist mir dann heute morgen beim Duschen auch noch eingefallen... ;-)

    Antworten Melden
    (4.5/5)   5 Votes
  8. Anj... 13.02.02 08:15

    Und Du darfst das Land selbst natürlich nicht vergessen. Also hätten wir für Dein Beispiel - unter Berücksichtigung Dänemarks *g* - 10 Farben.

    Antworten Melden
    (4.3/5)   5 Votes
  9. runaway 13.02.02 20:46

    stimmt...es sind 10 Farben

    noch etwas:
    a) ich kann nicht zählen
    b) ich habe die lieben Dänen vergessen

    aber bleibe bei meiner These, lieber etwas mehr Farben als nacher wenige...

    Antworten Melden
    (4.4/5)   7 Votes
  10. Suesse 13.02.02 23:39

    Ach ja, bunter ist es auch viel schöner, nicht? ;-))) Aber gefragt war ja das Minimum...

    Antworten Melden
    (4.3/5)   5 Votes
  11. Jan... 13.02.02 09:27

    4 ?

    Antworten Melden
    (4.1/5)   5 Votes
  12. Suesse 13.02.02 12:57

    eigentlich sollten 3 farben bei geschickter anordnung ausreichen - kommt aber auch noch auf die grenzverläufe an...

    Antworten Melden
    (4.5/5)   3 Votes
  13. Jan... 13.02.02 13:05

    schon vier, oder

    Versuch z.B. die Stelle mit Dtld., Niederlande, Belgien, Frankreich, Luxemburg

    mit drei geht es nicht

    Antworten Melden
    (4.1/5)   5 Votes
  14. 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)

    Antworten Melden
    (4.4/5)   7 Votes
  15. Suesse 13.02.02 23:36

    darum sagte ich ja: kommt auf die grenzverläufe an...

    Antworten Melden
    (4.1/5)   6 Votes
  16. 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


    Antworten Melden
    (4.1/5)   4 Votes
  17. 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*

    Antworten Melden
    (4/5)   4 Votes
  18. 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?

    Antworten Melden
    (4.4/5)   5 Votes
  19. runaway 20.02.02 19:05

    eine sehr bildende Darstellung...danke

    Antworten Melden
    (4.2/5)   3 Votes
  20. 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.

    Antworten Melden
    (4.4/5)   3 Votes
  21. Jan... 22.02.02 17:20

    4, habe noch einmal bei a2920000 nachgefragt! ;-)

    Antworten Melden
    (4.1/5)   4 Votes
  22. Mic... 25.02.02 19:57

    Bei der additiven Farbmischung verwendet man Grün, Blau, Rot, bei der subtraktiven Gelb, Cyan und Magenta.

    Antworten Melden
    (4/5)   7 Votes
  23. wavewoman 01.03.02 19:03

    Also ich tippe mal auf zwei Farben. Durch verschiedene Mischverhältnisse kann man aus zwei Farben beliebig viele(naja, jedenfalls sehr viele) unterschiedliche Farbtöne herstellen.

    Antworten Melden
    (4.5/5)   3 Votes
  24. a29... 06.03.02 16:40

    Wenn ich mit meinem Drucker daheim Grautöne erzeuge, kommt der sogar mit einer einzigen Farbe aus...

    Antworten Melden
    (4.5/5)   4 Votes
  25. Hen... 09.03.02 14:38

    di Frage ist nicht, wie man es macht, sondern warum man es machen soll. wenn man einfach den namen von dem land in die grenzen schreibt, weiss doch jeder bescheid.

    Antworten Melden
    (4/5)   5 Votes

Disclaimer: Erfahrungsberichte und andere Nutzerbeiträge sind subjektive Erfahrungen einzelner Personen und spiegeln nicht die Meinung der squeaker.net-Redaktion wieder. Beitrag melden.      

  • »Ehrliche, kontrollierte und anonyme Erfahrungsberichte auf squeaker.net sind eine wichtige und sinnvolle Hilfe im Bewerbungsprozess bzw. bei der Auswahl interessanter Arbeitgeber.«

    Was unsere Mitglieder über uns sagen
  • »squeaker.net’s eigener, authentischer Stil, hohe Qualität des Netzwerkes und die Infos sind das Beste.«

    Was unsere Mitglieder über uns sagen
  • »Man sollte sich ein genaues Bild von jeder Firma machen bevor man sich bewirbt. Deshalb habe ich mich auf www.squeaker.net angemeldet.«

    Was unsere Mitglieder über uns sagen
  • »squeaker.net hat mir bei meinem Bewerbungsprozess sehr geholfen, das Insider-Wissen zu den Interviews und Unternehmen ist Gold wert!«

    Aly Zaazoua, Squeaker und angehender Praktikant bei Siemens Management Consulting
  • »Unabhängige Bewertungen und Erfahrungsberichte wie auf squeaker.net sind unbezahlbar.«

    Was unsere Mitglieder über uns sagen