Vind een configuratie van tien (twaalf) punten op een bol zo dat de minimale afstand tussen twee van die punten zo groot mogelijk is.

Vind nu hier de oplossingen van de prijswinnaars.

MIJN EERSTE AANPAK

We gaan uit van een bol met straal 1. De onderstaande antwoorden zijn dus uitgedrukt in duizendtallen kilometers.
Een 'grote cirkel' is een cirkel op de bol, liggende in een plat vlak dat door het middelpunt van de bol gaat. Men noemt deze grote cirkels ook geodetische lijnen.

De hieronder te bespreken configuratie voor tien piraten is nog niet definitief.
Binnen twee weken, bij de bespreking der inzendingen, zal ik twee configuraties met tien punten geven waarbij de minimale afstand tussen twee van die punten nog een heel klein beetje groter is.

1) In een eerste poging met betrekking tot tien piraten beperk ik me tot configuraties die een noordpool en een zuidpool hebben. Ik begin dus met twee punten op de beide polen zo ver mogelijk van elkaar af te zetten. De andere acht punten liggen dan tussen x graden noorder- en zuiderbreedte, voor nader te bepalen x.
De kortste wegen over de bol zijn de grote cirkels van de bol. Maar omdat bij grotere cirkelbogen grotere koorden horen en vice versa, is de optimale configuratie hetzelfde indien men de afstanden door de ruimte meet en indien men ze langs grote cirkels van de bol meet.
Het gebied tussen x graden noorder- en zuiderbreedte kan worden verdeeld in acht congruente "vierhoeken". Een zo'n vierhoek komt overeen met een gebied op de bol begrensd door de breedtecirkels op x graden noorder- en zuiderbreedte en de meridianen op (k-1)*45 en k*45 graden oosterlengte (k=1,2,..,8).
Voor een optimale configuratie moeten de acht punten afwisselend links boven en rechts onder in zo'n vierhoek worden gekozen, zodat de verbindingslijnen (geodetische) diagonalen van de vierhoeken zijn, en samen een zigzagpatroon vormen. Anders komen er twee punten dichter bij elkaar dan nodig. Dus vier punten vormen (in de ruimte) een vierkant op x graden noorderbreedte, en vier punten nog een vierkant op x graden zuiderbreedte, waarbij het tweede vierkant over 45 graden gedraaid is ten opzichte van het eerste.

De tien punten hebben dan de volgende coördinaten: (met t:=(90-x)*pi/180)
(0,0,1),
(sin(t),0,cos(t)), (0,sin(t),cos(t)), (-sin(t),0,cos(t)), (0,-sin(t),cos(t)),
(sqrt(2)*sin(t)/2,sqrt(2)*sin(t)/2,-cos(t)), (-sqrt(2)*sin(t)/2,sqrt(2)*sin(t)/2,-cos(t)),
(-sqrt(2)*sin(t)/2,-sqrt(2)*sin(t)/2,-cos(t)), (sqrt(2)*sin(t)/2,-sqrt(2)*sin(t)/2,-cos(t)),
(0,0,-1).

De afstand tussen twee willekeurige punten wordt gemeten over de grote cirkel door die twee punten. De afstand is gelijk aan de hoek (in radialen) tussen de vectoren vanuit het middelpunt (0,0,0) van de bol naar de punten. Deze hoek berekenen we met behulp van het inproduct.
Er zijn drie verschillende afstanden tussen naburige punten:
1) t (tussen een pool en een ander punt op hetzelfde halfrond)
2) arccos(cos²(t)) (tussen twee buurpunten in hetzelfde vierkant)
3) arccos(sqrt(2)*sin²(t)/2 - cos²(t)) (tussen naburige punten in verschillende vierkanten).

Grafische analyse wijst uit dat het minimum der afstanden 1), 2) and 3) maximaal is voor de waarde van t ongelijk aan 0 waarvoor 1) gelijk is aan 3).
We vinden dan:
cos(t) = sqrt(2)*sin²(t)/2 - cos²(t),
dus cos(t)(1+cos(t)) = sqrt(2)*(1-cos²(t))/2,
dus cos(t) = sqrt(2)*(1-cos(t))/2,
dus cos(t) = sqrt(2)/(2+sqrt(2)) = 1/(1+sqrt(2)), dus de minimumafstand is dan t = arccos(1/(1+sqrt(2))) = 1.143717740 .

2) Er bestaat een platonisch veelvlak met twaalf hoekpunten. Het platonisch veelvlak heeft dertig ribben en twintig zijvlakken. De zijvlakken zijn allemaal congruente gelijkzijdige driehoeken, die overeenkomen met gelijkzijdige geodetische driehoeken op de bol. Omdat deze driehoeken de bol overdekken, geeft dit dan de optimale configuratie. Kiest men een andere configuratie, dan komen er twee punten dichter bij elkaar te liggen dan de zijde van zo'n driehoek.
Dit veelvlak heeft ook een noordpool en een zuidpool. We vinden dan de configuratie op soortgelijke wijze als bij tien piraten (zie het plaatje). Een verschil is dat er nu vijf punten op een breedtecirkel passen in plaats van vier. Een ander verschil is dat de kleinste afstand tussen twee punten op dezelfde breedtecirkel bij tien piraten groter is dan de afstand van zo'n punt tot de naaste pool, en bij twaalf piraten precies gelijk daaraan.

De afstand over de bol tussen naburige punten gelijk is aan de hoek t zodanig dat
de ruimtelijke afstand tussen (0,0,1) en (sin(t),0,cos(t))
gelijk is aan
de ruimtelijke afstand tussen (sin(t),0, cos(t)) en (sin(t)*cos(2*pi/5),sin(t)*sin(2*pi/5),cos(t)).

Deze hoek kan als volgt berekend worden met Pythagoras:
sqrt(sin²(t)+(1-cos(t))²) = sin(t)*sqrt(sin²(2*pi/5)+(1-cos(2*pi/5))²),
dus sqrt(2-2*cos(t)) = sin(t)*sqrt(2-2*cos(2*pi/5)),
dus 2*sin(t/2) = 2*sin(t/2)*cos(t/2)*2*sin(pi/5),
dus cos(t/2) = 1/(2*sin(pi/5)).
Dus de minimumafstand is nu t = 2*arccos(1/(2*sin(pi/5))) = 1.107148718 .

Achteraf vond ik, na enig zoeken op het internet, in eerste instantie deze site. Hij scheen aan te geven dat beide boven besproken configuraties optimaal zijn, dus ook die met tien piraten.
Later vond ik bij verder doorzoeken echter afwijkende informatie die betrekking heeft op publicaties van Tóth (1943) en Danzer (1963). De website die ik toen vond is deze.
Het blijkt dat de boven besproken aanpak, uitgaande van een noordpool en een zuidpool, lang niet bij elk aantal piraten de allerbeste configuratie oplevert. K.Schütte heeft in 1950 voor tien piraten een ingewikkelde configuratie gevonden die een iets grotere minimumafstand oplevert (het verschil is echter minder dan 1 percent). Vervolgens heeft Ludwig Danzer in 1963 bewezen dat deze configuratie optimaal is. Alleen hij en enkele andere specialisten in het vakgebied begrijpen hoe dit in elkaar steekt.
Professor Danzer behoort trouwens tot de deelnemers in deze kerstprijsvraag. Hij stuurde een heruitgave van zijn mooie Habilitationsschrift van ruim veertig jaar geleden.
Voor twaalf piraten is de door mij gevonden configuratie dezelfde als die van Danzer. Let er wel op dat een platonisch veelvlak ook niet altijd een optimale configuratie levert. Bij twintig piraten is dit bijvoorbeeld niet het geval.

DE OPLOSSINGEN VAN DE PRIJSWINNAARS ZULLEN BINNEN TWEE WEKEN OP DEZE SITE WORDEN GEPUBLICEERD.

klik hier om naar mijn hoofdpagina te gaan