Suche nach Induktionshypothese

Neue Frage »

Shizmo Auf diesen Beitrag antworten »
Suche nach Induktionshypothese
Hallo, ich habe hier eine Aufgabe:

Zitat:
Maria hat ein (nicht notwendigerweise konvexes) Vieleck auf Papier gezeichnet und ausgeschnitten. Nun aber fällt ihr ein, dass sie Dreiecke ja viel lieber mag. Daher will sie dieses Vieleck entlang einer Diagonalen (von Eckpunkt zu Eckpunkt) in zwei Teile schneiden und diesen Prozess solange mit den neuen Teilen wiederholen bis nur noch Dreiecke vorhanden sind. Da Maria unnötige Arbeit gerne vermeiden würde, sucht sie nach der minimalen Anzahl der Schnitte, die sie für ein n-Eck braucht. Uberzeugen Sie Maria mit Hilfe eines mathematisch formal korrekten Beweises, dass, egal wie sie schneidet, immer gleich viele Schnitte benötigt werden. Wieviele sind es? (Dass jedes Vieleck mindestens eine Diagonale hat, entlang derer man schneiden kann, durfen Sie vorraussetzen.)


Also ich hab herausgefunden, wenn n die Ecken sind, dann braucht man für alle n > 3 : n - 3 Schnitte.
Die Aufgabe sollen wir mit Induktion beweisen.

Allerdings weiß ich grad nicht was ich zeigen soll... unglücklich
Elvis Auf diesen Beitrag antworten »

IA: trivial für n=3
IS: n+1-Eck einmal schneiden, Reste haben höchstens n Ecken. Aus IV folgt Behauptung.

(Tut mir leid, das war zu einfach. Weniger Hinweise sind mir nicht möglich.)
HAL 9000 Auf diesen Beitrag antworten »

Zitat:
Original von Elvis
Reste haben höchstens n Ecken. Aus IV folgt Behauptung.

Kurz und knapp. Augenzwinkern

Vielleicht sollte man noch erwähnen, dass die IV hier zweimal angewandt wird, auf jedes der beiden Reste je einmal. Und dass es weniger ein Induktionsschritt als vielmehr ist, so wie hier (1.Teil des Beitrags) beschrieben.
Elvis Auf diesen Beitrag antworten »

Genau so ist es, das ist eine der vielen Möglichkeiten der vollständigen Induktion. Shizmo darf auch noch darüber nachdenken, warum ein einmal zerschnittenes n+1-Eck in 2 Vielecke mit nicht mehr als n Ecken zerfällt.
(Kurz und knapp: "Das sagt mir meine mathematische Intuition." Den Spruch wollte ich schon immer mal loswerden.)
Shizmo Auf diesen Beitrag antworten »

Erstmals vielen Dank für eure Beiträge, steht grad auf dem Schlauch.
Ich suche immer noch nach dem Ziel bzw. was ich überhaupt beweisen soll.
Also ich meine, mit Induktion kann ich Gleichungen, Ungleichungen,... beweisen, was beweise ich hier? Dass Maria immer n-3 Schnitte braucht, ja aber was ist mit dem n-3 (ich habe weder eine Gleichung, noch sonst was)... verwirrt


@HAL 9000: Danke für den Tipp, wenn man die Hypothese für alle anwenden darf, dann haben wir das "starke Induktion" genannt, allerdings wird die Hypothese dann anders formuliert.
HAL 9000 Auf diesen Beitrag antworten »

Zitat:
Original von Shizmo
was beweise ich hier? Dass Maria immer n-3 Schnitte braucht

Eben das sollst du beweisen!!!

Zitat:
Original von Shizmo
(ich habe weder eine Gleichung, noch sonst was)

Du hast Schnitte, die du zählen kannst (und sollst).
 
 
Shizmo Auf diesen Beitrag antworten »

Tut mir leid, ich bin zu doof und komm nicht drauf, kann mir vielleicht jemand die Induktionshypothese formulieren?
HAL 9000 Auf diesen Beitrag antworten »

Du redest jetzt über Dinge, über die doch schon lange Klarheit hier im Thread herrscht, oder? Erstaunt1

Die Induktionshypothese hast du doch selbst schon lange formuliert:

Zitat:
Original von Shizmo
wenn n die Ecken sind, dann braucht man für alle n > 3 : n - 3 Schnitte.
Shizmo Auf diesen Beitrag antworten »

Hmm, sollte die nicht so ausschauen:

n - 3 = ....

oder

n - 3 > ...

oder so ähnlich?

Denn was soll ich denn so bei der Basis zeigen? n = 4 und 4 - 3 = 1 und jetzt? Für was gilt das?
HAL 9000 Auf diesen Beitrag antworten »

Ja von mir aus kannst du dir Anzahl der nötigen Schnitte mit bezeichnen, dann lautet die zu beweisende Behauptung (oder wie du es nennst: Induktionshypothese) eben .

Damit deine übermächtige Sehnsucht nach einer Gleichungsformulierung der Behauptung gestillt ist. Big Laugh
Shizmo Auf diesen Beitrag antworten »

Big Laugh Big Laugh

Wie zeige ich denn die "nötigen Schritte"?

Ist das wie eine "normale, einfache" Induktion (sowie bei Summenformeln, etc.) oder muss man die irgendwie textuell lösen? (Falls ja, dann wunderts mich nicht, warum ich nichts kapier, weil sowas habe ich noch nie gemacht Big Laugh )
Elvis Auf diesen Beitrag antworten »

Du hast die Hypothese aufgestellt, dass für ein n-Eck genau n-3 Schnitte benötigt werden, um es in 3-Ecke zu zerlegen. Ich habe gezeigt, wie die vollständige Induktion gemacht wird. Der Induktionsanfang (IA) ist trivial und der Induktionsschritt (IS) wird durch einen Schnitt realisiert. Wenn man ein n+1-Eck einmal zerschneidet, bleiben 2 Vielecke (m-Eck und k-Eck) übrig, und es ist m<n+1,k<n+1. Mit ein bißchen Fleiß kann man sich die Details über n,m,k überlegen, und es ist zu zeigen, dass m-3+k-3+1=n+1-3 gilt. Wenn dir die rein geistige Erforschung des Problems zu schwierig erscheint, dann nimm ein paar Blatt Papier und Bleistift, zeichne n+1-Ecke und zerschneide von einer Ecke zu einer anderen und zähle die Ecken der beiden m-Ecke und k-Ecke.

Wenn dir dies immer noch zu schwierig erscheint, dann schneide im IS ein Dreieck ab und schaue was übrigbleibt. Schneide ein 4-Eck, 5-Eck, ... ab, und schaue was übrigbleibt.

Ja, das ist eine ganz normale vollständige Induktion. Das ist ein mächtiges Werkzeug in der Mathematik und nicht nur ein billiger Taschenspielertrick. Die vollständige Induktion ist zu recht ein Axiom der Peano-Axiome der natürlichen Zahlen.
Shizmo Auf diesen Beitrag antworten »

Vielen Dank für deine Antwort (und eure Geduld Big Laugh )

Die geistige Erforschung ist mir nicht zu schwierig, dass ist mir schon klar, ich bin nur nicht ganz sicher, wie ich das mathematisch korrekt niederschreibe.

LG
Elvis Auf diesen Beitrag antworten »

Immer noch nicht fertig ? Dann gebe ich dir gerne noch einen Hinweis.
Nimm ein n+1-Eck und zerschneide es ein mal so, dass es in zwei Vielecke zerfällt. Wie viele Ecken hat das n+1-Eck ? Wie viele Ecken haben die beiden Vielecke zusammen ? Zerlege das m-Eck und das k-Eck, wie viel Schnitte braucht die Zerlegung ? Addiere den ersten Schnitt dazu. Noch ein Tipp: nicht nur im Geiste schneiden, sondern ein 5-Eck und ein 6-Eck schneiden und richtig praktisch wirklich n=...,m=...,k=... aufschreiben. Richtig praktisch wirklich aufschreiben ist "mathematisch korrekt".
Shizmo Auf diesen Beitrag antworten »

Ich habs mal traumhaft gezeichnet Big Laugh

Auch fällt auf, dass man durch Schneiden immer n-2 Dreiecke bekommt.

Ok also:

IB: n = 3 -> n-3 = 0 -> Klar, ein Dreieck muss man nicht schneiden.

IH: Für ein beliebiges aber fixes n (n in N) braucht man immer n-3 Schnitte.

IS: (n -> n+1)
Du hast mal gesagt, dass das hier zz wäre: m-3+k-3+1=n+1-3 ? Die Gleichung stimmt, jedoch woher kommt die Idee, diese so anzusetzen.
...

//Auch hat unser Prof gesagt, wenn man die IH im I-Schritt nirgendwo einsetzt, stimmt die Induktion nicht.

Also lt. deiner Aussage würde ich die IH so definieren:
Für ein beliebiges aber fixes n (n in N): n-3 = m-3+k-3 Also gezeigt!

IS: (n -> n+1)
zz n+1-3 = m-3+k-3+1

(m-3+k-3)+1 =(laut IH)= (n-3)+1 = n+1-3
Elvis Auf diesen Beitrag antworten »

Zitat:
Original von Elvis
Wie viele Ecken hat das n+1-Eck ? Wie viele Ecken haben die beiden Vielecke zusammen ?

Diesen Hinweis hast du noch nicht benutzt. Ich gebe dir noch eine Chance. Wenn du möchtest, kommt morgen mein Beweis.
Shizmo Auf diesen Beitrag antworten »

Die Ecken erhöhen sich immer um 2.

Zitat:
Original von Elvis
[...]
Wenn du möchtest, kommt morgen mein Beweis.


Das wär super!!
Elvis Auf diesen Beitrag antworten »

Genau, die Ecken erhöhen sich immer um 2, weil die Ecken eines Diagonalschnitts nach dem Schneiden in beiden Vielecken gezählt werden. Nun sieht der Indusktionsschritt wie folgt aus:

Ecken (schnitt) Ecken
(zerlege (Induktionsvoraussetzung)) (schnitte)
(schnitte)
Shizmo Auf diesen Beitrag antworten »

Vielen Dank für deine Antwort, bin jetzt alles nochmal durchgegangen, habe alles nochmal schön aufgeschrieben und denke, dass ich es jetzt nun doch endlich noch kapiert habe Big Laugh

Vielen Dank!

LG
Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »