Konvexes Vieleck Einkreisen

20.07.2004, 11:24	Bruce	Auf diesen Beitrag antworten »
Konvexes Vieleck Einkreisen Hallo liebe Freunde anspruchsvoller mathematischer Probleme, wer von euch hat Zeit und Lust an der Lösung des folgenden Problems mitzuwirken: Gegeben ist ein beliebiges ebenes, konvexes Vieleck mit n Ecken. Betrachtet werden alle Kreise, die durch drei aufeinanderfolgende Eckpunkte dieses Vielecks gehen. Zu zeigen: Mindestens einer dieser Kreise überdeckt das gesamte Vieleck. Bemerkung: Ein Vieleck ist genau dann konvex, wenn für zwei beliebige Punkte des Vielecks auch die Vebindungsstrecke zum Vieleck gehört. Diesess Problem ist mit den Mitteln der Schulmathematik lösbar. Wenn ich mich richtig erinnere wurde diese Aufgabe im Jahr 1985 in der ersten Runde des Auswahlverfahrens für die deutsche Mannschaft zur IMO 1986 gestellt und mit Sicherheit von einigen findigen Mathespezialschülern gelöst. Ich gehörte nicht zu diesen und bin heute Physiker. Trotzdem ist mein Interesse an solchen Problemen nicht erloschen! Also Ihr echten Mathe-Asse unter den Board-Teilnehmern: Wenn euch dieses Problem reizt, gebt euch einen Ruck und steigt ein in dieses Thema. Vielleicht kann einer von euch oder wir gemeinsam diese Nuss knacken.
19.10.2004, 14:17	Poff	Auf diesen Beitrag antworten »
RE: Konvexes Vieleck Einkreisen Folgende 'Vermutung', von der ich meine den Beweis eigentlich schon zu kennen, aber nicht ausformulieren will weil mir das nicht unbedingt liegt, mag es also jemand anderes tun, oder einen Grund dafür liefern dass es falsch ist ... Sei K der Kreis durch die Punkte A1,A2,A3 und A4 außerhalb K, Ai mit i aus T c {1 ...n} innerhalb K liegend, dann gilt für den Kreis K' durch A2,A3,A4 alle Ai mit i aus T und A1 liegen innerhalb K' Dass daraus die Behauptung folgen würde sollte klar sein. Viel Spaß, oder das 'Gegenbeispiel' . .
19.10.2004, 17:12	Bruce	Auf diesen Beitrag antworten »
Hallo Poff, es freut mich, daß sich doch noch jemand für dieses Problem interessiert . Allerdings verstehe ich nicht so richtig, was Du in deinem Beitrag sagen willst . Ich nehme mal an, daß Du an einen Widerspruchsbeweis gedacht hast. Du willst also annehmen, es gibt ein konvexes n-Eck mit der Eigenschaft, daß keiner der Umkreise das n-Eck komplett überdeckt und versuchst einen Widerspruch zu konstruieren. Ich entnehme deinen Bemerkungen, daß die Punkte A1, A2 und A3 aufeinanderfolgende Eckpunkte sind durch die der Kreis K geht. Dieser Kreis schneidet nach Voraussetzung das n Eck, so daß ein Punkt A4 außerhalb von K liegt. Aber wie geht es jetzt weiter? Schau dir bitte mal die angehängte Skizze an und sag mir dann, wie Du weiter argumentierst. Gruß von Bruce
19.10.2004, 18:51	Poff	Auf diesen Beitrag antworten »
Nein Bruce, :-oo erstens interessiere ich mich NICHT brennend für das Problem gg und zweitens, oh Wunder, hast du mein präzise Formuliertes falsch gelesen :-oo Umgangssprachlich formuliert besagt das, falls A1,A2,A3 auf dem Kreis liegen und A4 außerhalb, so liegen A1 und ALLE die zuvor schon innerhalb lagen, nun innerhalb des NEUEN Kreises durch A2, A3, A4. was aber noch explizit zu beweisen ist, oder eben zu widerlegen. Ich meine es wäre richtig und zudem liese sich daraus die Beh. zeigen. Aber auch hier existiert noch ein Schwachpunkt, den ich zwar meinte im Griff zu haben, mich aber auch gut irren könnte da ich das alles nicht konkret durchdacht habe und deshalb auch primär als eine Anregung hier reinstellen wollte. Anders formuliert, weils nicht unbedingt meine Wellenlänge ist, ich eh keine Punkte mehr dafür bekomm, interessierts mich nicht 'brennend stark' . . Ja und jener Schwachpunkt ist eben das Problem, dass diese außerhalb liegenden Punkte leider nicht lückenlos aufeinander folgen ... (der A4 von OBEN ist direkt NEBEN A3 liegend)
20.10.2004, 15:23	Poff	Auf diesen Beitrag antworten »
@Bruce hab nochmal etwas drüber nachgedacht und auch den 'Grund' gefunden warum es mir nicht schmeckt. Stelle dir vor die Anzahl der Punkte des Vielecks läuft gegen unendlich, dann ist das Vieleck nichts anderes als eine geschlossene Konvexe Linie und die Aussage in etwa folgende: Die konvexe Linie hat eine minimale Krümmung, bzw einen maximalen Krümmungskreisradius und liegt vollständig innerhalb dieses maximalen Krümmungskreises. Wohl nicht 'allzuschwierig' nachzuweisen, dass 'du' mit stärkerer Krümmung nicht mehr aus dem Maximalkreis rauskommen kannst. Ich denke genau aus dieser Kante kommt auch die Aufgabe und das ist auch genau der Grund warum sie mir nicht schmeckt. Doppelpostanliegen mal extra ignoriere
20.10.2004, 18:05	Bruce	Auf diesen Beitrag antworten »
Poff, dein Hinweis war entscheidend! Bisher habe ich vermutet, daß der Umkreis mit dem größten Radius das konvexe Vieleck vollständig überdeckt. Mit deinem Hinweis auf die geschlossene konvexe und glatte Kurve erscheint es mir nun sehr plausibel, daß diese Vermutung stimmt. Blöderweise habe ich bisher nie an die geschlossene Kurve und ihre Krümmungskreise gedacht. Na ja, manchmal sieht man den Wald vor lauter Bäumen nicht. Zur Überprüfung der Idee mit dem größten Umkreis habe ich daran gedacht, zufällig konvexe n-Ecke mit dem Computer zu erzeugen und durch einfaches Nachrechnen zu testen, ob die Vermutung stimmt. Das ist leider daran gescheitert, daß mir kein vernünftiger Algorithmus zur Erzeugung eines zufälligen, konvexen Vielecks eingefallen ist. Gruß von Bruce
Anzeige

20.10.2004, 19:34	Poff	Auf diesen Beitrag antworten »
Bruce, mir ging das ähnlich, bin auch erst heute morgen darauf gestoßen, als ich mit dem von mir schon geposteten Ansatz das konstruktiv einzukreisen versuchte und dabei zwangsweise bei dem Problem ein A(k) k > 4 außerhalb und A1, A2, A3 auf der Kreislinie, darauf gestoßen bin. Wenn ich mal die von mir oben gepostete 'Vermutung' als richtig und gegeben ansetzte, dann lässt sich das Ziel damit sogar schrittweise 'konstruktiv' erzeugen. Dabei wird klar, dass der gesuchte Kreis wohl jener mit dem maximalen Radius sein dürfte, weil die 'Konstruktion' nämlich so angelegt ist, dass der Radius des Kreises dabei ständig zunimmt, zugleich keine der zuvor schon inneliegenden Ecken rausfallen sondern stets um wenigstens eine Ecke zunehmen. Wegen der Endlichkeit muss das zu einem Ende kommen. Zwar wird dabei nicht unbedingt ersichtlich, dass der Zielkreis jener mit dem größten Radius sein müsste, aber es wird ersichtlich dass jener das leisten würde, weil er eben in jenem Konstruktionsprozess (bei dem nichts rausfällt) erreichbar wäre. Weil das aber nur grob durchlaufen ist und die einzelnen Konstruktionsschritte noch genauerer Begründungen bedürften um den Status eines Beweises einzunehmen lass ich das mal außen vor, meine aber im Prinzip die Methode zur Lösung zu haben. Damit kann ich leben und bin zufrieden ... . .
03.01.2005, 11:19	AD	Auf diesen Beitrag antworten »
Ich greife mal diesen alten Thread auf, weil mir dazu eine Idee eingefallen ist: Vollständige Induktion über n Für n=3 gibt es nichts zu beweisen. Für n>3 betrachten wir alle n Radien der Umkreise von A_iA_{i+1}A_{i+2} (Indizes wie üblich modulo n) für i=1,...,n. O.B.d.A. sei derjenige Radius von A_1A_2_A_3 maximal, seine Größe sei R. Dann entferne man A_2 und betrachte das (n-1)-Eck A_1A_3...A_n. Nach Induktionsvoraussetzung gibt es nun hier ein Umkreisdreieck benachbarter Punkte, welches alle diese (n-1) Punkte enthält. Nun gibt es noch zwei Fälle zu untersuchen, deren Details ich mir hier spare: 1.) A_1A_3 gehört nicht zum Umkreisdreieck des (n-1)-Ecks. Dann gilt für den Radius r dieses Umkreises r<=R, und man kann (mittelbar) beweisen, dass auch A_2 innerhalb dieses Kreises liegt. 2.) A_1A_3 gehört zum Umkreisdreieck des (n-1)-Ecks, o.B.d.A. sei das das Dreieck A_1A_3A_4. 2.1.) A_2 liegt innerhalb oder auf dem Rand des Umkreises von A_1A_3A_4. Dann wählen wir A_1A_2A_3 als neues Umkreisdreieck. 2.2.) A_2 liegt außerhalb des Umkreises von A_1A_3A_4. Dann wählen wir A_2A_3A_4 als neues Umkreisdreieck.

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »