Lösungsbeschreibung des Preisrätsels vom Januar 2018

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	x_k	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 Punkt1

ist der gleiche Weg wie Punkt4

. 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.

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

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 Punkt1

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

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

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:

{
(xm1-xp1)^2+(ym1-yp1)^2-r^2=0,
(xm1-xp2)^2+(ym1-yp2)^2-r^2=0,
(xm2-xp3)^2+(ym2-yp3)^2-r^2=0,
(xm2-xp4)^2+(ym2-yp4)^2-r^2=0,
(xm1-xm2)^2+(ym1-ym2)^2-4*r^2=0,

xp1=-3,
yp1=0,
xp2=-3,
yp2=2,
xp3=2,
yp3=-2,
xp4=4,
yp4=-4
}

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:

{
xm1,
ym1,
xm2,
ym2,
r
}

Zum Schluss noch auf Ausführen drücken und das folgende Ergebnis erscheint:

{{xm1 -> -31.1209, ym1 -> 1., ym2 -> 16.8719, xm2 -> 22.8719,

>     r -> -28.1387}, {xm1 -> -31.1209, ym1 -> 1., ym2 -> 16.8719,

>     xm2 -> 22.8719, r -> 28.1387},

>    {xm1 -> -8.32529, ym1 -> 1., ym2 -> -6.69856, xm2 -> -0.698561,

>     r -> -5.41837}, {xm1 -> -8.32529, ym1 -> 1., ym2 -> -6.69856,

>     xm2 -> -0.698561, r -> 5.41837},

>    {xm1 -> -0.390894, ym1 -> 1., ym2 -> -1.29597, xm2 -> 4.70403,

>     r -> -2.79418}, {xm1 -> -0.390894, ym1 -> 1., ym2 -> -1.29597,

>     xm2 -> 4.70403, r -> 2.79418},

>    {xm1 -> -0.16292, ym1 -> 1., ym2 -> -4.87737, xm2 -> 1.12263,

>     r -> -3.00816}, {xm1 -> -0.16292, ym1 -> 1., ym2 -> -4.87737,

>     xm2 -> 1.12263, r -> 3.00816}}

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	x_m1	y_m1	x_m2	y_m2	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.

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


Kurzbewertung dieser Information:
sehr gut	gut	befriedigend
ausreichend	mangelhaft	ungenügend