Seit meiner Schulzeit verfolgt mich eine einfach formulierte, aber schwer lösbare Aufgabe. Ich glaube, ich kenne die Lösung, aber mathematisch kann ich sie nicht ableiten. Hier ist sie:
Placiere in einem Quadrat fünf Punkte so, dass die Summe ihrer Abstände voneinander maximal ist.
So einfach formuliert also. Klar ist, dass vier Punkte in die Ecken kommen. Der fünfte muss m. E. unendlich nah an einem Eck liegen; dies kann ich aber nicht beweisen.
Also, Mathe-Genies sind gefragt!
Der fünfte muss wohl eher in die Mitte oder nicht? Was meinst du mit unendlich nah?
edit: ah ich verstehe, glaub ich, was du meinst. aber die aufgabe ist wohl anders gedacht
Es ist Folgendes gemeint: wenn man alle Punkte mit allen anderen Punkten verbindet und dann diese Strecken addiert, bekommt man die gemeinte Summe der Abstände, die laut Aufgabe maximal sein soll.
Ich hoffe, so versteht ihr, was gemeint ist.
Original von Onken
Der fünfte muss wohl eher in die Mitte oder nicht? Was meinst du mit unendlich nah?
Die Mitte ist definitiv falsch (leicht zu zeigen). Unendlich nahe soll der Punkt am Eck sein, weil die Ecke bereits durch einen der vier Punkte besetzt ist.
Original von Hunne68
Original von Onken
Der fünfte muss wohl eher in die Mitte oder nicht? Was meinst du mit unendlich nah?Die Mitte ist definitiv falsch (leicht zu zeigen). Unendlich nahe soll der Punkt am Eck sein, weil die Ecke bereits durch einen der vier Punkte besetzt ist.
So wie du die Aufgabe jetzt umgeschrieben hast ja.
Aber du kannst keinen Punkt unendlich nah irgendwo hinsetzen. Du kannst ihn aber einfach auf einen anderen Punkt setzen. Das sollte es tun.
Also dürfen nicht zwei Punkte am selben Ort sein?
Wenn es stimmt, dass vier Punkte in den vier Ecken sind, was ich jetzt nicht formal überprüft habe, dann hast du im Prinzip Recht, denke ich. Wobei man dann sagt "es existiert kein Maximum", nicht "muss unendlich nah..."
Wenn man mal das Quadrat zwischen (0, 0) und (1, 1) betrachtet und die vier Ecken mit den ersten vier Punkten besetzt, dann gilt es nur noch, die Summe der Abstände des übrigen Punktes (x, y) zu den vier Ecken zu maximieren, also:
sqrt(x²+y²)+sqrt((1-x)²+y²)+sqrt(x²+(1-y)²)+sqrt((1-x)²+(1-y)²)
Diese Funktion hat ein Minimum im Mittelpunkt des Quadrats und ist in den Ecken maximal, wenn man das ganze Quadrat [0, 1] x [0, 1] als Definitionsbereich zulässt.
Ein Maximum hat sie auf der Menge [0, 1] x [0, 1] auf jeden Fall, da dies eine kompakte Menge ist. Dass dieses Maximum dann in einer Ecke liegt, folgt aus der Konvexität. Es folgt dann auch, dass die Funktion keine Maxima hat, wenn man die Eckpunkte nicht zulässt (da die Funktion stetig ist und die Eckpunkte Häufungspunkte des übrigen Definitionsbereiches sind).
Das gilt auch allgemein für andere Quadrate bzw. Rechtecke als (0, 0)-(1, 1), da die Funktion Wurzel(x² + y²) streng konvex ist und die Summe zweier konvexer Funktionen ebenfalls konvex ist.
edit: Vorherige schlampige Formulierung korrigiert.
Annahme: Quadrat mit seitenlänge a
Möglichkeit 1: Punkt in jeder Eche und "ungefähr" in der Mitte (darf die Verbindung bestimmt nicht schneiden)
4*a+4*sqrt(2)*a= 5,414*a
Möglichkeit 2: (die richtige) Punkt in jeder Eche und "ungefähr" in einer Ecke
6*a+3*sqrt(2)*a= 10,423*a
(gerundete Werte)
Original von Merlinius
sqrt(x²+y²)+sqrt((1-x)²+y²)+sqrt(x²+(1-y)²)+sqrt((1-x)²+(1-y)²)
Diese Funktion hat ein Minimum im Mittelpunkt des Quadrats und ist in den Ecken maximal, wenn man das ganze Quadrat [0, 1] x [0, 1] als Definitionsbereich zulässt.
Ein Maximum hat sie auf der Menge [0, 1] x [0, 1] auf jeden Fall, da dies eine kompakte Menge ist. Dass dieses Maximum dann in einer Ecke liegt, folgt aus der Konvexität.
Bis zu dieser Gleichung bin ich auch gekommen, allerdings konnte ich mit ihr nichts anfangen.
Um zu verstehen, warum die obige Behauptung (d.h. "Dass dieses Maximum dann in einer Ecke liegt, folgt aus der Konvexität.") stimmt, fehlen mir - ehrlich gesagt - die Mathekenntnisse.
Beweist die Konvexität der Funktion tatsächlich, dass das Maximum in der Ecke liegt?
Du musst erstmal zeigen, dass sowohl die ableitung nach x als auch nach y der funktion für eckpunkte=0 ist und dann musst du zeigen, dass die hesse matrix an diesen stellen positiv definit ist. Aus der konvexität der funktion folgt allerdings die positive definitheit der gesamten hesse matrix.
Original von Hunne68
Original von Merlinius
sqrt(x²+y²)+sqrt((1-x)²+y²)+sqrt(x²+(1-y)²)+sqrt((1-x)²+(1-y)²)
Diese Funktion hat ein Minimum im Mittelpunkt des Quadrats und ist in den Ecken maximal, wenn man das ganze Quadrat [0, 1] x [0, 1] als Definitionsbereich zulässt.
Ein Maximum hat sie auf der Menge [0, 1] x [0, 1] auf jeden Fall, da dies eine kompakte Menge ist. Dass dieses Maximum dann in einer Ecke liegt, folgt aus der Konvexität.
Bis zu dieser Gleichung bin ich auch gekommen, allerdings konnte ich mit ihr nichts anfangen.
Um zu verstehen, warum die obige Behauptung (d.h. "Dass dieses Maximum dann in einer Ecke liegt, folgt aus der Konvexität.") stimmt, fehlen mir - ehrlich gesagt - die Mathekenntnisse.
Beweist die Konvexität der Funktion tatsächlich, dass das Maximum in der Ecke liegt?
ja
Am einfachsten lässt sich das wohl veranschaulichen, wenn man eine Dimension tiefer geht.
Also stell Dir eine stetige Funktion vor, die auf einem Intervall definiert ist, z.B. auf [0, 1]. Stetig heißt anschaulich, dass die Funktion keine Sprünge macht. Konvex heißt: Wenn ich zwei Punkte überhalb des Graphen mit einer geraden Linie verbinde, dann schneidet die Linie den Graphen nicht. Das gilt z.B. für diese Funktion:
Anschaulich formuliert: Wenn man auf dem Graphen entlang fahren würde von links nach rechts, dann ist man stets in einer Linkskurve oder fährt geradlinig.
An einfachen Beispielen kann man sich dann ganz gut klarmachen, dass so eine Funktion auf einem Intervall - z.B. [0, 1] - ihr Maximum entweder in 0 hat oder in 1.
Das Prinzip kann man nun in die nächsthöhere Dimension auf [0, 1] x [0, 1] übertragen, also auf die obige Aufgabe.
Immer wenn ich einen "Querschnitt" dieses dreidimensionalen Graphen betrachte hat dieser sein Maximum in einem Randpunkt, wie oben erklärt. Denn das ist ja genau ein zweidimensionaler Graph dann. Deshalb liegt das Maximum von dreidimensionalen (streng) konvexen Graphen auf jeden Fall in einer Ecke, wenn der Definitionsbereich rechteckig ist.
Ich hoffe, das wird halbwegs anschaulich klar. Ich will es auch nicht zu mathematisch formulieren.
Oder stell Dir eine Salatschüssel vor. Die hat ja auch eine konvexe Form.
Wenn Du jetzt einen Holzwürfel in die Salatschüssel legst, dann stößt der immer in einer Ecke an, egal wie man ihn platziert. Und dazu muss die Salatschüssel nichtmals symmetrisch sein, sie muss nur konvex sein, also "nach unten ausgehöhlt".
Warum ist eigentlich so klar, dass die ersten 4 Punkte in den Ecken liegen müssen? Übersehe ich etwas?
Original von SlowLarry
Warum ist eigentlich so klar, dass die ersten 4 Punkte in den Ecken liegen müssen? Übersehe ich etwas?
Ist nicht klar(, zumindest mir nicht).
Stimmt.
Bei näherer Betrachtung habe ich meine Zweifel, ob das überhaupt gilt. Ich glaube fast nicht.
Angenommen wir haben fünf Punkte A, B, C, D, X.
Maximiert werden soll die Summe aller Abstände. Die Summe kann man folgendermaßen Gruppieren:
Umfang des Vierecks ABCD + Länge der beiden Diagonalen des Vierecks ABCD + d(A, X) + d(B, X) + d(C, X) + d(D, X)
Die ersten beiden Summanden (d.h. Umfang + Diagonalen von ABCD) werden zwar maximal, wenn man die Punkte A, B, C, D in die Ecken legt, aber es ist nicht klar, dass dies für jedes X die gesamte Summe maximiert.
Original von Merlinius
Bei näherer Betrachtung habe ich meine Zweifel, ob das überhaupt gilt. Ich glaube fast nicht.
Macht mich nicht fertig, Jungs! Meine sicher geglaubte Lösung wankt also auch :).
Ist ne Lösung so aufwendig?
Also ich denke nicht, dass es optimal ist den fünften Punkt in die Ecke zu setzen.
Falls ich mich nicht verrechnet habe kommt dann 18,07 raus (11+5*sqrt(2))
Wenn ich die Punkte im Pentagramm setze, also jeweils 3mal auf die "Hälfte" und dann auf 1/3 und 2/3 kommt 15,17 raus (2/3*sqrt(13) + 2/3*sqrt(35)+ 2*sqrt(2)+ 6) ok weniger,
aber wenn ich wieder die vier Ecken verwende und einmal auf die "Hälfte" kommt
20,13 raus(4*sqrt(2) + 2*sqrt(5) +10)
Ich sage nicht, dass 20,13 optimal ist, aber besser als 18,07 und auch besser als alles was mir sonst noch so einfällt.
Die Punkte müssen ja auf dem Rand liegen und eine "gewisse" Symmetrie aufweisen.
Alles natürlich unter der Annahme, dass ich mich nicht verrechnet habe, deswegen auch die genauen Ergenisse in Klammern.
Edit: Der fünfte Punkt in der Mitte hätte 19,13 (8+8*sqrt(2))
Edit2: Ha Punkt in die Mitte war doch besser als Punkt auf die Ecke 
Ne, du musst dich verrechnet haben.
Edit: Ich komme auf 10,2426 wenn 2 Punkte in der Ecke sind und auf 10,0645, wenn einer mittig auf der Kante ist. Jeweils Seitenlänge 1.
Das ist aber auch logisch. Wenn man den 5. Punkt auf einer Seite verschiebt, ändert sich an der Summe nur der Teil, der zur Verbindung zu den Punkten der anderen Seite gehört. Also nur zwei Längen. Diese Längen werden auf der Mitte der Seitenlinie minimal und in der Ecke maximal.
