Vollst. Induktion, Geraden < Induktion < eindimensional < reell < Analysis < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 21:05 Mi 24.09.2008 | | Autor: | Teufel |
| Aufgabe | Beweisen durch vollständige Induktion:
n Geraden in einer Ebene können diese in höchstens [mm] (n^2+n+2)/2 [/mm] Teile zerlegen. |
Hi!
Habe hier ein paar Probleme.
Bin mal rückwärts rangegangen und habe herausgefunden, dass beim Hinzufügen der k-ten Gerade höchstens k neue Teilflächen hinzu kommen können. Allerdings weiß ich nicht, wie ich das zeigen kann!
Das kann man sicher auch induktiv machen, allerdings kriege ich da auch nur den Induktionsanfang hin.
Wäre für Hilfe dankbar!
![[anon]](/images/smileys/anon.png "[anon]") Teufel
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 23:34 Mi 24.09.2008 | | Autor: | Fulla |
Hallo Teufel,
du hast Recht: mit der k-ten Geraden kommen k neue Teile dazu. Das musst du nur noch in Formeln packen....
Ich denke mal, dass du mit der vollständigen Induktion vertraut bist...
Induktionsanfang: $n=1$
[mm] $\frac{1^2+1+2}{2}=2$ [/mm] Richtig, eine Gerade teilt eine Ebene in zwei Teile.
Induktionsvoraussetzung: Die Behauptung sei für $n$ Geraden schon bewiesen.
Induktionsschritt: [mm] $n\rightarrow [/mm] n+1$
Nehmen wir erstmal die ersten $n$ Geraden. Nach der Induktionsvoraussetzung teilen diese die Ebene in [mm] $\frac{n^2+n+2}{2}$ [/mm] Teile.
Wie du schon herausgefunden hast, kommen bei der $(n+1)$-ten Gerade $n+1$ Teile dazu, also sind es jetzt insgesamt
[mm] $\frac{n^2+n+2}{2}+(n+1)$ [/mm] Teile.
Diesen Term musst du jetzt nur noch ein bisschen umformen.
Lieben Gruß,
Fulla
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 23:38 Mi 24.09.2008 | | Autor: | Bastiane |
Hallo Fulla!
> Hallo Teufel,
>
> du hast Recht: mit der k-ten Geraden kommen k neue Teile
> dazu. Das musst du nur noch in Formeln packen....
>
> Ich denke mal, dass du mit der vollständigen Induktion
> vertraut bist...
>
>
> Induktionsanfang: [mm]n=1[/mm]
>
> [mm]\frac{1^2+1+2}{2}=2[/mm] Richtig, eine Gerade teilt eine Ebene
> in zwei Teile.
>
>
> Induktionsvoraussetzung: Die Behauptung sei für [mm]n[/mm] Geraden
> schon bewiesen.
>
>
> Induktionsschritt: [mm]n\rightarrow n+1[/mm]
>
> Nehmen wir erstmal die ersten [mm]n[/mm] Geraden. Nach der
> Induktionsvoraussetzung teilen diese die Ebene in
> [mm]\frac{n^2+n+2}{2}[/mm] Teile.
> Wie du schon herausgefunden hast, kommen bei der [mm](n+1)[/mm]-ten
> Gerade [mm]n+1[/mm] Teile dazu, also sind es jetzt insgesamt
Kann man das denn einfach so behaupten, dass da genau n+1 Teile hinzukommen? Oder muss man das noch irgendwie beweise oder wenigstens begründen? Mich erinnert das so ein bisschen an algorithmische Geometrie...
Viele Grüße
Bastiane
![[cap]](/images/smileys/cap.gif "[cap]")
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 23:46 Mi 24.09.2008 | | Autor: | Fulla |
Hallo Bastiane,
ich hab mir das so überlegt:
die $k$-te Gerade kann höchstens alle anderen $(k-1)$ Geraden schneiden. Es entstehen höchstens $(k-1)$ neue Schnittpunkte und $k$ neue Teile:
Wenn wir die $k$-te Gerade entlanglaufen, teilen wir zunächst ein Teil, kommen zum ersten Schnittpunkt, teilen das nächste Teil, kommen zum zweiten Schnittpunkt, .... , kommen zum $(k-1)$-ten Schnittpunkt und Teilen das letzte ($k$-te) Teil.
Ich hoffe, das war einigermaßen verständlich 
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 23:43 Mi 24.09.2008 | | Autor: | Marcel |
Hallo Fulla,
> Hallo Teufel,
>
> du hast Recht: mit der k-ten Geraden kommen k neue Teile
> dazu. Das musst du nur noch in Formeln packen....
>
> Ich denke mal, dass du mit der vollständigen Induktion
> vertraut bist...
>
>
> Induktionsanfang: [mm]n=1[/mm]
>
> [mm]\frac{1^2+1+2}{2}=2[/mm] Richtig, eine Gerade teilt eine Ebene
> in zwei Teile.
>
>
> Induktionsvoraussetzung: Die Behauptung sei für [mm]n[/mm] Geraden
> schon bewiesen.
>
>
> Induktionsschritt: [mm]n\rightarrow n+1[/mm]
>
> Nehmen wir erstmal die ersten [mm]n[/mm] Geraden. Nach der
> Induktionsvoraussetzung teilen diese die Ebene in
> [mm]\frac{n^2+n+2}{2}[/mm] Teile.
> Wie du schon herausgefunden hast, kommen bei der [mm](n+1)[/mm]-ten
> Gerade [mm]n+1[/mm] Teile dazu, also sind es jetzt insgesamt
> [mm]\frac{n^2+n+2}{2}+(n+1)[/mm] Teile.
>
> Diesen Term musst du jetzt nur noch ein bisschen umformen.
der Beweis ist natürlich richtig, es fehlt aber die Begründung, warum durch das Hinzufügen der [mm] $\black{n+1}$-ten [/mm] Gerade [mm] $\black{n+1}$ [/mm] neue Flächenstücke hinzukommen
(Übrigens, wenn man mal davon ausgeht, dass die Behauptung stimmt, kann man sich auch durch Rückwärtsrechnen überlegen, was man zu zeigen hat:
Wenn man nämlich [mm] $\frac{(n+1)^2+(n+1)+2}{2}-\frac{n^2+n+2}{2}$ [/mm] berechnet, so erhält man gerade [mm] $\black{n+1}$.)
[/mm]
Das war doch die eigentliche Frage? Die Begründung scheint darin zu liegen, dass die [mm] $\black{n+1}$-te [/mm] Gerade die [mm] $\black{n}$ [/mm] Geraden in maximal [mm] $\black{n}$ [/mm] Punkten schneiden kann. Wobei ich mir nicht ganz sicher bin, ob diese Begründung wirklich ausreicht.
Man findet sie aber auch z.B. ![[]](/images/popup.gif) hier.
Gruß,
Marcel
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 23:47 Mi 24.09.2008 | | Autor: | Fulla |
Hallo Marcel,
siehe oben
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 23:59 Mi 24.09.2008 | | Autor: | Marcel |
> Hallo Marcel,
>
> siehe oben
Hallo Fulla,
ja, ich finde, das ist eine sehr schöne elementare Begründung, warum (in meiner Formulierung) die [mm] $\black{n+1}$ [/mm] Gerade, weil sie maximal [mm] $\black{n}$ [/mm] Schnittpunkte mit den alten Geraden hat, dann auch maximal [mm] $\black{n+1}$ [/mm] neue Flächenstücke liefert.
Gruß,
Marcel
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 23:44 Mi 24.09.2008 | | Autor: | Teufel |
Hi, danke für die Antwort erstmal ;)
Ja, Induktion kenne ich (sonst könnte ich die Aufgabe ja eh nicht lösen :)).
Habe die Aufgabe auch von hinten aufgerollt, also schon n+1 eingesetzt um zu gucken, woraus ich hinarbeiten muss.
Also [mm] S=\bruch{(n+1)²+(n+1)+2}{2}=...=\bruch{n²+n+2}{2}+n+1. [/mm] Damit bin ich überhaupt drauf gekommen, dass immer eine Fläche mehr pro Gerade zu kommt (eine bei der ersten Gerade, 2 bei der 2., 3 bei der 3, ..., wie schon erwähnt).
Also ich habe alles schon rückwärts durchgekaut, hätte ich vielleicht erwähnen sollen, sorry.
Mir geht es jetzt aber darum zu zeigen, wie diese +n+1 zustande kommen, warum also die maximale Anzahl der Flächen genau so linear steigt.
Für 1, 2 und 3 Geraden ist das alles noch schön offensichtlich, danach kommt man aber mit bloßer Anschauung nicht mehr weiter (ich zumindest nicht). Die Frage für mich ist also nur: Wieso erzeugt die k-te Gerade höchstens k mehr Teilflächen? Damit wäre dann alles gelöst.
Teufel
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 23:53 Mi 24.09.2008 | | Autor: | Marcel |
Hallo Teufel,
etwas elementar schulgeometrisch-logisch (dieses Wort habe ich gerade neu erfunden, Du wirst sicher wissen, was ich meine  ) findet man, wie in meiner Mitteilung erwähnt, eine Begründung hier.
Vielleicht kann man das ja noch irgendwie so formulieren, dass es wasserdicht wird. Andererseits erscheint mir die Begründung wiederum intuitiv klar... Naja, notfalls beim Aufgabensteller nachfragen, wie genau man den Beweis zu führen hat
P.S.:
Fulla hat hier übrigens gerade doch eine schöne Überlegung mitgeliefert, warum die maximal [mm] $\black{n}$ [/mm] Schnittpunkte dann [mm] $\black{n+1}$ [/mm] neue Flächenstücke liefern.
Gruß,
Marcel
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 23:57 Mi 24.09.2008 | | Autor: | Teufel |
Jo, jetzt mit der PDF und so hat's Klick gemacht. Hätte mir vielleicht mal einen Fall mit mehreren Geraden aufzeichnen sollen... Na ja, habe die Aufgabe nur mal gefunden und habe keinen konkreten Fragesteller :) aber mir persönlich ist der Beweis jetzt wasserdicht genug.
Vielen Dank euch allen!
Teufel
|
|
|
|
