Ein bisschen Mathematik. Gesucht: Kürzestes Straßennetz
In meinen nahezu täglich erscheinenden #mathepuzzle(s) auf Twitter gabs gestern folgende Aufgabe (leicht modifiziert):
4 Orte bilden die Eckpunkte eines Quadrats.
Die Gegend ist vollkommen flach und nicht bewachsen (stellen sie sich zum Beispiel eine Gegend in Arizona vor).
Es soll eine Straßennetz angelegt werden, auf dem man von jedem Ort aus
jeden anderen erreichen kann. Wie kann man das so machen, dass die
Länge aller Straßen addiert möglichst klein ist?
Eine von einigen meiner Follower vorgeschlagene Lösung ist ein X:
Diese Grafik ist dynamisch, man kann den grünen Punkt mit der Maus bewegen. Wenn man das tut, dann kommt ein roter Punkt zum Vorschein. Den kann man auch bewegen.
Wenn man die beiden Punkte verschiebt, dann stellt man fest, dass es bessere Lösungen des Problem gibt, insbesondere diese:
Auch hier kann man den roten und den grünen Punkt verschieben.
Klickt man auf den gerundeten Doppelpfeil in der oberen rechten Ecke, dann kann man den Ausgangszustand der Grafik(en) wiederherstellen.
Wie können wir nachweisen, dass das die Lösung für das kürzeste Straßennetz ist?
Es ist aufwändig und anspruchsvoll zu zeigen, dass die beste Lösung zwei „Zwischenpunkte“ haben muss. Nehmen wir das einmal als gesichert an. Der Rest der Überlegungen geht so:
Wir zeichnen Ellipsen durch je 2 Eckpunkte und einen Zwischenpunkt.
Bewegt man den roten oder den grünen Punkt auf seiner Ellipse, dann bleibt die Summe der Abstände von seinen beiden Quadrateckpunkten gleich. Der Abstand zum andern Zwischenpunkt ändert sich. Am kleinsten wird der Abstand zwischen den beiden Zwischenpunkten, wenn beide auf der senkrechten Mittellinie des (gedachten) Quadrats liegen.
Das gilt auch dann, wenn die Ellipsen verschieden groß sind, wenn also der rote Punkt von seinen beiden Eckpunkten in Summe nicht gleich weit entfernt ist wie der grüne Punkt von seinen beiden Eckpunkten.
Jetzt fügen wir noch einen Hilfspunkt ein
und berechnen die Summe der Wegstrecken im oberen System (oranger Punkt, roter Punkt, zwei blaue Punkte) und im unteren System (oranger Punkt, grüner Punkt, zwei blaue Punkte)
Wenn eines der beiden Teilsysteme eine kleinere Wegstrecke als die andere ergibt, dann kann man das andere System so ändern, dass sie dieselbe Streckensumme ergibt. Man muss dazu nur den Zwischenpunkt dieses Systems so verschieben, dass er das Spiegelbild des „besseren“ Punktes um die waagrechte Mittelachse des Quadrats ist.
Zwischenbilanz: wenn wir das untere System (oranger Punkt, grüner Punkt, zwei blaue Punkte) durch Verschieben des grünen Punkts so einstellen, dass es die kleinste Streckensumme ergibt, dann haben wir auch die beste Lösung für das Gesamtsystem gefunden, weil wir ja den besten roten Punkt durch Spiegelung des besten grünen Punkts erhalten.
Außerdem wissen wir schon, dass der beste grüne Punkt auf der senkrechten Mittelachse des Quadrats liegen muss.
Das geänderte Problem, das wir lösen müssen, sieht also so aus:
Bestimme $x$ so, dass die Summe der 3 Wegstrecken kleinstmöglich wird. Wir sehen in der Grafik zwei rechtwinkelige Dreiecke, daher ist die Summe der 3 Wegstrecken $ \sqrt{(\frac{1}{2})^2+x^2} + \sqrt{(\frac{1}{2})^2+x^2} + (1-x) = 2\sqrt{(\frac{1}{2})^2+x^2} + (\frac{1}{2}-x)$
Das ist eine klassische Extremwertaufgabe. Die kann man ganz altmodisch mit Papier und Stift lösen. Man muss dazu die erste Ableitung bilden, die gleich 0 setzen und diese Gleichung lösen.
Man kann aber auch zur Website Wolfram Alpha gehen und dort die Aufgabe
solve derivative of 2*sqrt((1/2)^2+x^2)+(1/2)-x=0 for x
eingeben und erhält die Lösung $x=\frac{1}{2\sqrt{3}}$
In der Grafik, in der wir genau diese Lösung einzeichnen, markieren wir ein rechtwinkeliges Dreieck:
Weil die Strecke $x$ die Länge $\frac{1}{2\sqrt{3}}$ und Wegstrecke vom grünen Punkt zum Quadratpunkt rechts unten die Länge
$\sqrt{(\frac{1}{2})^2+(\frac{1}{2\sqrt{3}})^2}=\frac{1}{\sqrt{3}}$
hat, ist die Wegstrecke vom grünen Punkt nach rechts unten doppelt so lange wie $x$. Damit ist diese Figur eine halbes gleichseitiges Dreieck, und der Winkel zwischen diesen beiden Strecken 60º. Damit ist der Winkel zwischen den beiden schrägen Wegstrecken 120º und wir haben gezeigt, wie die Lösung für das kürzeste Straßennetzwerk dieser Konfiguration aussieht.
Wie man das Problem mit alter analoger Technik lösen kann (Seifenlösung) zeigt ein YouTube-Video, auf das mich mein Twitter-Follower @behackl hingewiesen hat.