Anzahl der kürzesten Wege bew. < Induktion < eindimensional < reell < Analysis < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | | In einem amerikanischen Stadtplan mit n+1 Avenues und m+1 Streets wollen Sie von Punkt A nach Punkt B gehen. Wieviel kürzeste Wege gibt es? Beweisen Sie die Formel mit vollständiger Induktion. |
Hallo liebe MatheRaum-Community!
Ich muss die erwähnte Aufgabe beweisen und habe keine Ahnung, wie ich das tun soll. Zu sagen wäre dazu noch, dass die Punkte A und B n+m-weit voneinander entfernt sind (Punkt A liegt oben links, Punkt B unten rechts). Die Numerierung beginnt bei Punkt A (0,0) und endet bei Punkt B (n,m). Es sind jeweils die "Knoten" zwischen den Streets und Avenues numeriert. Da ich das Bild nicht online stellen kann hoffe ich, dass diese Beschreibung reicht.
Die Formel für die Anzahl der kürzesten Wege habe ich mir bereits überlegt. Sie müsste folgendermaßen sein: [mm] \vektor{m+n \\ n}
[/mm]
Nun habe ich allerdings das Problem, dass ich nicht weiß wie ich die Formel beweisen soll, da mir ja eigentlich ein Teil fehlt, um eine vernünftige Induktionsveraussetzung zu haben, oder täusche ich mich da?
Da ich selber dabei möglichst viel lernen will, wäre es sehr freundlich, wenn ihr mir keine komplette Lösung postet, sondern einen guten Tipp, wo mein Denkfehler liegt oder was ich übersehen habe. Danke schonmal dafür!!
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
Mfg
Jack
P.S.: Falls noch irgendwelche Fragen bestehen tut es mir Leid, diese nicht geklärt zu haben, werde dies aber schnellstmöglich tun wenn ihr sie stellt.
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 19:45 Mi 31.10.2007 | | Autor: | Blech |
> Die Formel für die Anzahl der kürzesten Wege habe ich mir
> bereits überlegt. Sie müsste folgendermaßen sein:
> [mm]\vektor{m+n \\ n}[/mm]
Denke nicht.
> Nun habe ich allerdings das Problem, dass ich nicht weiß
> wie ich die Formel beweisen soll, da mir ja eigentlich ein
> Teil fehlt, um eine vernünftige Induktionsveraussetzung zu
> haben, oder täusche ich mich da?
Versuch mal, über die n Zeilen der Länge m zu induzieren.
Wenn Du eine Zeile der Länge m hast, wieviele Möglichkeiten hast Du dann, von links in der oberen Straße nach ganz rechts in der unteren zu gehen?
Und wieviele kommen mit einer zweiten Zeile hinzu?
|
|
|
| |
|
> Denke nicht.
Warum nicht, wenn ich fragen darf? Kam bis jetzt immer hin.
> Wenn Du eine Zeile der Länge m hast, wieviele Möglichkeiten hast Du
> dann, von links in der oberen Straße nach ganz rechts in der unteren zu > gehen?
> Und wieviele kommen mit einer zweiten Zeile hinzu?
Genau darüber mache ich mir schon seit Tagen Gedanken, ich erkenne nur kein Muster dahinter! Meine Formel habe ich auch großteils durch ausprobieren bekommen und nicht, weil ich das Muster dahinter durchschaut habe. Wenn ich also ein Muster von m=m und n=1 habe, dann bekomme ich m+1 Wege. Ich krieg es aber nicht allgemein formuliert, wieviel immer dazukommen.
|
|
|
| |
|
Ich denke schon, dass du recht hast. Eigentlich ist das elementare Kombinatorik, wenn man sich's so überlegt: Insgesamt sind es n+m Schritte (Straßen), die in beliebiger Reihenfolge zurückgelegt werden können. Wir müssen jetzt daraus n Schritte auswählen und die Anzahl der Möglichkeiten n aus (n+m) auszuwählen ist gerade (n+m) über n.
|
|
|
| |
|
Schön, dass du mir wenigstens mit der Formel zustimmen kannst, generation.
Nur stellt sich mir jetzt immer noch die Frage, wie beweise ich das korrekt? Ich habe ja nur eine Formel, aber um eine vernünftige Induktionsvoraussetzung zu haben bräuchte ich doch noch eine, oder? Oder kann ich einfach als Basisfall n=1 und m=m+1 annehmen und dann einfach sagen, es gibt m+2 Wege? Das kann ich ja irgendwie nicht verifizieren anhand einer zweiten Formel.
Ich hoffe ihr versteht, was ich meine.
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 22:16 Mi 31.10.2007 | | Autor: | Blech |
> Schön, dass du mir wenigstens mit der Formel zustimmen
> kannst, generation.
Sie ist auch (fast) richtig. Ich hatte es bei einem kurz durchgespielt und kam auf was anderes; das Problem war, daß Du in der Formel die Schritte nach rechts bzw. unten zählst und nicht die Gesamtzahl der Straßen (ist jeweils 1 mehr).
Ist natürlich kein ernsthaftes Problem
> Nur stellt sich mir jetzt immer noch die Frage, wie beweise
> ich das korrekt? Ich habe ja nur eine Formel, aber um eine
> vernünftige Induktionsvoraussetzung zu haben bräuchte ich
> doch noch eine, oder? Oder kann ich einfach als Basisfall
> n=1 und m=m+1 annehmen und dann einfach sagen, es gibt m+2
> Wege? Das kann ich ja irgendwie nicht verifizieren anhand
> einer zweiten Formel.
Wie wäre es mit doppelter Induktion:
[Dateianhang nicht öffentlich]
Also, die erste Zeile ist trivial. (d.h. (1,k), (j,k) ist die Matrixgröße; j und k sind Schritte, nicht Straße, wie bei Dir oben)
Jetzt nehmen wir (2,1); das ist das gespiegelte von (1,2), also paßt
Jetzt (2,2); das ist die Anzahl der Möglichkeiten (2,1) zu durchlaufen (also zum roten Punkt zu kommen) + die Anzahl der Möglichkeiten zum blauen zu kommen.
Jetzt (2,3); das ist (2,2)+(1,3)
usw. so füllen wir die zweite Zeile.
dann die 3. Zeile, etc.
die Formel ergibt sich jeweils aus
[mm] ${n+1\choose k+1} [/mm] = [mm] {n\choose k}+{n\choose k+1}$
[/mm]
EDIT: 1. mußt Du bei der 3. Zeile natürlich nicht mehr bei (3,1) anfangen, sondern es geht ab (3,2), da wir (2,3) ja schon kennen.
2. ggf. mußt Du das ganze spiegeln (d.h. eine Spalte nach der anderen füllen, anstatt Zeilen), weil es so nur funktioniert wenn [mm] $m\geq [/mm] n$
3. Kommt man natürlich schneller durch, wenn man sich diagonal durchhangelt, anstatt jeweils eine Zeile (Spalte) ganz zu machen.
Aber wir müssen die Schritte ja nicht wirklich machen, nur ihre Machbarkeit zeigen, also ist's kein Unterschied =)
4. Ich hoffe jetzt funktioniert's wirklich allgemein.
Dateianhänge:
Anhang Nr. 1 (Typ: PNG) [nicht öffentlich]
|
|
|
| |
|
Vielen Dank, Blech!
Ich habe verstanden was du tust, aber nicht warum es so funktioniert. Könntest du das vielleicht etwas erläutern, oder mir einfach einen Link geben, wo das beschrieben ist?
Und vielleicht noch eine Frage, die mit dem eigentlichen Thema nicht mehr viel zu tun hat, hätte man sowas mit "Schulwissen" lösen können, denn entweder ich (und nicht nur ich) bin extrem blöd, oder die Aufgabe ist nicht ganz einfach? (Ich hatte erst 3 Vorlesungen)
Mfg
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 23:06 Mi 31.10.2007 | | Autor: | Blech |
> Vielen Dank, Blech!
>
> Ich habe verstanden was du tust, aber nicht warum es so
> funktioniert. Könntest du das vielleicht etwas erläutern,
> oder mir einfach einen Link geben, wo das beschrieben ist?
Naja, sowohl vom blauen, wie auch vom roten Punkt gibt es jeweils nur noch einen Weg zum Endpunkt. Gleichzeitig haben sie keine Wege gemein, weil sie auf Punkten enden, die jeweils nicht in der Menge der möglichen Punkte des anderen liegen.
> Und vielleicht noch eine Frage, die mit dem eigentlichen
> Thema nicht mehr viel zu tun hat, hätte man sowas mit
> "Schulwissen" lösen können, denn entweder ich (und nicht
> nur ich) bin extrem blöd, oder die Aufgabe ist nicht ganz
> einfach? (Ich hatte erst 3 Vorlesungen)
Also vielleicht gibt es eine brilliante, offensichtliche Methode zur Induktion hier, kann gut sein. Leider sehe ich sie nicht.
Sicher, daß Ihr das ganze mit Induktion lösen müßt?
Die andere Antwort hatte nämlich einen recht kurzen, eingängigen Beweis, der nur Schulwissen enthielt.
Vielleicht sollst Du auch nur mit Induktion zeigen, daß jeder Weg, bei dem man sich nur nach links und unten bewegt, ein kürzester Weg ist? Die Anzahl könntest Du dann kombinatorisch machen.
|
|
|
| |
|
Super, jetzt ist mir das klar geworden.
Und ja, wir sollen die Formel mit vollständiger Induktion beweisen. Die Aufgabenstellung ist auch exakt so, wie im ersten Beitrag von mir aufgeschrieben. Dann werde ich einfach deine angegeben Formel für den Induktionsbeweis benutzen, der mir eigentlich gelingen sollte.
Also nochmal danke!!
Mfg
Jack
|
|
|
| |
|
| Status: |
(Frage) beantwortet  | | Datum: | 15:40 Do 01.11.2007 | | Autor: | jackie |
Hallo,
ich habe die lösung der aufgabe nicht wirklich verstanden, ich wäre froh wenn mir jemand die ganze lösung schreiben könnte und ne erklärung dazu, vllt als private nachricht falls die anderen die lösung nicht mitlesen wollen und selber knobeln wollen. ich wäre sehr froh drum.
danke
gruß jackie
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 08:04 Fr 02.11.2007 | | Autor: | koepper |
Guten Morgen Professor Jackie,
es geht hier nicht um knobeln sondern um verstehen. Und verstehen kann man nur durch eigenes Denken.
Wenn jemand behauptet er habe "alles" nicht verstanden, dann behaupte ich kühn, er habe es auch gar nicht richtig gelesen und sich bemüht es zu verstehen. Andernfalls wären nämlich konkrete Fragen vorhanden.
Nichts für ungut 
LG
Will
|
|
|
|
