Mathematik: Täuschend einfach
Released by matroid on So. 03. März 2002 13:44:53 [Statistics]
Written by matroid - 5459 x read [Outline] Printable version Printer-friendly version -  Choose language   
Mathematik

\(\begingroup\)\(\newcommand{\IX}{\mathbb{X}} \newcommand{\IW}{\mathbb{M}} \newcommand{\politician}[1]{\text{Ich habe die Frage nicht verstanden. #1}} \newcommand{\ba}{\begin{aligned}} \newcommand{\ea}{\end{aligned}} \newcommand{\bpm}{\begin{pmatrix}} \newcommand{\epm}{\end{pmatrix}} \newcommand{\bc}{\begin{cases}} \newcommand{\ec}{\end{cases}} \newcommand{\on}{\operatorname} \newcommand{\ds}{\displaystyle}\)
Sehnen zwischen 7 Punkten teilen Kreis in Gebiete Auf einem Kreis seien n Punkte gegeben.
Je zwei Punkte seien durch eine gerade Linie verbunden.
Durch die Linien wird das Innere des Kreises in Gebiete unterteilt.

Wie groß ist (höchstens) die Anzahl der Gebiete?


 

Mit nur einem Punkt kann keine Sehne gezeichnet werden. Die Anzahl der Gebiete ist 1. Mit 2 Punkten sind es 2 Gebiete. Mit dreien 4, bei 3 Punkten 8 Gebiete. Für 5 Punkte zählen wir 16 Gebiete.

Sehr schön! Die Vermutung lautet: Die Anzahl der Gebiete ist gleich 2n-1, n die Anzahl der Punkte.

Bild 1 Bild 2 Bild 3 Bild 4 Bild 5

Beweisskizze, induktiv (aber falsch): Von jedem weiteren Punkt werden Sehnen zu allen anderen Punkten gezogen. Die Anzahl der Sehnen ist n. Jede Sehne teilt ein vorhandenes Gebiet in 2 Teile.
Das ist aber falsch. Bild 6 Die Anzahl der Gebiete für n=6 ist höchstens 31 (siehe Bild).

Wie ist die richtige Lösung?

Wenn je zwei Sehnen verschiedene Schnittpunkte haben, dann ist die Anzahl der Gebiete gleich
binomial(n,4) + binomial(n,2) + 1
binomial(n,k) schreibe ich für den Binomialkoeffizienten "n über k". Das ist die Anzahl der verschiedenen Auswahlen von k Elementen aus n Elementen, ohne Unterscheidung der Reihenfolge der gewählten Elemente.

Sofern es 3 Sehnen gibt, die sich in einem Punkt schneiden, ist die Anzahl der Gebiete kleiner.

Zum Beweis

Ich werde zuerst eine Rekursionsformel für die gesuchte Anzahl herleiten und damit die genannte Formel induktiv beweisen. Sehnen zwischen 8 Punkten teilen Kreis in Gebiete Die vorstehende Abbildung soll die Gedankengänge anschaulich machen.

Die Abbildung zeigt einen Kreis mit 8 Punkten. Der rote Punkt ist neu hinzugekommen. Wie man sieht, gibt es Gebiete, die von den neuen Sehnen mehrfach geteilt werden und es gibt Gebiete, die von den neuen Sehnen nicht geteilt werden.
Je 'weiter' eine zuvor vorhandenes Gebiet von dem neuen Punkt entfernt ist, desto weniger neue Sehnen schneiden hindurch, und unter den Gebieten, die gleich weit von dem neuen Punkt entfernt sind, werden mit zunehmenden Abstand immer weniger von den neuen Sehnen durchschnitten.

Der Begriff des 'Abstands' eines Gebietes von dem neuen Punkt, kann definiert werden, durch die Anzahl der bestehenden Sehnen, die man ausgehend von dem roten Punkt kreuzen muß, um in dieses Gebiet zu gelangen (auf gerade Weg). In der Abbildung habe ich Gebiete mit gleichen Farben gefüllt, wenn sie von einer roten Sehne durchschnitten werden und 'gleich weit' von der roten Ecke entfernt sind.

Aber nicht dieses Farbpuzzle, sondern das Zählen der neuen Sehnenschnittpunkte führt zur gesuchten Rekursion.

Betrachte im Bild die Anzahl der roten Sehnen, die die vorhandenen (blauen) Sehnen schneiden.

2 neue Sehnen schneiden keine vorhandene Sehne.
1 vorhandene Sehne wird von 5 neuen Sehnen geschnitten.
2 vorhandene Sehnen werden von 4 neuen Sehnen geschnitten.
3 vorhandene Sehnen werden von 3 neuen Sehnen geschnitten.
4 vorhandene Sehnen werden von 2 neuen Sehnen geschnitten.
5 vorhandene Sehnen werden von 1 neuen Sehnen geschnitten.
6 vorhandene Sehnen werden von 0 neuen Sehnen geschnitten.

Wenn man die neuen Sehnen durchläuft, und keine 2 Schnittpunkte verschiedener Sehnenpaare gleich sind, dann betritt man mit jedem Schnittpunkt ein Gebiet und teilt es. Außerdem wird das Gebiet, in dem der hinzugefügte, rote Punkt liegt, von den neuen n Sehnen genau n mal durchschnitten, sodaß n neue Gebiete entstehen.

Im Bild zählt man

1*5 + 2*4 + 3*3 + 4*2 + 5*1
= 5 + 8 + 9 + 8 + 5 = 35 neue Schnittpunkte.
Bezeichne mit a(n) die Anzahl der Gebiete, in die das Innere eines Kreises durch die Sehnen zwischen n Punkten auf der Peripherie des Kreises geteilt wird (sofern alle Schnittpunkte zweier Sehnen verschieden sind).
Es gilt: a(n) = a(n-1) + n-1 + T(n-1)

mit T(n) := Sk=1n-1 k*(n-1-k)

bzw. T(n) = Sk=0n-2 (k+1)*(n-2-k)

Beispiel:
a(6) = a(5) + T(5) + 5
T(5) = Sk=14 k*(4-k)
= 1*3 + 2*2 + 3*1 + 4*0 = 10
=> a(6) = a(5) + 10 + 5 = 16 + 15 = 31

und mit T(6) = 1*4 + 2*3 + 3*2 + 4*1 + 5*0 = 20
=> a(7) = a(6) + 20 + 6 = 31 + 26 = 57

Hilfssatz:
Die Anzahl der Schnittpunkte aller Sehnen zwischen n gegebenen Punkte auf einem Kreis und den Sehnen von einem weiteren Punkt auf dem Kreis zu diesen n Punkten ist
T(n) := Sk=0n-2 (k+1)*(n-2-k)
[sofern verschiedene Sehnenpaare verschiedene Schnittpunkte haben].

Beweis des Hilfssatzes: Jede Sehne verläuft zwischen 2 Punkten auf dem Kreis.
Von jedem der beiden Punkte zähle die Anzahl der anderen gegebenen Punkte, die man von dem Punkt - in der Richtung, die nicht über den anderen Endpunkt der Sehne führt, - entlang der Peripherie des Kreises bis zum neuen, roten Punkt durchlaufen muß.
Ordne jeder Sehne die Summe der Anzahlen der Punkte zwischen ihren beiden Endpunkten zum zusätzlichen Punkt zu (ohne dabei den anderen Endpunkt der Sehne zu durchlaufen). Diese Anzahl nenne ich den Abstand der Sehne vom neuen Punkt oder kurz den Abstand der Sehne.

Der größte Abstand, den eine Sehne haben kann, ist n-2, denn von den n gegebenen Punkten können höchstens n-2 zwischen den Endpunkten der Sehne und dem neuen Punkt liegen.

Es gibt eine Sehne mit Abstand 0.
Es gibt zwei Sehnen mit Abstand 1.
Allgemein gibt es m+1 Sehnen mit Abstand m (< n-2 = der Anzahl der vorhandenen Ecken), weil eine Sehne den Abstand m hat, wenn ihre beiden Endpunkte in Summe m Punkte von der zusätzlichen Ecke entfernt liegen.
Es gibt m+1 Möglichkeiten die Zahl m in nichtnegative Summanden zu zerlegen, nämlich m = 0 + m, m = 1 + (m-1), ... , m = (m-1) + 1, m = m + 0.
Wir bilden eine disjunkte Zerlegung aller vorhandenen Sehnen in Teilmengen mit Sehnen gleichen Abstands zum neuen Punkt.

Die Aufteilung aller vorhandenen Sehnen in solche Teilmengen ist disjunkt, da der Abstand einer Sehne eindeutig ist, aber ist diese Aufteilung auch vollständig?
Ja, denn zwischen den vorhandenen n Punkten gibt es binomial(n,2) Sehnen in dem Kreis.
Andererseits ist
Sm=0n-2 m+1 = Sm=1n-1 m = n*(n-1)/2 = binomial(n,2).
Jede Sehne befindet sich also in einer der Teilmengen.

Nun zeige ich, daß eine Sehne mit Abstand m von genau n-2-m neuen, roten Sehnen geschnitten wird.
Wenn nämlich eine Sehne den Abstand m hat, m £ n-2, dann teilt diese Sehne den Kreis in 2 Teile.
In dem einen Teil liegt der neue, rote Punkt.
In dem anderen Teil liegen n-2-m andere Punkte. Von dem neuen Punkt verlaufen zu den Punkten im anderen Teil des Kreises genau n-2-m Sehnen. Alle diese Sehnen schneiden die eine Sehne, die wir gerade betrachten.

Wir haben gezeigt:
a. Es gibt m+1 Sehnen mit Abstand m, 0 £ m £ n-2.
b. Sehnen mit Abstand m werden von n-2-m neuen Sehnen geschnitten.
=> Die Anzahl der Schnittpunkte der neuen Sehnen mit den alten Sehnen zwischen n Kreispunkten ist gleich T(n) = Sk=0n-2 (k+1)*(n-2-k).
Qed für den Hilfssatz.

Für T(n) können wir eine andere Darstellung finden, wenn wir die Summe zerlegen und die bekannten Formeln für die Summe oder die Quadratsumme von Zahlen anwenden:
=> T(n) = binomial(n,3)

Dann gilt: a(n) = a(n-1) + n-1 + binomial(n-1,3)

Nun können wir abschließend zeigen,
daß a(n) = binomial(n,4) + binomial(n,2) + 1

Beweis mit Induktion, für n>3:
Induktionsanfang: a(4) = 1 + 6 + 1,
a(5) = 5 + 10 + 1 = 16
Zeige nun, daß aus der Gültigkeit der Formel für n die Formel auch für n+1 folgt.

a(n+1) = a(n) + n + binomial (n,3)
= binomial(n,4) + binomial(n,2) + 1 + n + binomial(n,3)
= binomial(n,4) + binomial(n,2) + 1 + n + binomial(n,3)
= binomial(n+1,4) - binomial(n,3) + binomial(n+1,2) - binomial(n,1) + 1 + n + binomial(n,3)
= binomial(n+1,4) + binomial(n+1,2) - n + 1 + n
= binomial(n+1,4) + binomial(n+1,2) + 1
QED.

Referenzen:
mathworld.wolfram.com
Folge a(n) bei Sloane's: A000127
Tetraederzahlen bei Sloane's: A000292

Anmerkungen: T(n) = binomial(n,3) Kugeltetraeder werden auch als Tetraederzahlen bezeichnet, denn T(n) ist die Anzahl von Kugeln in einem Tetraeder mit 3 Ebenen von Kugeln, 6 in einem Dreieck auf dem Boden, 3 darüber und 1 in der Spitze. T(n) ist die Anzahl der Kugeln in einem Kugeltetraeder mit Seitenlänge n Kugeln.

Trennlinie

Matroid 2002

\(\endgroup\)
Get link to this article Get link to this article  Printable version Printer-friendly version -  Choose language     Kommentare zeigen Comments  
pdfFür diesen Artikel gibt es keine pdf-Datei


Arbeitsgruppe Alexandria Dieser Artikel ist im Verzeichnis der Arbeitsgruppe Alexandria eingetragen:
: Mathematik :: Kombinatorik :: Binomialkoeffizienten :: Kreisflächen :: Leicht verständlich :
Täuschend einfach [von matroid]  
Auf einem Kreis seien n Punkte gegeben. Je zwei Punkte seien durch eine gerade Linie verbunden. Durch die Linien wird das Innere des Kreises in Gebiete unterteilt. Wie groß ist (höchstens) die Anzahl der Gebiete?
[Die Arbeitsgruppe Alexandria katalogisiert die Artikel auf dem Matheplaneten]

 
 
Aufrufzähler 5459
 
Aufrufstatistik des Artikels
Insgesamt 668 externe Seitenaufrufe zwischen 2012.01 und 2023.02 [Anzeigen]
DomainAnzahlProz
https://duckduckgo.com60.9%0.9 %
https://www.ecosia.org30.4%0.4 %
http://google.de32148.1%48.1 %
https://google.de21632.3%32.3 %
https://google.com385.7%5.7 %
http://google.ee152.2%2.2 %
http://google.lu182.7%2.7 %
https://www.bing.com71%1 %
https://www.startpage.com60.9%0.9 %
http://images.google.de60.9%0.9 %
http://google.se60.9%0.9 %
http://google.dk40.6%0.6 %
https://suche.web.de20.3%0.3 %
http://google.ch40.6%0.6 %
http://google.at20.3%0.3 %
http://de.search-results.com20.3%0.3 %
http://www.ask.com10.1%0.1 %
http://search.sweetim.com10.1%0.1 %
http://search.incredibar.com10.1%0.1 %
http://adguard.com10.1%0.1 %
http://search.snapdo.com10.1%0.1 %
http://int.search.myway.com20.3%0.3 %
http://www.bing.com10.1%0.1 %
http://google.com20.3%0.3 %
http://www.sitejot.com10.1%0.1 %
https://google.ch10.1%0.1 %

Aufrufer der letzten 5 Tage im Einzelnen
Insgesamt 1 Aufruf in den letzten 5 Tagen. [Anzeigen]
DatumAufrufer-URL
2023.02.08 19:36https://duckduckgo.com/

Häufige Aufrufer in früheren Monaten
Insgesamt 638 häufige Aufrufer [Anzeigen]
DatumAufrufer-URL
2012-2018 (172x)http://google.de/url?sa=t&rct=j&q=
2020-2023 (153x)https://google.de/
2020-2022 (57x)https://google.de
2020-2022 (31x)https://google.com/
201211-11 (30x)http://google.de/url?sa=t&rct=j&q=vollständige induktion binomialkoeffizie...
201301-01 (15x)http://google.ee/imgres?q=kreis 7 teilen
201305-05 (15x)http://google.de/url?sa=t&rct=j&q=sehnenschnittpunkte im kreis gebiete
201205-05 (12x)http://google.de/url?sa=t&rct=j&q=vollständige induktion tetraederzahlen
201312-12 (11x)http://google.de/imgres?start=297&espv=210&es_sm=91&biw=1676&bih=860&tbm=isch...
201304-04 (10x)http://google.lu/imgres?q=kreis in 7 gleiche teile teilen
2017-2018 (10x)http://google.de/url?sa=i&rct=j&q=
201203-03 (9x)http://google.de/url?sa=t&rct=j&q=zwischen je zwei punkten von n vorhandenen ...
201410-10 (8x)http://google.de/url?sa=t&source=web&cd=6&ved=0CCYQFjAF
201204-04 (8x)http://google.de/url?sa=t&rct=j&q=wie viele geraden entstehen wenn von den ge...
201202-02 (8x)http://google.lu/imgres?q=einen kreis in sieben teilen
201307-07 (7x)http://google.de/url?sa=t&rct=j&q=sehnenschnittpunkte im kreis
2021-2022 (7x)https://www.bing.com/
201402-02 (7x)http://google.de/imgres?start=97&sa=N&rlz=1T4ACAW_deDE449DE449&biw=1440&bih=7...
202005-05 (7x)https://google.com/url?sa=t
202103-03 (6x)https://google.de/url?sa=t
2020-2023 (6x)https://www.startpage.com/
2015-2016 (6x)http://images.google.de/url?sa=t&rct=j&q=
201210-10 (6x)http://google.se/imgres?q=kugelpyramide
201308-08 (6x)http://google.de/imgres?um=1&sa=N&biw=1280&bih=663&tbm=isch&tbnid=5uS5X8pV_Qt...
201201-01 (5x)http://google.de/url?sa=t&rct=j&q=täuschende mathematik dreieck
201212-12 (5x)http://google.de/imgres?tbo=d&biw=1280&bih=827&tbm=isch&tbnid=XZ2TAIcRu-3zYM:
2020-2022 (5x)https://duckduckgo.com/
201302-02 (4x)http://google.de/search?q=Anzahl der Punkte auf einem Kreis
201401-01 (4x)http://google.de/imgres?sa=X&espvd=210&es_sm=93&biw=1846&bih=1115&tbm=isch&tb...
201206-06 (4x)http://google.de/url?sa=t&rct=j&q=durch sehne teilen den kreis in gebiete
201207-07 (4x)http://google.dk/imgres?q=sieben punkte im kreis

[Top of page]

"Mathematik: Täuschend einfach" | 2 Comments
The authors of the comments are responsible for the content.

Re: Täuschend einfach
von: luxi am: Mo. 04. März 2002 23:25:44
\(\begingroup\)Hallo matroid,
das ist sehr interessant wie man solche Formeln beweisen kann. mich würde interessieren ob es eine Interpretation der Formel binomial(n,4)+binomial(n,2)+1 gibt, die man direkter einsehen kann. Wäre es möglich jedes von den Gebieten entweder mit einer 4-elementigen Teilmenge oder einer 2-elemtigen teilmenge oder einer 0 elementigen Teilmenge (für die 1) der n Punkte zu verbinden. Oder vielleicht kann man auch die äquivalente Formel binomial(n-1,4)+binomial(n-1,3)+binomial(n-1,2)+binomial(n-1,1)+binomial(n-1,0) irgendwie in dem Bild wiederfinden. Eine Bijektion zwischen Gebieten und Teilmengen muß doch etwas bedeuten, aber was?
cu luxi\(\endgroup\)
 

Re: Täuschend einfach
von: Bozzo am: Fr. 06. Mai 2011 23:00:15
\(\begingroup\)Ich muss zugeben, ich hab den Beweis in dem Artikel jetzt nicht gelesen, weil er mir zu lang war. Daher weis ich nicht, inwieweit sich das, was ich jetzt schreibe, mit dem Artikel ueberschneidet. Aber luxis Frage nach einer Interpretation der Formel kann ich glaube ich beantworten. Es gibt (n ueber 2) Moeglichkeiten 2 der n Punkte auf dem Kreis auszuwaehlen, und jeder dieser Moeglichkeiten entspricht gerade eine der Geraden, die durch den Kreis geht; naemlich die, die die beiden gewaehlten Punkte verbindet. Weiter gibt es (n ueber 4) Moeglichkeiten, 4 der n Punkte auf dem Kreis auszuwaehlen, und jeder dieser Moeglichkeiten entspricht gerade ein Schnittpunkt zweier Geraden im Inneren des Kreises; naemlich der, der entsteht, wenn man die gewaehlten 4 Punkte paarweise verbindet. (Ja. Es entsteht tasaechlich immer nur genau 1 Schnittpunkt im Inneren des Kreises!) Ziehen wir eine neue Linie in den Kreis ein, teilt diese eine gewisse Anzahl k an Gebieten in zwei, und aus genau sovielen Gebieten mehr besteht nachher das Kreisinnere. Dabei hat dann die neue Linie offenbar k-1 alte Linien geschnitten. Wir haben durch das einziehen der neuen Linie also 1 Linie, k-1 Schnittpunkte und k neue Gebiete hinzugewonnen. Δ#Linien plus Δ#Schnittpunkte ist also offenbar Δ#Gebiete. Zu Beginn bildet das Innere des Kreises 1 Gebiet. Da wir (n ueber 2) Linien und (n ueber 4) Schnittpunkte haben (keine Schnittpunkte fallen zusammen!), haben wir zuletzt offenbar 1 + (n ueber 2) + (n ueber 4) Gebiete. \(\endgroup\)
 

 
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2023 by Matroids Matheplanet
This web site was originally made with PHP-Nuke, a former web portal system written in PHP that seems no longer to be maintained nor supported. PHP-Nuke is Free Software released under the GNU/GPL license.
Ich distanziere mich von rechtswidrigen oder anstößigen Inhalten, die sich trotz aufmerksamer Prüfung hinter hier verwendeten Links verbergen mögen.
Lesen Sie die Nutzungsbedingungen, die Distanzierung, die Datenschutzerklärung und das Impressum.
[Seitenanfang]