Geschlossene Streifenzüge < Wettbewerbe < Schule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 13:18 Fr 02.09.2005 | | Autor: | Cool-Y |
Es sei A(n) die maximale Anzahl der Selbstüberschneidungen von geschlossenen Streckenzügen [mm] P_{1}P_{2}...P_{n}P_{1} [/mm] (n [mm] \ge3), [/mm] bei denen keine drei der Eckpunkte auf einer gerade Geraden liegen.
Man beweise:
a) A(n)= [mm] \bruch{n(n-3)}{2}, [/mm] falls n ungerade
und
b) A(n)= [mm] \bruch{n(n-4)}{2}+1, [/mm] falls n gerade ist.
diese aufgabe war meiner meinung nach die schwerste der zweiten runde des bwm dieses jahr, und auch die einzige, die ich nicht lösen konnte. da seit gestern die bearbeitungszeit zu ende ist, wollte ich hier mal fragen, ob die vielleicht jemand lösen könnte.
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 14:21 Fr 02.09.2005 | | Autor: | Hanno |
Hallo Mario!
Die (a) konntest du lösen, oder? Bei der (b) muss ich sagen, dass sie auch die einzige der Aufgaben war, die ich leider leider auch nach Stundenlanger Überlegung nicht rausbekam.
Liebe Grüße,
Hanno
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 15:17 Fr 02.09.2005 | | Autor: | Cool-Y |
jep, die a) war relativ leicht. aber die b) is ne echte nuss...
hanno, darfst du denn als student bei dem wettbewerb mitmachen?!
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 15:51 Fr 02.09.2005 | | Autor: | Hanno |
Hallo Mario!
Ja, ich bin ja auch noch Schüler (13. Klasse) und studiere nebenher an der Uni-Kaiserslautern [Fernstudium].
Liebe Grüße,
Hanno
|
|
|
| |
|
Hallo zusammen,
ich gehe davon aus, dass die Ecken des Polygonzuges ein regelmäßiges n-Eck bilden:
das wäre beweisbedürftig, aber es vereinfacht das Folgende ohne die Allgemeinheit einzuschränken. Dann kann man nämlich eine Ecke auf dem Umkreis zwischen seinen unmittelbaren Nachbarn hin- und herschieben ohne die Knotenzahl A(n) zu verändern.
Der Beweis geht mit Induktion:
Induktions-Anfang ist das Quadrat, bei dem zwei gegenüberliegende Seiten durch die Diagonalen ersetzt wurden: dann gilt A(4) = 1 und es gibt einen Durchmesser, der alle 4 Verbindungen des Polygonzuges trifft.
Induktionsvoraussetzungen:
Es gilt A(n) und es gibt einen Durchmesser W-O (Skizze), der alle n Verbindungen schneidet. Dabei sind SW, NW, SO und NO die unmittelbar benachbarten Ecken des Polygonzuges (die roten Verbindungen gibt es noch nicht, der grüne ist ein zu W-O alternativer Durchmesser):
[Dateianhang nicht öffentlich]
Dann liegen n/2 der Ecken auf der Südhälfte und schicken 2*(n/2) Verbindungen über den Äquator W-O zu den n/2 Ecken in die Nordhälfte. Davon sind die Verbindungen SW-N1 und SW-N2 exemplarisch eingezeichnet (wobei N1 und N2 beliebig sind, auch N1 = NW bzw. N2 = NO sein kann, aber die Reihenfolge von N1 und N2 beibehalten werden soll). Der grüne Durchmesser kann zwischen den Begrenzungen NW, SW, NO und SO hin- und hergedreht werden ohne die n Kreuzungen zu verlieren.
Induktionsschluss:
Jetzt werden die Punkte W und O und die Verbindung W-O eingefügt.
Von SW wird eine Verbindung SW-N2 (blau) so auf W umgeklemmt, dass sie die andere Verbindung SW-N1 schneidet: dadurch entseht ein neuer Knoten (schwarz-rot) und die andern bleiben erhalten (da ich auch SW über W bis kurz vor NW drehen kann ohne A(n) zu verändern). Allerdings verliert W-O dabei einen Knoten (blau-rot) non seinen n Stück, sodass die Gesamtzahl der Knoten um n erhöht wird.
Dann wird die Verbindung SW-O geknüpft und südlich davon liegen immer noch n/2-1 Ecken, die insgesamt n-2 Verbindungen über SW-O nach Norden schicken (was für grün gilt, gilt auch für SW-O: es wird n mal geschnitten minus der beiden Verbindung von SW selbst).
Der Polygonzug ist jetzt wieder (einfach) geschlossen und die Gesamtknotenzahl ist insgesamt um 2n - 2 erhöht worden, es gilt deshalb:
[mm]A(n) + 2n - 2 = A(n+2)[/mm] .
Außerdem trifft der grüne Durchmesser alle n alten Verbindungen (statt der blauen jetzt W-N2) und zusätzlich die beiden neuen W-O und SW-O, also n+2 Stück.
Dann schiebe ich alle n+2 Ecken auf die Positionen im n+2-Eck
Damit reproduzieren sich die Induktionsvoraussetzungen für n+2 und es ist gezeigt, dass es tatsächlich für alle [mm] n\in \IN [/mm] n-Ecke mit A(n) Knoten gibt.
Dass es nicht mehr sein können, ist noch zu zeigen, ist aber einfacher(falls ihr Bedarf habt, meldet euch).
Grüße, Richard
Dateianhänge:
Anhang Nr. 1 (Typ: jpg) [nicht öffentlich]
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 10:39 Mi 07.09.2005 | | Autor: | Cool-Y |
danke, das macht mir die sache klarer.
|
|
|
|
