Lösungsbeschreibung des Preisrätsels vom Januar 2018

Wegführungen

1.) Voraussetzungen

Gegeben sind vier Punkte in einer Ebene mit den folgenden Koordinaten: $$ P_1=(x_1,y_1)=(-3, 0) \\ P_2=(x_2,y_2)=(-3, 2) \\ P_3=(x_3,y_3)=( 2,-2) \\ P_4=(x_4,y_4)=( 4,-4) $$

2.) gerade Wege ohne Kreuzung

Der kürzeste Weg in der Ebene ist immer eine Strecke und in diesem Fall drei Strecken, die vier Punkte miteinander verbinden sollen.
Bei $n$ Punkten sind immer $v$ Verbindungslinien zwischen je zwei Punkten möglich. $$v=\sum_{i=0}^{n-1} i$$ In diesem Fall ist $n=4$ und demzufolge $v=6$.
Es gibt dabei zwei mögliche Konfigurationen, die Bild 1 zeigt: links ohne Kreuzung, rechts mit Kreuzung.

Bild 1

Um festzustellen, ob im konkreten Fall eine Kreuzung vorliegt, bildet man Paare von Verbindungslinien, die keinen gemeinsamen Punkt haben. Das sind die folgenden drei Möglichkeiten: $$ \text{1. Paar:}\quad\overline{P_1P_2}\quad\overline{P_3P_4} \\ \text{2. Paar:}\quad\overline{P_1P_3}\quad\overline{P_2P_4} \\ \text{3. Paar:}\quad\overline{P_1P_4}\quad\overline{P_2P_3} $$ Jedes Streckenpaar liegt auf einem Geradenpaar, deren Kreuzungspunkt $K(x_k,y_k)$ bestimmt werden kann: $$ x_k = \frac{(x_b y_a - x_a y_b)(x_c - x_d) + (x_c y_d - x_d y_c)(x_a - x_b)} {(x_c-x_d)(y_a-y_b) + (x_a-x_b)(y_d-y_c)} $$ Liegt z.B. die Koordinate $x_k$ auf beiden Strecken des Paares, also zwischen den Endpunkten, dann ist eine Kreuzung vorhanden. Eine Überprüfung der $y_k$-Koordinate erübrigt sich.
Die Indizes $a$, $b$, $c$ und $d$ können nun für die drei Paare durch $1$, $2$, $3$ und $4$ entsprechend der Tabelle 1 ersetzt werden.

Paar	a	b	c	d	xk	Kreuzung
1	1	2	3	4	-3	nein
2	1	3	2	4	1.375	ja
3	1	4	2	3	5.75	nein

Tabelle 1

3.) die möglichen geraden kreuzungsfreien Wege und deren Längen

Alle möglichen Wege, die vier Punkte ohne Verzweigung miteinander zu verbinden, findet man, wenn man die Punkte permutiert, also in allen Anordnungen aneinander reiht. Die Anzahl der Möglichkeiten ist $$4!=1\cdot 2\cdot 3\cdot 4=24$$ Dabei sind aber zur Hälfte Duplikate enthalten, denn ist der gleiche Weg wie . Eine weitere Reduktion ergibt sich aus der Bedingung der Kreuzungsfreiheit. Dadurch fallen alle Verbindungen aus, bei denen sowohl $\overline{P_1P_3}$ als auch $\overline{P_2P_4}$ enthalten sind. Es bleiben 8 Möglichkeiten. Die sortierbare Tabelle 2 enthält die Lösung der ersten Rätselfrage.

Punktanordnung	1. Strecke	2. Strecke	3. Strecke	Gesamtlänge
	2,00000000	6,40312424	2,82842712	11,23155136
	2,00000000	9,21954446	2,82842712	14,04797158
	2,00000000	5,38516481	2,82842712	10,21359193
	2,00000000	8,06225775	2,82842712	12,89068487
	8,06225775	9,21954446	6,40312424	23,68492644
	8,06225775	2,82842712	6,40312424	17,29380911
	6,40312424	2,00000000	8,06225775	16,46538199
	6,40312424	5,38516481	8,06225775	19,85054679

Tabelle 2

Im folgenden Bild 2 werden die Wege grafisch dargestellt. Mit Klick auf die entsprechende Punktanordnung in Tabelle 2 wird der dazu passende Weg angezeigt.

Bild 2

4.) Wege mit einem geraden Stück und beiderseits sich knickfrei anschließenden Kreisbögen

Aus der obigen Abbildung geht hervor, wie der Anschluss eines Kreisbogens an die mittlere Strecke herzustellen ist. Es ist die Punktabfolge als Beispiel gewählt, wobei der zweite Bogen zu $P_4$, der auf die gleiche Weise zu konstruieren ist, hier im Bild weggelassen ist.

Es beginnt mit der Bestimmung des Winkels $\gamma$. Dazu bieten sich zwei Methoden an:
1.) über das Skalarprodukt der Vektoren $\vec{u}=\overrightarrow{P_2 P_1}$ und $\vec{v}=\overrightarrow{P_2 P_3}$: $$ \vec{u}\circ\vec{v}=\left|\vec{u}\right|\cdot\left|\vec{v}\right|\cdot\cos\gamma \\ \gamma = \arccos\left(\frac{\vec{u}\circ\vec{v}}{\left|\vec{u}\right|\cdot\left|\vec{v}\right|}\right) $$ oder 2.) über den Cosinussatz im Dreieck $\triangle P_1P_2P_3$: $$ c^2=a^2+b^2-2ab\cdot\cos\gamma \\ \gamma = \arccos\left(\frac{a^2+b^2-c^2}{2ab}\right) $$ Wie man leicht sehen kann ist der Winkel $$ \alpha=90°-\gamma\quad\text{(im Winkelmaß)} \\ \alpha=\pi/2-\gamma\quad\text{(im Bogenmaß)} $$ und der Winkel des Bogens $$ \varphi=360°-2\cdot(90°-\alpha)=360°-2\cdot\gamma\quad\text{(im Winkelmaß)} \\ \varphi=2\pi-2\cdot(\pi/2-\alpha)=2\pi-2\cdot\gamma\quad\text{(im Bogenmaß)} $$

Des Weiteren sind die Koordinaten des Mittelpunkts $M_1$ zu suchen, die durch den Schnittpunkt der Geraden $d$ und $e$ sich ergeben. Für die Geradengleichungen $$ y = m_d x + n_d \\ y = m_e x + n_e $$ sind die Steigung $m$ und der Schnittpunkt mit der y-Achse $n$ zu bestimmen: $$ m_d = -\frac{x_1-x_2}{y_1-y_2} \\ n_d = \frac{y_1+y_2}2+\frac{x_1-x_2}{y_1-y_2}\cdot \frac{x_1+x_2}2 \\ m_e = -\frac{x_3-x_2}{y_3-y_2} \\ n_e = y_2+\frac{x_3-x_2}{y_3-y_2}\cdot x_2 $$ Dabei sind $(\frac{x_1+x_2}2|\frac{y_1+y_2}2)$ die Koordinaten des Punktes A. Die Steigungen ergeben sich aus der Senkrecht-Stellung zur Referenz-Strecke und die Schnittpunkte mit der y-Achse durch Einsetzen der Koordinaten eines Punktes auf der Geraden.
Die Schnittpunkt-Koordinaten des Punktes $M_1$ errechnen sich nun aus den beiden Geradengleichungen. $$ x_{m1}=-\frac{n_d-n_e}{m_d-m_e} \\ y_{m1}=m_d\cdot x_{m1}+n_d $$ Als Letztes wird der Radius noch zur Berechnung der Bogenlänge benötigt. Er ergibt sich z.B. aus dem Abstand der Punkte $M_1$ und $P_1$ $$ r_1=+\sqrt{(x_1-x_{m1})^2+(y_1-y_{m1})^2} $$ Die abschließende Formel für die Bogenlänge mit $\varphi$ im Bogenmaß ist nun $$\rand{ b_1=\varphi\cdot r1 }$$ In der folgenden Tabelle sind alle Kombinationen von möglichen Wegen nach dem obigen Berechnungsschema aufgelistet und nach Länge sortiert.

Punkt- 1. Kreisbogen 2. Kreisbogen mittlere   gesamter

Anordnung xm1 ym1 Radius1 φ1 [°] Bogen1 xm2 ym2 Radius2 φ2 [°] Bogen2 Strecke Weg -3,80 1,00 1,2806 257,32 5,7514 -6,00 -12,00 12,8062 12,68 2,8342 6,403124 14,988714 -3,80 -9,25 9,2845 326,28 52,8728 -88,00 -104,25 136,0664 356,12 845,7090 6,403124 904,984922 -3,86 1,00 1,3171 261,20 6,0044 16,00 10,00 18,4391 351,20 113,0250 9,219544 128,248903 -9,93 -20,25 21,4025 338,29 126,3653 58,50 73,75 94,5003 356,12 587,3587 9,219544 722,943542 -2,83 -6,83 6,8354 46,40 5,5352 -38,50 -46,50 60,1041 351,20 368,4164 2,828427 376,780036 -6,83 -14,83 15,3206 329,49 88,1042 -18,50 -22,50 28,9914 12,68 6,4162 2,828427 97,348794 -2,43 1,00 1,1518 120,51 2,4225 6,67 0,67 5,3748 329,49 30,9090 8,062258 41,393719 16,14 17,25 24,4747 338,29 144,5042 6,67 16,92 19,4838 344,11 117,0178 8,062258 269,584264 -2,60 1,00 1,0770 136,40 2,5640 0,67 -5,33 3,5901 46,40 2,9072 5,385165 10,856340 6,10 8,25 11,0396 326,28 62,8673 -13,83 -27,08 29,1696 344,11 175,1901 5,385165 243,442612 -0,10 0,00 2,9000 136,40 6,9037 3,07 2,00 6,0714 261,20 27,6787 2,000000 36,582385 1,10 2,00 4,1000 257,32 18,4134 1,64 0,00 4,6429 120,51 9,7653 2,000000 30,178729

Damit ist die Rätselfrage 2 beantwortet.

5.) Wege aus zwei Kreisbögen mit gleichem Radius und ohne Knick

Hier sollen zwei Kreisbögen mit gleichem Radius und mit je zwei darauf liegenden Punkten die Verbindung aller vier Punkte herstellen. Die Bedingung, dass am Berührungspunkt beider Kreise kein Knick auf dem Weg auftreten soll, bedeutet am Berührungspunkt eine gemeinsame Tangente, oder anders beschrieben liegt der Berührungspunkt in der Mitte der geraden Verbindung beider Kreismittelpunkte.

Die Frage, welche zwei Punkte zusammen auf einem Kreisbogen liegen sollen, kann mit dem Wissen aus Tabelle 1 schnell beantwortet werden. Das Paar 2 fällt auch hier für eine Lösung aus, weil bei zwei sich außen berührende Kreise niemals die Sehnen sich kreuzen, die durch die jeweilige Verbindung der beiden Punkte entstehen.

Zusammengefasst ergibt sich dann folgendes zu lösende Gleichungssystem, einmal mit den Werten von Paar 1 und zum zweiten mit den Werten von Paar 3. $$ (x_{m1}-x_a)^2 + (y_{m1}-y_a)^2 - r^2 = 0 \\ (x_{m1}-x_b)^2 + (y_{m1}-y_b)^2 - r^2 = 0 \\ (x_{m2}-x_c)^2 + (y_{m2}-y_c)^2 - r^2 = 0 \\ (x_{m2}-x_d)^2 + (y_{m2}-y_d)^2 - r^2 = 0 \\ (x_{m1}-x_{m2})^2 + (y_{m1}-y_{m2})^2 - 4r^2 = 0 $$ Die ersten vier Gleichungen beschreiben den Abstand der vier Punkte von den 2 Mittelpunkten der zu suchenden Kreise und die letzte Gleichung fordert die Knickfreiheit am Berührungspunkt. Die fünf Unbekannten sind die Koordinaten der Kreismittelpunkte und der Radius beider Kreise: $x_{m1}$, $y_{m1}$, $x_{m2}$, $y_{m2}$ und $r$.

Wer keine anderen Optionen zur Lösung solcher Gleichungssysteme hat, kann auf die auch schon in früheren Rätseln erwähnte Internetseite von Mathematica zurückgreifen. Eine Beschreibung in deutsch ist ebenfalls auf dieser Seite.
Es ist insbesondere darauf zu achten, dass alle Listen in geschweiften Klammern {} und die Listenelemente durch Kommata getrennt geschrieben werden müssen. Das bezieht sich auf die Liste der Gleichungen und die Liste der Variablen. Auch die Lösungen werden als Liste in dieser Form ausgegeben.
Hier folgt als kopierbarer Text für das Feld Eingabe das Geichungssystem für das Paar 1 und die Werte aller Koordinaten: Im Feld Kategorie wählen... sucht man "Gleichungssystem lösen" aus.
bei Operation wählen... klickt man auf "Gleichungssystem numerisch lösen".
Dann erscheint Liste der Variablen: und man kopiert das folgende ein: Zum Schluss noch auf Ausführen drücken und das folgende Ergebnis erscheint: Das ist eine Liste von 8 Lösungslisten. Jede Lösungsliste oder kurz Lösung enthält die Wertzuweisung zu den angegebenen Variablen. Wenn man alle Lösungen mit negativen Radien streicht bleiben noch 4 Lösungen.
Mit dem Paar 3 wird der obige Ablauf wiederholt. Auch da werden die Lösungen mit negativen Werten gestrichen. Darüber hinaus sind 2 Lösungen mit komplexen Werten ebenfalls zu streichen, also bleiben noch 2 weitere.
Das zusammengefasste Ergebnis ist in folgender Tabelle 3 aufgelistet.

Paar	xm1	ym1	xm2	ym2	r
1	-31,12089677	1,00000000	22,87190020	16,87190020	28,13867153
1	-8,32528936	1,00000000	-0,69856099	-6,69856099	5,41836753
1	-0,39089436	1,00000000	4,70402938	-1,29597062	2,79417828
1	-0,16291951	1,00000000	1,12263140	-4,87736860	3,00815985
3	-83,06760945	-148,24331653	104,73219943	131,54024929	168,48413272
3	-5,30708657	-12,16240150	6,97017899	9,33772373	12,37928344

Tabelle 3

Im folgenden Bild 3 sind die in der Tabelle 3 gelisteten Kreise dargestellt. Da die Radien sehr stark variieren kann man den Zoom-Faktor (angegeben in Pixel pro Einheit) in weiten Bereichen verändern.

Bild 3

Da jedes Kreispaar auf zwei verschiedenen Umlaufrichtungen einen gesuchten Weg erzeugen kann ist die Anzahl der Lösungen für die Rätselfrage 3 das Doppelte von Tabelle 3 also 12 Möglichkeiten. Die folgende Tabelle 4 zeigt die nach Länge des Weges vorsortierte Liste aller Möglichkeiten. Auch hier kann man durch Klick auf die Zeile in Spalte Punktanordnung das Bild des Weges in dem darunter folgenden Bild 4 sich anzeigen lassen.

	Punktanordnung	1. Bogen	2. Bogen	Gesamtlänge
		9,04532040	164,16034596	173,20566636
		169,75558833	15,46976076	185,22534910
		30,76940033	9,91653850	40,68593883
		5,28673839	26,98963565	32,27637404
		8,61783698	15,66162667	24,27946365
		10,98386374	4,86039850	15,84426224
		6,39237582	4,48266693	10,87504275
		14,54724855	17,36274611	31,90999466
		17,28434401	1050,51587031	1067,80021432
		1047,73619283	16,16418403	1063,90037687
		76,47281227	73,67902868	150,15184095
		72,61310963	73,67163100	146,28474063

Tabelle 4

Bild 4

Diese Informationen wurden zusammengestellt von