Feindliche Brüder
Zehn Brüder besitzen gemeinsam ein quadratisches Grundstück. Jeder der Brüder will darauf ein Haus bauen. Leider mögen sich die Brüder gegenseitig nicht. Deshalb wollen sie soweit wie möglich voneinander entfernt wohnen.
Die mathematische Beschreibung des Problems ist die folgende:
«In einem Einheitsquadrat sind zehn Punkte so zu verteilen,
dass der minimale Abstand zwischen zwei beliebigen Punkten
größtmöglich wird.»
Bei der besten Lösung (gefunden von K. Schlüter 1979) befinden sich acht der Punkte auf den Seiten des Quadrats und zwei Punkte im Inneren. Für die acht Punkte auf den Seiten gilt
P3 = (0, e) für ein kleines e,
P4 = (0, d + e)
P5 = (0, 1)
P2 = (u, 0) für u = sqrt(d² - e²)
P1 = (d + u, 0)
P9 = (1, v) mit v = sqrt(d² - (1 - d - u)²)
P8 = (1, d + v)
P7 = (1 - w, 1) mit w = sqrt(d² - (1 - d - v)²)
und der Punkt P6 im Inneren wird über
P6 = ((1 - w)/2, 1 - x) mit x = sqrt(d² - (1 - w)²/4)
festgelegt. Der zweite Punkt im Inneren, P10, ist der Mittelpunkt des Kreises durch die drei Punkte P2, P6 und P9.
Wenn man fordert, dass der Abstand zwischen P4 und P6 gleich d wird, dann ergibt sich eine Lösung für e zwischen 0 und 0.05 in Abhängigkeit von d. Fordert man zusätzlich, dass der Radius des Kreises um P10 gleich d wird, dann ist d zwischen 0.418 und 0.422 eindeutig bestimmt.
Für die Berechnung einer Näherung für d werden einige Hilfsfunktionen benötigt.
(defproc square (x)
(* x x))
(defproc square-sum (x y)
(+ (square x) (square y)))
(defproc distance-square (p q)
(square-sum
(- (first p) (first q))
(- (second p) (second q))))
(defproc square-difference-root (a b precision)
(square-root (- (square a) (square b)) precision))
Die Funktion square quadriert ihr Argument. Die Funktion square-sum berechnet die Summe zweier Quadrate. Die Funktion distance-square berechnet das Quadrat des Abstandes zweier Punkte, dabei werden die Punkte als Listen ihrer Koordinaten repräsentiert. Die Funktion square-root berechnet eine Näherung für eine Quadratwurzel mit einer wählbaren Genauigkeit (siehe Quadratwurzeln mit dem Halley-Verfahren berechnen). Die Funktion square-difference-root berechnet die Quadratwurzel der Differenz zweier Quadrate.
Die Hilfsfunktionen werden in den Funktionen verwendet, die die Größen u, v, w und x in Abhängigkeit von d und e berechnen.
(defproc u-from-d-and-e (d e precision)
(square-difference-root d e precision))
(defproc v-from-d-and-e (d e precision)
(square-difference-root
d
(- 1 d (u-from-d-and-e d e (* precision 1e-4)))
precision))
(defproc w-from-d-and-e (d e precision)
(square-difference-root
d
(- 1 d (v-from-d-and-e d e (* precision 1e-4)))
precision))
(defproc x-from-d-and-e (d e precision)
(square-difference-root
d
(/ (- 1 (w-from-d-and-e d e (* precision 1e-4))) 2)
precision))
Mit diesen können wiederum Funktionen aufgestellt werden, die die Punkte P2, P4, P6 und P9 in Abhängigkeit von d und e bestimmen.
(defproc p2-from-d-and-e (d e precision)
(list
(u-from-d-and-e d e precision)
0))
(defproc p4-from-d-and-e (d e precision)
(list
0
(+ d e)))
(defproc p6-from-d-and-e (d e precision)
(list
(/ (- 1 (w-from-d-and-e d e precision)) 2)
(- 1 (x-from-d-and-e d e precision))))
(defproc p9-from-d-and-e (d e precision)
(list
1
(v-from-d-and-e d e precision)))
Die Funktion e-from-d berechnet eine Lösung für e in Abhängigkeit von d mittels der Regula Falsi im Intervall von 0 bis 0.05.
(defproc distance-p4p6-from-d-and-e (d e precision)
(square-root
(distance-square
(p4-from-d-and-e d e (* precision 1e-4))
(p6-from-d-and-e d e (* precision 1e-4)))
precision))
(defproc e-from-d (d precision)
(let
((f (lambda (e)
(-
d
(distance-p4p6-from-d-and-e
d
(approximate e precision)
(* precision 1e-4))))))
(regula-falsi f 0 0.05 precision)))
Schließlich berechnet die Funktion r-from-d zuerst e, dann P2, P6 und P9 und dann den Radius des Kreises durch die drei Punkte (siehe Kreis durch drei Punkte) in Abhängigkeit von d.
(defproc r-from-d (d precision)
(let
((e (e-from-d d (* precision 1e-4))))
(let
((p2 (p2-from-d-and-e d e (* precision 1e-2)))
(p6 (p6-from-d-and-e d e (* precision 1e-2)))
(p9 (p9-from-d-and-e d e (* precision 1e-2))))
(square-root
(third
(circle-3p
(first p2)
(second p2)
(first p6)
(second p6)
(first p9)
(second p9)))
precision))))
Mittels der Regula Falsi wird ein d zwischen 0.418 und 0.422 gesucht, so dass es selbst und der Radius des Kreises in Abhängigkeit von ihm gleich sind.
(defproc approximate-d (precision)
(let
((f (lambda (d)
(let
((dt (approximate d precision)))
(- dt (r-from-d dt (* precision 1e-4)))))))
(regula-falsi f 0.418 0.422 precision)))
Diese letzte Funktion errechnet d zu
0.42127 95439 83903 43276
88217 60650 29809 16103
67214 07261
wenn eine Genauigkeit von 50 Stellen gewünscht wird.
Den paarweisen Abstand d der zehn Häuser der feindlichen Brüder kann man wesentlich effizienter berechnen als über das Nachvollziehen der geometrischen Konstruktion. Der Abstand ergibt sich auch als Nullstelle eines speziellen Polynoms 18ten Grades.
Wenn die Nullstelle mit dem Newton-Verfahren bestimmt werden soll, dann wird zusätzlich die Ableitung des Polynoms benötigt. Die Ableitung eines Polynoms ist wiederum ein Polynom. Dessen Koeffizienten berechnet die Funktion derive-coefficients.
(defproc derive-coefficients (factor coefficients)
(if
(> factor 0)
(cons
(* factor (first coefficients))
(derive-coefficients (- factor 1) (rest coefficients)))
nil))
Die Funktion wird aufgerufen mit dem Grad des abzuleitenden Polynoms und dessen Koeffizienten, beginnend mit dem für den höchsten Grad.
Für die Berechung der Nullstelle hinterlegt man zunächst die Koeffizienten des speziellen Polynoms in einer Variable:
(setq *coefficients* (quote
(1180129 -11436428 98015844 -462103584 1145811528
-1398966480 227573920 1526909568 -1038261808 -2960321792
7803109440 -9722063488 7918461504 -4564076288 1899131648
-563649536 114038784 -14172160 819200)))
Ebenso verfährt man mit den Koeffizienten der Ableitung.
(setq *derived-coefficients* (derive-coefficients 18 *coefficients*))
Dann definiert man das Polynom und seine Ableitung als Funktionen, dabei wird das Horner-Schema benutzt:
(defproc f (x)
(horner *coefficients* x 0))
(defproc df (x)
(horner *derived-coefficients* x 0))
Schließlich kann man das Newton-Verfahren mit einem geeigneten Startwert aufrufen
(defproc approximate-d (precision)
(newton f df 0.4 precision))
und erhält dann eine Näherung für die angegebene Zahl von Stellen, z.B 1000:
0.42127 95439 83903 43276 88217 60650 29809 16103 67214 07261
22321 65437 54540 65172 93922 43779 15363 29068 84719 24624
39704 24712 72076 99105 97915 09929 20869 17123 48324 27629
01447 11516 56286 94730 09905 73094 16117 67848 29561 80962
15999 45859 38679 03057 12546 49247 86948 42887 50917 75727
51782 42071 66857 59363 44941 72461 65998 81807 82076 20389
14125 65114 05238 12064 38415 12679 32086 76812 06102 06967
94299 76135 37234 21613 24378 59535 26179 87168 27175 91229
61522 41943 42470 00890 26211 55241 43115 72102 63805 29885
46322 11465 88880 19699 24571 12132 81498 03895 88061 30304
02968 89085 26450 58197 83963 19092 62305 24640 95894 51203
09473 39548 17421 02101 08417 51706 67750 58306 97550 66920
65559 99958 58674 89096 33756 53353 87779 92407 24424 62289
63690 43926 31336 26595 24119 30261 63673 87318 38433 90952
89604 23860 48303 38633 27292 66718 75152 58130 02997 24362
84286 89671 04570 97528 36526 29329 25014 65311 51897 64821
62050 64173 42346 20693 03382 76268 81510 11536 19208 42089
57922 43511 70595 75223 31377 07160 50190 29592 32772 25665
09010 06939 77282 76653 82086 87924 85371 67620 32272 76087
72719 10043 63657 95106 09937 95142 00599 51090 72518 53342
Quellen
Jochen Werner
"Numerische Mathematik 1"
Seiten 83f
Jochen Werner
"Merkwürdige Mathematik"
Seiten 348ff
Steven R. Finch
"Mathematical Constants"
Cambridge University Press
August 2003
Seite 487
Link
http://en.wikipedia.org/wiki/Circle_packing_in_a_square
Die mathematische Beschreibung des Problems ist die folgende:
«In einem Einheitsquadrat sind zehn Punkte so zu verteilen,
dass der minimale Abstand zwischen zwei beliebigen Punkten
größtmöglich wird.»
Bei der besten Lösung (gefunden von K. Schlüter 1979) befinden sich acht der Punkte auf den Seiten des Quadrats und zwei Punkte im Inneren. Für die acht Punkte auf den Seiten gilt
P3 = (0, e) für ein kleines e,
P4 = (0, d + e)
P5 = (0, 1)
P2 = (u, 0) für u = sqrt(d² - e²)
P1 = (d + u, 0)
P9 = (1, v) mit v = sqrt(d² - (1 - d - u)²)
P8 = (1, d + v)
P7 = (1 - w, 1) mit w = sqrt(d² - (1 - d - v)²)
und der Punkt P6 im Inneren wird über
P6 = ((1 - w)/2, 1 - x) mit x = sqrt(d² - (1 - w)²/4)
festgelegt. Der zweite Punkt im Inneren, P10, ist der Mittelpunkt des Kreises durch die drei Punkte P2, P6 und P9.
Wenn man fordert, dass der Abstand zwischen P4 und P6 gleich d wird, dann ergibt sich eine Lösung für e zwischen 0 und 0.05 in Abhängigkeit von d. Fordert man zusätzlich, dass der Radius des Kreises um P10 gleich d wird, dann ist d zwischen 0.418 und 0.422 eindeutig bestimmt.
Für die Berechnung einer Näherung für d werden einige Hilfsfunktionen benötigt.
(defproc square (x)
(* x x))
(defproc square-sum (x y)
(+ (square x) (square y)))
(defproc distance-square (p q)
(square-sum
(- (first p) (first q))
(- (second p) (second q))))
(defproc square-difference-root (a b precision)
(square-root (- (square a) (square b)) precision))
Die Funktion square quadriert ihr Argument. Die Funktion square-sum berechnet die Summe zweier Quadrate. Die Funktion distance-square berechnet das Quadrat des Abstandes zweier Punkte, dabei werden die Punkte als Listen ihrer Koordinaten repräsentiert. Die Funktion square-root berechnet eine Näherung für eine Quadratwurzel mit einer wählbaren Genauigkeit (siehe Quadratwurzeln mit dem Halley-Verfahren berechnen). Die Funktion square-difference-root berechnet die Quadratwurzel der Differenz zweier Quadrate.
Die Hilfsfunktionen werden in den Funktionen verwendet, die die Größen u, v, w und x in Abhängigkeit von d und e berechnen.
(defproc u-from-d-and-e (d e precision)
(square-difference-root d e precision))
(defproc v-from-d-and-e (d e precision)
(square-difference-root
d
(- 1 d (u-from-d-and-e d e (* precision 1e-4)))
precision))
(defproc w-from-d-and-e (d e precision)
(square-difference-root
d
(- 1 d (v-from-d-and-e d e (* precision 1e-4)))
precision))
(defproc x-from-d-and-e (d e precision)
(square-difference-root
d
(/ (- 1 (w-from-d-and-e d e (* precision 1e-4))) 2)
precision))
Mit diesen können wiederum Funktionen aufgestellt werden, die die Punkte P2, P4, P6 und P9 in Abhängigkeit von d und e bestimmen.
(defproc p2-from-d-and-e (d e precision)
(list
(u-from-d-and-e d e precision)
0))
(defproc p4-from-d-and-e (d e precision)
(list
0
(+ d e)))
(defproc p6-from-d-and-e (d e precision)
(list
(/ (- 1 (w-from-d-and-e d e precision)) 2)
(- 1 (x-from-d-and-e d e precision))))
(defproc p9-from-d-and-e (d e precision)
(list
1
(v-from-d-and-e d e precision)))
Die Funktion e-from-d berechnet eine Lösung für e in Abhängigkeit von d mittels der Regula Falsi im Intervall von 0 bis 0.05.
(defproc distance-p4p6-from-d-and-e (d e precision)
(square-root
(distance-square
(p4-from-d-and-e d e (* precision 1e-4))
(p6-from-d-and-e d e (* precision 1e-4)))
precision))
(defproc e-from-d (d precision)
(let
((f (lambda (e)
(-
d
(distance-p4p6-from-d-and-e
d
(approximate e precision)
(* precision 1e-4))))))
(regula-falsi f 0 0.05 precision)))
Schließlich berechnet die Funktion r-from-d zuerst e, dann P2, P6 und P9 und dann den Radius des Kreises durch die drei Punkte (siehe Kreis durch drei Punkte) in Abhängigkeit von d.
(defproc r-from-d (d precision)
(let
((e (e-from-d d (* precision 1e-4))))
(let
((p2 (p2-from-d-and-e d e (* precision 1e-2)))
(p6 (p6-from-d-and-e d e (* precision 1e-2)))
(p9 (p9-from-d-and-e d e (* precision 1e-2))))
(square-root
(third
(circle-3p
(first p2)
(second p2)
(first p6)
(second p6)
(first p9)
(second p9)))
precision))))
Mittels der Regula Falsi wird ein d zwischen 0.418 und 0.422 gesucht, so dass es selbst und der Radius des Kreises in Abhängigkeit von ihm gleich sind.
(defproc approximate-d (precision)
(let
((f (lambda (d)
(let
((dt (approximate d precision)))
(- dt (r-from-d dt (* precision 1e-4)))))))
(regula-falsi f 0.418 0.422 precision)))
Diese letzte Funktion errechnet d zu
0.42127 95439 83903 43276
88217 60650 29809 16103
67214 07261
wenn eine Genauigkeit von 50 Stellen gewünscht wird.
Den paarweisen Abstand d der zehn Häuser der feindlichen Brüder kann man wesentlich effizienter berechnen als über das Nachvollziehen der geometrischen Konstruktion. Der Abstand ergibt sich auch als Nullstelle eines speziellen Polynoms 18ten Grades.
Wenn die Nullstelle mit dem Newton-Verfahren bestimmt werden soll, dann wird zusätzlich die Ableitung des Polynoms benötigt. Die Ableitung eines Polynoms ist wiederum ein Polynom. Dessen Koeffizienten berechnet die Funktion derive-coefficients.
(defproc derive-coefficients (factor coefficients)
(if
(> factor 0)
(cons
(* factor (first coefficients))
(derive-coefficients (- factor 1) (rest coefficients)))
nil))
Die Funktion wird aufgerufen mit dem Grad des abzuleitenden Polynoms und dessen Koeffizienten, beginnend mit dem für den höchsten Grad.
Für die Berechung der Nullstelle hinterlegt man zunächst die Koeffizienten des speziellen Polynoms in einer Variable:
(setq *coefficients* (quote
(1180129 -11436428 98015844 -462103584 1145811528
-1398966480 227573920 1526909568 -1038261808 -2960321792
7803109440 -9722063488 7918461504 -4564076288 1899131648
-563649536 114038784 -14172160 819200)))
Ebenso verfährt man mit den Koeffizienten der Ableitung.
(setq *derived-coefficients* (derive-coefficients 18 *coefficients*))
Dann definiert man das Polynom und seine Ableitung als Funktionen, dabei wird das Horner-Schema benutzt:
(defproc f (x)
(horner *coefficients* x 0))
(defproc df (x)
(horner *derived-coefficients* x 0))
Schließlich kann man das Newton-Verfahren mit einem geeigneten Startwert aufrufen
(defproc approximate-d (precision)
(newton f df 0.4 precision))
und erhält dann eine Näherung für die angegebene Zahl von Stellen, z.B 1000:
0.42127 95439 83903 43276 88217 60650 29809 16103 67214 07261
22321 65437 54540 65172 93922 43779 15363 29068 84719 24624
39704 24712 72076 99105 97915 09929 20869 17123 48324 27629
01447 11516 56286 94730 09905 73094 16117 67848 29561 80962
15999 45859 38679 03057 12546 49247 86948 42887 50917 75727
51782 42071 66857 59363 44941 72461 65998 81807 82076 20389
14125 65114 05238 12064 38415 12679 32086 76812 06102 06967
94299 76135 37234 21613 24378 59535 26179 87168 27175 91229
61522 41943 42470 00890 26211 55241 43115 72102 63805 29885
46322 11465 88880 19699 24571 12132 81498 03895 88061 30304
02968 89085 26450 58197 83963 19092 62305 24640 95894 51203
09473 39548 17421 02101 08417 51706 67750 58306 97550 66920
65559 99958 58674 89096 33756 53353 87779 92407 24424 62289
63690 43926 31336 26595 24119 30261 63673 87318 38433 90952
89604 23860 48303 38633 27292 66718 75152 58130 02997 24362
84286 89671 04570 97528 36526 29329 25014 65311 51897 64821
62050 64173 42346 20693 03382 76268 81510 11536 19208 42089
57922 43511 70595 75223 31377 07160 50190 29592 32772 25665
09010 06939 77282 76653 82086 87924 85371 67620 32272 76087
72719 10043 63657 95106 09937 95142 00599 51090 72518 53342
Quellen
Jochen Werner
"Numerische Mathematik 1"
Seiten 83f
Jochen Werner
"Merkwürdige Mathematik"
Seiten 348ff
Steven R. Finch
"Mathematical Constants"
Cambridge University Press
August 2003
Seite 487
Link
http://en.wikipedia.org/wiki/Circle_packing_in_a_square
Abbildung: die ungefähre Lage der zehn Punkte im Einheitsquadrat
brüder.zir
10-brothers.sheet.xml
d10.sheet.xml