Vollständigkeit der vollständigen Induktion... |
| 21.08.2006, 17:18 | sqrt4 | Auf diesen Beitrag antworten » | ||||
| Vollständigkeit der vollständigen Induktion... bei der Lösung eines Problems hätte ich jetzt folgenden Ansatz um die Aufgabe zu lösen. Also ich beweise sie mit vollständiger Induktion. Das Problem ist, das die Aufgabe mit zunehmenden n immer umfangreicher wird. Soll heißen für n=1 gibt es einen Fall und für n=10 gibt es tausend Fälle. Jetzt will ich zeigen, dass ich mit meinem Induktionsschritt alle Fälle bearbeite. Dazu hätte ich jetzt angenommen dass es einen Fall gibt, den mein Induktionsschritt außer Acht lässt. Dabei komme ich zu einem Widerspruch. Ist das logisch richtig??? Ist da nicht ein Fehler drin?.. weil ich ja etwas annehme, was ich eigentlich beweisen will. |
||||||
| 21.08.2006, 17:27 | irre.flexiv | Auf diesen Beitrag antworten » | ||||
Kannst du das Problem bitte mal posten? |
||||||
| 21.08.2006, 17:39 | sqrt4 | Auf diesen Beitrag antworten » | ||||
Solche Aufgaben gibt es viele. Ein Bsp wäre vielleicht. 2 Menschen haben jeweils n Karten. Jeder schreibt die auf seine n Karten die Zahlen 1-2n (hinten und vorne). Man beweise, dass man dann die Karten der beiden in einer Reihe hinlegen kann, so dass man alle Zahlen von 1- 2n sehen kann. Für n=1 gibt es ja nur einen Fall (wenn man mal von der Bezeichnung hinten und vorne absieht..) Aber für n=100 gibt es was weiß ich wieviele Fälle.. Mir gehts jetzt aber weniger um die Aufgabe sondern um das Prinzip meiner Argumentation... |
||||||
| 21.08.2006, 17:49 | irre.flexiv | Auf diesen Beitrag antworten » | ||||
Ich versteh das Problem nicht. Würd jetzt einfach sagen alle Karten auf den Tisch dann liegt jede Zahl zwischen 1 und 2n genau 2 mal da. Edit: Ich ziehe meinen Kommentar zurück. =) |
||||||
| 21.08.2006, 17:54 | JochenX | Auf diesen Beitrag antworten » | ||||
Mich würde etwas anderes viel mehr interessieren - wie sieht denn dein Induktionsschritt in einem dieser vielen Beispiele aus? Bleiben wir bei deinem obigen Beispiel - in meinen Augen für eine Induktion ungeeignet.
Dafür hätte ich gerne ein Beispiel, da kann ich mir absolut nix vorstellen, wo das sinnvoll sein sollte, dieses "Beweisverfahren" |
||||||
| 21.08.2006, 18:45 | sqrt4 | Auf diesen Beitrag antworten » | ||||
Das ist ja gerade das Problem der Induktionsschritt ist alles andere als leicht. Trotzdem kann man ihn formulieren. Aber um zu beweisen dass er wirklich für alle Fälle gilt mach ich den Widerspruchsbeweis.. Naja ich wusste ja das es eher Blödsinn ist.... |
||||||
| Anzeige | ||||||
|
|
||||||
| 21.08.2006, 18:51 | Lazarus | Auf diesen Beitrag antworten » | ||||
Was ich nicht verstehe ist folgender Sachverhalt. 2 Menschen haben n Karten, von denen jede zwei Seiten hat, deswegen klappt es ja mit allen Zahlen in der Reihe von 1-2n. Wenn ich nun 4 Menschen hab, schreiben die dann 4n Zahlen auf die Karten ? Wo ist dann die dritte und vierte Seite der Karte? Andernfalls ist das Problem trivial weil alle 2n Zahlen doppelt dastehen und man Zweimal die Reihe bilden könnte. Oder hab ich die Aufgabenstellung gänzlich missverstanden? \\edit: Und der Beweis dafür, dass es dann auch gehen würde, wenn die 4 Leute z.b. einen Tetraeder beschriften fühlt sich ein bisschen nach Schublade an.. |
||||||
| 21.08.2006, 19:01 | JochenX | Auf diesen Beitrag antworten » | ||||
Die Laufzahl ist nicht die Anzahl der Menschen, das sind immer 2 Stück. Es variieren die Anzahl der Karten, also n. Hier das Problem nochmal etwas verständlicher formuliert (ich hatte oben auch erst Probleme): Das Spiel: Es gibt 2 Leute, die bekommen n Karten mit je Vorder- und Rückseite. Sie schreiben die Zahlen von 1 bis 2n so auf die Karten, dass jede Vorder- und Rückseite genau eine Zahl hat (es sind ja je genau 2n Vorder- und Rückseiten). Behauptung: Egal, wie die beiden ihre Zahlen schreiben, am Ende kann man die insgesamt 2n Karten (beider Mitspieler) so auslegen, dass jede Zahl von 1 bis 2n genau einmal zu lesen ist (dabei ist natürlich immer genau eine von Vorder/Rückseite pro Karte lesbar). Und das soll für alle n gehen.
ich lerne gerne dazu - deine Aussage, "dass es geht", müsstest du hier mal genauer erklären. Was meinst du mit, man kann ihn "formulieren"? Formulieren als Text in der Art "Annahme: man kann das Spiel mit n Karten pro Spieler machen, zz. dann geht es auch mit n+1 Karten pro Spieler" kann ich das auch, aber ich will doch hoffen, du meinst mit deiner Aussage "beweisen"!? Weil FORMULIEREN ist ja nicht das Problem, das geht ja eigentlich immer und das bedeutet überhaupt nix für die Beweisbarkeit. |
||||||
| 21.08.2006, 19:01 | sqrt4 | Auf diesen Beitrag antworten » | ||||
Jeeep Es soll sich immer um 2 Menschen handeln.... (Induktion nach n (Karten)) Nein aber mir geht es nicht um das Problem an sich sondern um DIE LOGIK..., die leider was ich bisher mitbekommen habe nicht richtig ist. @LOED Können wir von dem Problem wieder Abstand nehemen?! Das verwirrt scheinbar zu sehr.. Nein ich meine beweisen. Aber dass meine Aussage wirklich stimmt, nämlich nicht das der Induktionsschritt richtig ist, sondern VOLLSTÄNDIG ist das will ich mit einem Widerspruchsbeweis beweisen.... |
||||||
| 21.08.2006, 20:16 | irre.flexiv | Auf diesen Beitrag antworten » | ||||
Ich verstehe jetzt was du meinst. Die Anzahl der Fälle ist für den Induktionsbeweis unerheblich. Was du beweisen willst ist ja nur die Existenz einer Lösung. D.h. auf das Kartenbeispiel bezogen: Für jedes n ist lassen sich die Karten so hinlegen, dass ... und zwar unabhängig von der Beschriftung der Karten. Ich hab mal angefangen und so schwer ist es glaube ich nicht. Man muss nur 3 Fälle unterscheiden. |
||||||
| 21.08.2006, 20:27 | sqrt4 | Auf diesen Beitrag antworten » | ||||
Nochmal: Vergesst die Aufgabe Mir geht es um das Prinzip des Beweises. |
||||||
| 21.08.2006, 20:29 | JochenX | Auf diesen Beitrag antworten » | ||||
Nochmal: ich verstehe nicht, was du genau meinst und ich vermute, dass es den meisten hier genauso geht. Da musst du mal ein Beispiel komplett bringen, sonst wird das nichts. Also jetzt das gegebene Beispiel wieder vergessen - okay - aber deine Frage wird dadurch nicht klarer. |
||||||
| 21.08.2006, 20:42 | sqrt4 | Auf diesen Beitrag antworten » | ||||
Okay sry. Also ich versuch es. (oder doch eher tun (Yoda)) 
Allgemein (ohne Bsp) (Es bleibt aber bei den zunehmenden Fällen mit zunehmenden n) Ich beweise die Aussage A(n) mit vollständiger Induktion. Meiner Meinung nach ist dieser Beweis auch richtig. Der einzige Punkt wo es hacken könnte ist, dass mein Induktionsschritt einen Fall auslässt. Also führe ich im Nachhinein noch einen Widerspruchsbeweis und nehme an nicht alle Fälle bearbeitet zu haben. Es stellt sich aber heraus das mein Induktionschritt doch alle Fälle beachtet. Wo ich jetzt bei dieser Sache das Problem sehe ist, dass ich annehme dass es weitere Lösungen gibt. Doch ursprünglich sollte ich ja die Aussage A(n) beweisen. |
||||||
| 21.08.2006, 20:54 | PK | Auf diesen Beitrag antworten » | ||||
Das erinnert mich schwer an die erste Aufgabe der zweiten Runde des BWM 2006. Da braucht man nämlcih exakt den gleichen Ansatz
edit: vielleicht Zufall, ich will hier nichts unterstellen. |
||||||
| 21.08.2006, 20:59 | JochenX | Auf diesen Beitrag antworten » | ||||
Also wenn ich dich hier richtig verstehe, dann gehört dieser Widerspruchsbeweis einfach zu deinem Induktionsschritt dazu. Induktionsschritt ist ja immer, dass du annimmst, etwas gelte für alle Werte <n und zeigst, dass es dann für n gilt (oftmals reicht, dass es für n-1 gilt). Wenn du dabei zeigen musst, dass dein Beweis nur dann gilt, wenn blablabla alle Fälle blabla, dann gehört das da einfach dazu. Wann das sinnvoll sein kann, weiß ich noch nicht, aber ich wüsste nicht, was daran scheitern sollte. Vielleicht postet PK ja mal die alte (alte??) BWM-Aufgabe. |
||||||
| 21.08.2006, 21:04 | irre.flexiv | Auf diesen Beitrag antworten » | ||||
Nochmal: Du hast also eine Aussage A(n) bewiesen. D.h. für jedes n gibt es einen Fall so dass A(n) gilt. Du kannst aber weder sagen welcher Fall das ist, noch für wieviel Fälle A(n) gilt denn du hast nur die Existenz bewiesen. Das macht die Frage ob der Induktionsschritt einen Fall ausgelassen hat sinnlos. |
||||||
| 21.08.2006, 21:10 | JochenX | Auf diesen Beitrag antworten » | ||||
Hat deine Frage irgendetwas mit der BWM zu tun, sqrt 4? PK sagt mir, dass die entsprechende Runde noch anläuft, deswegen würde ich das normalerweise bis zum Rundenende übernächsten Freitag schließen und verwahren..... Wenn es nichts dringendes ist, dann kann es ja wohl auch bis dahin warten. Einwände? [danke, PK] |
||||||
| 21.08.2006, 21:31 | sqrt4 | Auf diesen Beitrag antworten » | ||||
Kein Problem wir können auch später darüber reden . . . Aber was du geschrieben hast LOED scheint einleuchtend... sqrt4 |
||||||
| 21.08.2006, 21:38 | JochenX | Auf diesen Beitrag antworten » | ||||
Okay, jetzt wurde eh schon ziemlich viel gesagt. Ich mache trotzdem vorerst mal zu *vorerst geschlossen*. Bitte erinnere mich jemand daran, das dann übernächsten Freitag (1.9.) wieder aufzumachen (*) (bzw. vielleicht ists ja eh schon gegessen). Bitte verstehe mich nicht falsch, du bist ja schon einige Zeit im Forum unterwegs und kennst die Regeln, dir will hier niemand böses unterstellen 8ich glaube auch nicht, dass du irgendwo anschummeln wolltest), aber das sind halt so Standardregeln, dass man bei solchen Wettbewerben nicht hilft (und es könnte ja sein..... naja, du weißt, wie das ist). Ich denke, wir kommen deswegen im Forum nicht schlechter miteinander aus 
Gruß, Jochen (*) ah, endlich kann ich mal die persönlichen Termine sinnvoll testen |
||||||
| 01.09.2006, 20:12 | JochenX | Auf diesen Beitrag antworten » | ||||
heute sollte nach PK der Wettbewerbeinsendetermin vorbei sein hier ist es wieder *offen* |
||||||
| 01.09.2006, 22:01 | AD | Auf diesen Beitrag antworten » | ||||
Ich versteh's auch nicht. Ich ahne nur dunkel, dass sqrt4 irgendwelche "kombinatorischen Vielfältigkeiten" einer konkreten Aussage A(n) mit dem Induktionsprinzip durcheinandermengt. Das eine hat aber mit dem anderen primär nix zu tun. Klar kann so ein Schluss , oder allgemeiner , ziemlich kompliziert und zum Haareausraufen sein, und manchmal auch nicht gelingen. Trotzdem stellt das aber nicht das Induktionsprinzip an sich in Frage. |
||||||
| 02.09.2006, 01:48 | Lazarus | Auf diesen Beitrag antworten » | ||||
Jetzt wos vorbei ist muss ich aber dochmal fragen: Ich seh den zusammenhang mit "der" Aufgabe von BWM nicht. (darf ich die schon posten?) Denn der entscheidente Punkt bei der BWM aufgabe war ja, dass der Reihe nach nummeriert wurde und es dann egal wo die jeweiligen Anfänge lagen möglich sein soll die Zahlenfolge 1-n zu finden. Hier ist das Problem zwar ähnlich klingend dennoch ein gänzlich anderes, oder lieg ich da falsch. Servus |
||||||
| 02.09.2006, 05:35 | PrototypeX29A | Auf diesen Beitrag antworten » | ||||
Deine Aussage A(n) ist doch in deinem Beispiel: Für jede Beschriftung von n Karten gibt es eine Konfiguration (eine Folge von Entscheidungen welche Karte oben liegt) bei der jede Zahl einmal zu sehen ist. Wenn du im Induktionsschritt A(n) => A(n+1) zeigst, dann reicht das. Das "Für alle" steckt ja dann schon im Induktionsschritt. Aber etwas anderes zu zeigen wäre Unsinn
|
||||||
|
|
Verwandte Themen
| Die Beliebtesten » |
|
| Die Größten » |
|
| Die Neuesten » |
|
