Kreis in Flächen unterteilen

geschrieben am 03.04.2014 17:48:51
( Link )
Ich bräuchte mal eure Hilfe bei einem Beweis für Mathe.

Situation:
Wenn man drei Punkte auf einem Kreis anbringt und sie alle mit geraden Linien verbindet, entstehen vier Flächen.
Vier Punkte auf einem Kreis erzeugen acht Flächen, fünf Punkte sechzehn Flächen.
Problem: Sechs Punkte erzeugen einunddreißig Flächen und sieben Punkte siebenundfünfzig.

Allgemein gilt die Formel:
Anzahl Flächen = (n über 4) + (n über 2) + 1 (wenn n die Anzahl der Punkte auf dem Kreisrand ist)

Aufgabe:
Erkläre wie die Formel zustande kommt. (Mit vollständiger Induktion)


Zum besseren Verständnis hier mal eine Tabelle wie viele Schnittpunkte, Flächen und Geraden bei n Punkten auf dem Kreisrand entstehen:
Punkte auf dem Kreisrand ; Flächen im Kreis ; Schnittpunkte im Kreis ; Gerade Linien die Punkte verbinden

0 ; 1 ; - ; -
1 ; 1 ; - ; -
2 ; 2 ; - ; 1
3 ; 4 ; - ; 3
4 ; 8 ; 1 ; 6
5 ; 16 ; 5 ; 10
6 ; 31 ; 15 ; 15
7 ; 57 ; 35 ; 21
8 ; 99 ; 70 ; 28
9 ; 163 ; 128 ; 36
10 ; 256 ; 210 ; 45


Was ich rausgefunden habe, dass das (n über 4) die Anzahl der Schnittpunkte beschreibt die entstehen und dass (n über 2 die Anzahl der Geraden), aber ich hab keinen Schimmer, wie dass hilft, die Anzahl der Flächen im Kreis zu ermitteln oder wo die +1 herkommt.

Ich hoffe ihr habt ein paar Ideen, oder habt von diesem Problem schon mal gehört
geschrieben am 03.04.2014 21:45:18
( Link )
So wie ich das sehe, brauchst du die Formel nicht mal zu verstehen - stumpf beweisen reicht.
Erst zeigst du, dass die Formel für einen "Basisfall" gilt (ich schätze, da nimmt man n=4), und dann zeigst du, unter Annahme, dass sie für ein beliebiges n gilt, dass sie auch für n+1 gilt.

(Ich hätte dir auch gerne beim Beweisen geholfen, aber ich bin zu müde für rigoroses Umformen.)
geschrieben am 03.04.2014 23:49:16
( Link )
Blergh, vollständige Induktion! >_<
Da habe ich schon in so ziemlich jeder Arbeit und in der Abitur-Prüfung verkackt. Zwar verstehe auch ich durchaus den grundlegenden Ablauf - erst die Gleichung für ein beliebiges n ausrechnen und dann beweisen, dass die Formel auch für n + 1 gilt, wenn sie für n gilt - aber bei der Umsetzung scheitere ich jedes mal. Ich bekomme einfach nie den Umwandlungsschritt von n nach n + 1 hin, egal, wie ich es versuche. Ich weiß eigentlich auch nie so recht, wie ich da anfangen soll.

Also... blergh!
Da wird dir wohl der gute alte spinatkuchen helfen müssen (oder aber WYE, sobald er ausgeschlafen ist).
-Das quadratische Rad neu erfinden-
Mit das quadratische Rad neu erfinden (englisch Reinventing the square wheel) bezeichnet man die Bereitstellung einer schlechten Lösung, wenn eine gute Lösung bereits existiert.

-Slowsort-
Slowsort (von engl. slow: langsam) ist ein langsamer, rekursiver Sortieralgorithmus, der nach dem Prinzip Vervielfache und kapituliere (engl. Multiply and surrender, eine Parodie auf Teile und herrsche) arbeitet.

geschrieben am 04.04.2014 18:30:48
( Link )
Naja, ich dachte dafür, dass ich die vollständige Induktion anwenden kann muss ich die Formel verstehen, aber mal schauen.

Formel: (n über 4) + (n über 2) + 1 = max. Anzahl Flächen

Induktionsanfang: n=4
(4 über 4) + (4 über 2) + 1 = 8

Induktionsannahme: n=k
(k über 4) + (k über 2) + 1 = max. Anzahl Flächen

Induktionsschritt: Zu zeigen: n=k+1
((k+1) über 4) + ((k+1) über 2) + 1 = Und jetzt stellt sich hier für mich die Frage zu was das gleich ist, damit man Umformen kann.
geschrieben am 04.04.2014 19:33:47
( Link )
Stimmt, jetzt dämmert's mir - ich glaube, du musst einen weiteren Weg finden, die Anzahl der Flächen zu ermitteln, und dich darauf dann im Induktionsschritt beziehen. Ja, dann muss man die Formel tatsächlich auch verstehen.

Angenommen, du hättest so einen zweiten Weg gefunden, nennen wir ihn F(n) für die Anzahl der Flächen bei n Punkten. Dann sähe deine Induktion so aus:
Induktionsannahme: F(k) = (k 2) + (k 4) + 1
Induktionsschritt: F(k+1) = [irgendwas, in dem F(k) vorkommt] = [weitere Umformungen] = (k 2) + (k 4) + 1
Wie du F(k+1) in eine Form kriegst, in der F(k) vorkommt, das ist der große Trick. Damit die Induktion klappt, muss man sich immer irgendwie auf das vorherige beziehen können. Da braucht's einen Geistesblitz, und den hab ich gerade nicht.

Wahrscheinlich hab ich mindestens ein bisschen falsch gedacht oder erklärt, und spinatkuchen wird uns alle deswegen verhauen, aber so ist mein momentaner WIssensstand.
geschrieben am 05.04.2014 18:52:06
( Link )
Doch, du hast genau das gesagt, was ich eigentlich ausdrücken wollte.

Mir fehlt nur genau wie dir der Geistesblitz.
geschrieben am 22.06.2014 20:23:05
( Link )
Wie lautet jetzt eigentlich die Lösung?
geschrieben am 27.06.2014 13:04:23
( Link )
Also ich kann dir die Formel herleiten und somit kann ich die explizite Formel auch nachvollziehen.
Hat auf der eulerschen Polyederformel e+f=k+1 beruht.
Ich kenne aber nach wie vor keine rekursive Formel und somit ist eine Induktion ja nicht möglich.
Desweiteren weiß ich mittlerweile, dass das Ganze das Punkt-Kreis-Problem von Leo Moser ist und es auch noch einen Zusammenhang mit dem Pascalschen Dreieck gibt, welcher sehr interessant ist, aber auch nur in meinen Augen zur expliziten Formel führt.

Da mein Mathelehrer wie sich rausgestellt hat, aber keine Ahnung hat und er nicht mal die explizite Formel kannte werden wir das mit der Induktion wohl nie hinbekommen :/