Induktivfalle

Induktives Vorgehen beim Auffinden von Gesetzmäßigkeiten ist in der Physik wie in der Mathematik verbreitet und führt oftmals, aber nicht immer, zu brauchbaren Ergebnissen. Ein Beispiel, bei dem es funktioniert, ist die Addition der Kuben aufeinander folgender natürlicher Zahlen. Dabei ergibt sich:
13=12, 13+23=32, 13+23+33=62, 13+23+33+43=102,
und die Vermutung liegt nahe, daß für jedes natürliche n gilt:
13+23+33+...+n3=dn2, wobei dn=1+2+3+...+n
die n-te der Zahlen 1,3,6,10,... ist, die, weil man sie so

veranschaulichen kann, Dreieckszahlen heißen.

Gesetzmäßigkeiten, die durch ein paar Anfangsbeispiele, d. h. unvollständig induktiv, gefunden wurden, müssen anschließend mit Hilfe der vollständigen Induktion oder auf anderem Wege allgemein bewiesen werden. Wird darauf verzichtet, gerät man unter Umständen in eine böse Falle.

Bei den Dreieckszahlen fand nach einer oft zitierten Anekdote der erst neunjährige Gauß heraus, daß sie sich für jedes natürliche n mit dem Term n(n+1)/2 viel leichter als durch stures Aufsummieren berechnen lassen. Dabei wendete er ein eigenes, nicht-induktives Verfahren an, das seinem Lehrer unbekannt war und ihn sehr beeindruckte.

Liegt ein auf analytischen oder konstruktiven Überlegungen beruhendes Beweisverfahren nicht auf der Hand und findet man auch bei angestrengtem Nachdenken nichts dergleichen, bleibt einem kaum anderes übrig, als den induktiven Weg zu versuchen. Dies soll bei der folgenden geometrischen Aufgabe geschehen:

In wieviele Teile wird die Fläche eines Kreises durch die Diagonalen eines auf dem Kreisumfang liegenden, regelmäßigen n-Ecks zerlegt?

Um für den Anfang möglichst viel Zahlenmaterial zu haben, betrachten wir dabei auch das "Eineck" und "Zweieck":

xxxxx
Bei diesen fünf Figuren ist die Antwort einfach: bedeutet n die Anzahl der Ecken, dann wird der Kreis in 2n-1 Bereiche zerlegt.

Doch Vorsicht! Beim nächsten Schritt erhält man statt der erwarteten 32 Teile nur 30 (wir haben sechs Sektoren mit fünf Feldern):
xxxxxxxxxxxxxxxxxx
Der gefundene Term 2n-1 ist für n>5 falsch – die Induktivfalle hat zugeschnappt! Wodurch muß man ihn bei beliebigem n ersetzen,
und wie läßt sich das begründen?

Hans-Jürgen


Re: Induktivfalle
von
Rebecca am Fr. 09. Januar 2004 14:33:24


Hallo Hans-Jürgen,

das ist eine sehr schöne Aufgabe, leicht zu begreifen, schwer zu lösen. Die würde gut in eine MPC passen.
Nach meinen Ergebnissen kommt für n>5 nie wieder eine Zweierpotenz vor. Beim 13-Eck kommt 456 raus, wie jeder hier leicht (*g*) nachzählen kann.

http://fed.matheplanet.com/mprender.php?stringid=3743654fed-Code ausblenden

\geo
e(700,700) xy(-1.2,1.2) form(of) nolabel()
name()
f(0,0,black)
P(0,0,M)
c(red) pen(2)
kreis(M,1,K)
c(white)
p(K,0,P1)
p(K,27.69230769,P2) p(K,55.38461538,P3) p(K,83.07692308,P4)
p(K,110.7692308,P5) p(K,138.4615385,P6) p(K,166.1538462,P7)
p(K,193.8461538,P8) p(K,221.5384615,P9) p(K,249.2307692,P10)
p(K,276.9230769,P11) p(K,304.6153846,P12) p(K,332.3076923,P13)
makro(v,c(blue)s(P%1,P%2)c(blue)s(P%1,P%3)s(P%1,P%4)s(P%1,P%5)c(blue)s(P%1,P%6)c(blue)s(P%1,P%7)s(P%1,P%8)c(blue)s(P%1,P%9)c(blue)s(P%1,P%{10})s(P%1,P%{11})s(P%1,P%{12})c(blue)s(P%1,P%{13}))
v(1,2,3,4,5,6,7,8,9,10,11,12,13)
v(2,3,4,5,6,7,8,9,10,11,12,13,1)
v(3,4,5,6,7,8,9,10,11,12,13,1,2)
v(4,5,6,7,8,9,10,11,12,13,1,2,3)
v(5,6,7,8,9,10,11,12,13,1,2,3,4)
v(6,7,8,9,10,11,12,13,1,2,3,4,5)
v(7,8,9,10,11,12,13,1,2,3,4,5,6)
v(8,9,10,11,12,13,1,2,3,4,5,6,7)
v(9,10,11,12,13,1,2,3,4,5,6,7,8)
v(10,11,12,13,1,2,3,4,5,6,7,8,9)
v(11,12,13,1,2,3,4,5,6,7,8,9,10)
v(12,13,1,2,3,4,5,6,7,8,9,10,11)
c(white)
makro(fi,k(P%1,0.02,c%1) f(c%1,white,top))
fi(1)fi(2)fi(3)fi(4)fi(5)fi(6)fi(7)fi(8)fi(9)fi(10)fi(11)fi(12)fi(13)


\geooff

geoprint(,Graphik)



Gruß
Rebecca


Re: Induktivfalle
von
Rebecca am Fr. 09. Januar 2004 15:50:54


Uups, kleiner Übertragungsfehler: 456 gilt für das 12-Eck, beim 13-Eck sind es 794.

Gruß
Rebecca


Re: Induktivfalle
von
Rebecca am Fr. 09. Januar 2004 15:56:02


Hi,

die Aufgabe kann man noch modifizieren: Berechnung nicht für ein regelmäßiges n-Eck, sondern für ein beliebiges konvexes Polygon im Kreis.
Zusatzfrage: wenn n ungerade ist, ist in beiden Fällen das Ergebnis gleich; warum ???

Gruß
Rebecca


Re: Induktivfalle
von
Hans-Juergen am Fr. 09. Januar 2004 18:47:26 http://www.hjcaspar.de/hpxp/anfang.htm


Hallo Rebecca,

die Ausdehnung der Aufgabe auf beliebige, unregelmäßige Polygone ist sicher möglich, nur wird dabei das Abzählen zur Kontrolle bei größerem n sehr mühselig und geht bei regelmäßigen N-Ecken bis n=13 leichter, wie Deine schöne Graphik zeigt.

Hinsichtlich Deiner Zusatzfrage denke ich folgendes: bei ungeradem n gibt es im Innern des N-Ecks anscheinend keine Punkte, in dem sich mehr als zwei Diagonalen schneiden, während dies bei geradem n der Fall ist. Wegen der Achsensymmetrie ist die Kreismitte ein solcher Punkt.

Macht man nun bei geradem n aus einem regelmäßigen Vieleck durch Verschieben eines Punktes auf dem Kreisumfang ein unregelmäßiges, so kann es sein, daß aus einem Punkt, in dem sich mehr als zwei Diagonalen schneiden, ein Dreieck wird; dann gibt es eine Fläche mehr als beim regelmäßigen N-Eck. Dies sieht man sehr schön bei n=6:
Bild
regelmäßig: 30 Flächen
Bild
unregelmäßig: 31 Flächen.

Viele Grüße,
Hans-Jürgen


Re: Induktivfalle
von
Hans-Juergen am Sa. 10. Januar 2004 09:43:16 http://www.hjcaspar.de/hpxp/anfang.htm


Unsere durch Abzählen erhaltene Folge für regelmäßige Vielecke: 1,2,4,8,16,30 ist in der
Online-Enzyklopädie der Zahlenfolgen (früher: Sloanes Enzyklopädie ...) enthalten und wird dort fortgesetzt mit 57, 88, 163, 230, 386, 456, 794, 966, … mit der Aufgabenstellung: "Join n equal points around circle in all ways, count regions."

Begründet wird die Folge nicht, doch wenn man auf einen der angegebenen Links klickt, gibt es noch den Hinweis:

"We give a formula for the number of interior intersection points made by the diagonals of a regular n-gon.
The answer is a polynomial on each residue class modulo 2520. We also compute the number of regions formed by the diagonals, by using Euler's formula V - E + F = 2." Darin bedeuten: V=vertex=Ecke, E=edges=Kanten, F=faces=Flächen; gemeint sind jeweils deren Anzahlen. Auf deutsch schreibt man für sie: e-k+f=2. e bedeutet die Ecken des Polyeders, k seine Kanten. (Beispiel Tetraeder: e=4, k=6, f=4; 4-6+4=2.)

Wie man die Eulersche Formel auf ebene Polygone überträgt, wird u. a. hier erklärt. Die Kanten des Polyeders werden zu Strecken, seine Ecken zu Punkten.
Durch Auszählen der auf der Seite angefügten Beispiele ergibt sich, dass für sie gilt:

e-k+f=1    (1)

mit 1 auf der rechten Seite statt der 2 im räumlichen Fall. (1) erhält man auch bei den aus unseren einleitenden gewonnenen Figuren ab dem Dreieck:


Allgemein, nicht nur anhand weiterer Beispiele, wird die Gültigkeit von (1) hier auf dem Matheplaneten untersucht.


Re: Induktivfalle
von
Hans-Juergen am Do. 29. Januar 2004 17:30:08

 

Hi,

im folgenden skizziere ich eine Teillösung der obigen,
ursprünglichen Aufgabe und betrachte dazu als erstes das
regelmäßige 7-Eck:

http://matheplanet.com/matheplanet/nuke/html/img/hj/induktivc/7eck.gif

Die Diagonale 0→2 wird von anderen Diagonalen 4-mal,

die Diagonale 0→3 6-mal,

die Diagonale 0→4 6-mal,

die Diagonale 0→5 4-mal

geschnitten. Zusammen ergibt das 20 Schnittpunkte. Da die übrigen 6 Eckpunkte
mit dem Eckpunkt 0 gleichberechtigt sind, bekäme man durch Multiplikation mit n=7
insgesamt 140 Diagonalenschnittpunkte. Das aber wären viel zu viele, da bei
diesem Vorgehen alle Schnittpunkte mehrfach gezählt werden. Das regelmäßige
7-Eck hat insgesamt nur 35 Diagonalenschnittpunkte, und man muß, um auf diese Anzahl zu kommen, die erhaltenen 140 noch durch 4 dividieren.

Dasselbe machen wir zur Kontrolle mit dem regelmäßigen 5-Eck. Hier ergeben sich
sinngemäß (2+2)*5/4=5 Diagonalenschnittpunkte:

Bild
und beim regelmäßigen Neuneck

http://matheplanet.com/matheplanet/nuke/html/img/hj/induktivc/9eck.gif


sind es (6+10+12+12+10+6)*9/4=126. (Das Nachzählen wird langsam etwas mühselig.http://matheplanet.com/matheplanet/nuke/html/img/hj/induktivc/angestrengt.gif)

Die Zahlen 5,35,126 beim Fünf-, Sieben- und Neuneck kommen im Pascalschen Dreieck vor:

1

1 1

1 2 1

1 3 3 1

1 4 6 4 1

1 5 10 10 5 1

1 6 15 20 15 6 1

1 7 21 35 35 21 7 1

1 8 28 56 70 56 28 8 1

1 9 36 84 126 126 84 36 9 1.

Es sind die Binomialkoeffizienten

http://matheplanet.com/matheplanet/nuke/html/img/hj/induktivc/binko1.png

Anschaulich begründen läßt sich das so: Jeder Diagonalenschnittpunkt entsteht durch Schnitt zweier Strecken, die durch je 2, insgesamt also 4 Eckpunkte des n-Ecks festgelegt sind.
4 Objekte lassen sich aber aus n Objekten auf n über 4 Arten auswählen.

Voraussetzung hierbei ist, daß nur Polygone betrachtet werden, bei denen jeder Diagonalenschnittpunkt von nicht mehr als zwei Diagonalen gebildet wird.

Deshalb lassen wir das regelmäßige 6-, 8-, 10-,...-Eck außeracht, nehmen aber das Quadrat noch mit hinzu.

Es ist also die Anzahl der Diagonalenschnittpunkte gleich


und wenn man die Eckpunkte des Vielecks mit hinzunimmt, folgt


Die Anzahl k der Kanten ist ebenfalls nicht schwer zu ermitteln. Wie oben gehen wir von einem festen Startpunkt aus und sehen nun nach, in wieviele Teile die jeweiligen Diagonalen von anderen zerschnitten werden. Es ist jedesmal einer mehr, als es Diagonalenschnittpunkte gibt, und so läßt sich herausfinden, daß gilt:

http://matheplanet.com/matheplanet/nuke/html/img/hj/induktivc/binko3.png

(Zu k rechnen auch die Seiten des n-Ecks.)
[Probe: n=5:   k=2·5+5·4/2=20 wie oben beim Fünfeck.]

Damit und mit Gl. (1) erhält man die Anzahl f der Teilflächen des n-Ecks zu

http://matheplanet.com/matheplanet/nuke/html/img/hj/induktivc/binko4.png

und wenn im Sinne der ursprünglichen Aufgabe noch die das n-Eck umgebenden Kreissegmente hinzugenommen werden:


==================================================================

Hiermit kann man Rebeccas Angabe bestätigen, daß der Kreis mit einbeschriebenem 13-Eck 794 Teilflächen besitzt.

Die für n = 4, 5, 7, 9, 11, 13, ... erhältlichen Zahlen f ' = 8, 16, 57, 163, 386, 794, ... sind auch in der Folge bei Sloane enthalten.

Hans-Jürgen


Re: Induktivfalle
von
Rebecca am Do. 29. Januar 2004 18:04:52


Hi Hans-Jürgen,

danke für deine schöne Lösung, ich hatte damals als Ergebnis
http://fed.matheplanet.com/mprender.php?stringid=647488fed-Code ausblenden

1+(n^4-6n^3+23n^2-18n)/24

erhalten, weil ich nicht - wie du - an die Binomialkoeffizienten gedacht hatte.

Gruß
Rebecca



Zurück zur Themenübersicht