Oplossingen Kerstprobleem 2003


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


DE INZENDINGEN VAN DE DEELNEMERS AAN DE PRIJSVRAAG

Laat ik beginnen met de kleinere bijdragen, in de vorm van losse opmerkingen en kleine notities. De opmerkingen worden voorzien van een sterretje, mijn commentaar volgt meteen daarna met een plusje.

* Is er voor tien piraten wel een oplossing gevonden? (directeur van een school in Limburg).
+ Ja, door K.Schütte in 1950. Het bewijs werd in 1963 gegeven door Ludwig Danzer.

* Wij zijn niet slim genoeg voor dit probleem (vader en zoon, beiden zijn wiskundeleraar).
+ Het vraagstuk is zo moeilijk dat dr Danzer destijds ruim zestig bladzijden nodig had om de oplossing beknopt op te schrijven.

* Ik plaats tien punten op de speelbal van Mark, en dan maar puzzelen en schuiven die handel. (Roy Kneefel)
+ Volhouden, Roy.

* Ik koop een ballon en maak een netwerk van touwtjes en knopen. (Ing. Karel Hendriks)
+ Ik ben benieuwd waar dat toe leidt.

* Ik teken een spiraal op de bol, van pool naar pool. Dan zet ik de punten eerst op de rand van een vooraanzicht van de bol, op gelijke afstanden van elkaar. Daarna beweeg ik de punten afwisselend over de bol naar voren en naar achteren, tot ze op de spiraal aankomen. (mijn vrouw Marian)
+ Goed nagedacht, Marian.

* Ik denk gebruik te moeten maken van de regels van sinus, cosinus en tangens. Kun je me die toesturen? Het is me wel al duidelijk dat alle punten even ver van elkaar af moeten liggen. (mijn broer Jacques)
+ Dat is correct voor twaalf piraten, maar voor tien is het niet realiseerbaar.

* Ik zet vijf piraten op de noordpool en vijf op de zuidpool. Van de vijf lopen er vier naar het zuiden (resp. noorden), in vier richtingen met telkens negentig graden verschil. Ze lopen zo ver door tot er een evenwicht ontstaat. (mijn zoon Michiel)
+ Heel goed gedacht.

* Ik heb voor het probleem in de vakantie niet veel tijd gehad. De afstanden tussen de punten en de hoeken tussen de ribben moeten gelijk zijn. De afstand tussen twee punten is: (t/360) keer 2 keer pi keer bolstraal, waarbij t de hoek tussen de punten, gezien vanuit het middelpunt van de bol. (Floris Courtens)
+ De eerste gedachte is voor twaalf piraten wel, maar voor tien niet realiseerbaar. De afstandsformule is correct.

* Heb jij wel een goed bewijs dat jouw configuratie optimaal is? Wij zien alleen een configuratie waarvan we min of meer kunnen bewijzen dat die een lokaal maximum oplevert. (Twee wiskundigen van de KUN).
+ Het probleem bleek inderdaad moeilijker dan ik aanvankelijk dacht. Mijn bewijs voor tien piraten is alleen correct als men aanneemt dat de configuratie een noordpool en een zuidpool heeft.

* Voor de straal van de bol neem ik 1 megameter.
Laat a de kleinste geodetische afstand tussen twee verschillende punten zijn. Als men om elk der punten een cirkel trekt met geodetische straal a/2, dan ontstaan 10 (12) cirkelvormige gebieden die twee aan twee disjunct zijn of elkaar raken.
Laat b de oppervlakte zijn van het gedeelte van de bol gelegen binnen zo'n cirkelvormig gebied. Dan is de som van deze oppervlakten hoogstens gelijk aan de oppervlakte van de bol. Dus n keer b is kleiner of gelijk aan 4 keer pi, met n=10 respectievelijk n=12.
Een eenvoudige berekening levert b = 2.pi.(1-cos(a/2)) .
Er volgt dat cos(a/2) voor tien piraten minstens 4/5 is, en voor twaalf minstens 5/6.
We vinden als noodzakelijke voorwaarde voor tien piraten dat a hoogstens 1.287002218 is, en voor twaalf piraten hoogstens 1.171371087.
Maar zijn deze voorwaarden ook voldoende?
Mooi probleem! (professor dr A.H.M.Levelt, Nijmegen)
+ Dank u wel voor uw korte maar belangrijke notitie, professor!
U berekende b via integratie over een cirkelvormig bolsegment met behulp van bolcoördinaten.
De voorwaarden zijn niet voldoende, omdat de 10 of 12 cirkels de bol niet geheel overdekken (voor 10 raken ze elkaar niet eens altijd).

Dan volgen hier nu de bijdragen van de inzenders die daadwerkelijk willen meedingen naar de prijzen.


Om te beginnen een mooie bijdrage van de heer Martien Luijcks uit Haarlem.

Oplossing voor 10 piraten:

De oplossing voor 10 piraten ligt mijns inziens als volgt:
Een op de noordpool, een op de zuidpool. Verdeel de planeet in acht verticale schijven, en doe op keerkringhoogten om en om noord en zuid een piraat op de aldus ontstane meridianen, zo de aarde rond. Er ontstaat een zigzagpatroon van v-tjes en tentjes, als je het verbindt.

Oplossing voor 12 piraten:

De oplossing voor twaalf piraten is mijns inziens minder elegant:
Een op de noordpool, een op de zuidpool. Verdeel de piraten om en om noord en zuid, maar nu op respectievelijk een derde en twee derde hoogte van de bol op de nieuwe meridianen. Opnieuw een zigzagpatroon, maar nu met grotere amplitude.

Aanvullende analyse:

Op risico van de grote miskleun toch even een aanvullende analyse. Er is mijns inziens sprake van gelijkzijdige driehoeken. Een keerkring zit op 23 graden van de evenaar, eenderde op 30 graden. De keerkring leek mij gezien zijn goddelijke precisie de meest aangewezen keus.

Mijn commentaar:

Bedankt voor deze goede bijdrage. Jouw aanpak stemt overeen met de mijne.
De afstanden tussen de punten kloppen niet precies, maar zijn wel heel aardig geschat. In feite moet het niet 23 en 30 graden zijn, maar grofweg 24.5 en 26.5.
Voor 10 piraten kunnen de afstanden (van een piraat naar de dichtstbijzijnde andere) niet allemaal aan elkaar gelijk zijn, voor 12 wel.


De volgende bijdrage ontving ik van de heer Peter Janssen uit Lanaken (B.).

Oplossing voor 12 piraten

Ik weet dat er een regelmatig veelvlak is met twaalf hoekpunten, dertig ribben en twintig zijvlakken (elk zijvlak is een gelijkzijdige driehoek).
De hoekpunten liggen als volgt op de bol (met straal 1 keer 1000 km):
1 helemaal bovenaan in (0,0,1), 1 helemaal onderaan in (0,0,-1), 5 in een vlak z=c en 5 in een vlak z=-c (in beide vlakken vormen die 5 punten een regelmatige vijfhoek).
De punten in z=c liggen op de cirkel x2+y2=r2=1-c2.
Ik bereken c als volgt: de afstand door de ruimte tussen (r*cos(72),r*sin(72),c) en (r,0,c) moet gelijk zijn aan die tussen (r,0,c) en (0,0,1), dus
r2(2-2*cos(72)) = r2+(c-1)2 = 2-2*c.
Dus r2 = 1-c2 = (2-2*c)/(4*sin2(36)).
De afstand over de bol tussen (0,0,1) en (r,0,c) is de hoek s zo dat cos(s)=c, dus arccos(c).
Met de rekenmachine vind ik s=1.107148718.
De vijfhoek in z=-c ligt 36 graden gedraaid t.o.v. die in z=c.

Oplossing voor 10 piraten

Voor het probleem met 10 piraten vervang ik de 2 keer 5 punten op z=c en z=-c door 2 keer 4 punten op z=d en z=-d.
De punten in z=d vormen een vierkant, die in z=-d ook, maar het tweede vierkant is 45 graden gedraaid t.o.v. het eerste.
Ik eis nu dat de afstand door de ruimte tussen (0,0,1) en (R,0,d) gelijk is aan die tussen (R,0,d) en (R*cos(45),R*sin(45),-d) (de afstand tussen twee naburige punten in z=d is groter).
Ik bereken d als volgt: R2+(d-1)2 = R2(2-2^(1/2))+4*d2, dus
2-2*d = 2-2^(1/2) + d2(2+2^(1/2)).
De kleinste afstand over de bol is nu arccos(d) = 1.14371774.

Mijn commentaar:

Uw presentatie is zeer helder. De uitkomsten komen overeen met die van mij. Voor 10 piraten is de configuratie niet helemaal optimaal.


De volgende zeer originele bijdrage mocht ik ontvangen van de heer Harrie Schreuders uit Sittard. Ik geef zijn formuleringen samenvattend weer.

Oplossing voor 10 piraten:

Volgens mij moet ik slechts de volgende kansrijke gevallen bekijken:
1) Een punt onderaan op de bol, dan vijf punten in een vlak wat meer naar boven, dan vier punten in een derde vlak nog wat meer naar boven. De vlakken hoeven niet evenwijdig te zijn. De vijf punten vormen een regelmatige vijfhoek, de vier een ruit.
2) Een punt onderaan, dan telkens meer naar boven drie keer drie punten in drie horizontale vlakken. Drie punten in een horizontaal vlak vormen een gelijkzijdige driehoek, met variërende lengte van de zijde. De driehoeken in het eerste en derde vlak zijn gelijk geöriënteerd, die in het tweede ligt gedraaid over zestig graden ten opzichte van de andere twee.
3) Een punt onderaan, dan meer naar boven twee keer vier punten in twee horizontale vlakken, tenslotte een punt bovenaan op de bol. Vier punten in een horizontaal vlak vormen een vierkant. Het tweede vierkant is vijfenveertig graden gedraaid ten opzichte van het eerste.

Ik bekijk de gevallen door met Cabri constructies te maken in vooraanzichten, bovenaanzichten en zijaanzichten van de bol. Ik streef naar zo veel mogelijk symmetrie in de configuratie en naar zo veel mogelijk gelijke afstanden tussen naburige punten. Ik varieer de lengte der koorden, waardoor de bolstraal mee verandert. Ik hou in het oog wanneer de verhouding van minimale koordelengte en bolstraal maximaal is.
In geval 1) vind ik de maximale verhouding 1.08810. De afstand over de bol wordt dan 1150.51 km.
In geval 2) vind ik de maximale verhouding 1.09053. De afstand over de bol wordt dan 1153.41 km.
In geval 3) vind ik de maximale verhouding 1.08239. De afstand over de bol wordt dan 1143.72 km.

Oplossing voor 12 piraten:

Een icosaëder is een platonisch regelmatig veelvlak met 12 hoekpunten, en daarmee is dat de beste oplossing. De afstand over de bol wordt dan 1107.15 km.

Mijn commentaar:

De constructies die u bijleverde getuigen van veel creativiteit, raffinement en ruimtelijk inzicht. En van kennis van vlakke meetkunde.
U buit de grote mogelijkheden van Cabri volledig uit. Met Cabri kunnen elementen van een constructie in onderlinge afhankelijkheid van elkaar gevarieerd worden, en Cabri verricht zeer precieze metingen.
Uw uitkomsten in geval 3) stemmen overeen met de mijne. U hebt ook de exacte uitkomst 1000*wortel(4-wortel(8)) gevonden.
Uw uitkomsten in geval 2) benaderen die van professor Danzer nog dichter. Ik heb ze geverifieerd met een Pascalprogramma, waarbij ik bolcoördinaten gegeven heb aan de hoekpunten van de drie driehoeken (zie het plaatje). Bij de optimale elevaties vond ik uw uitkomst 1.09053 . Proficiat met deze configuratie.
Uw uitkomsten in geval 1) heb ik niet meer geverifieerd. Deze configuratie lijkt wel een beetje op de optimale van professor Danzer.
Uw afstanden over de bol kloppen met de formule die het verband tussen koorde en boog geeft:
boog = 2*arctan(k/wortel(4-k2)).


Aan professor Danzer stuurde ik een mailtje om te vragen of hij ook met een inzending aan deze kerstprijsvraag wilde deelnemen. Hij stuurde een herdruk van zijn Habilitationsschrift van 1963. Deze kunt u zelf vinden in Discrete Mathematics 60 (1986), p.3-66 .
Ik destilleer uit dit boekje de volgende gedachten die aan zijn methode mede ten grondslag liggen.

Oplossing voor 10 piraten:

We kunnen trachten een gegeven configuratie te verbeteren door een hoekpunt een beetje te verschuiven. Als er in de configuratie een convexe geodetische vijfhoek voorkomt, kunnen we een hoekpunt naar binnen flippen, zodat een vijfhoek ontstaat met even lange zijden als voor het flippen, maar die minder plaats in beslag neemt.
Door dit verbetertraject met heel verschillende configuraties te beginnen, hopen we niet te blijven steken bij een relatief maximum, maar het globale maximum te vinden.
Om in te schatten of de kortste afstand in een bepaalde soort configuraties in theorie nog groter kan worden gemaakt, kunnen we proberen de som der oppervlakten van de daarin voorkomende geodetische veelhoeken te schatten, en deze vergelijken met de totale oppervlakte van de bol.
Zo vonden we uiteindelijk een configuratie waarvan we ook konden bewijzen dat die optimaal is.
De configuratie van Danzer ziet er als volgt uit: zie hier.
De kleinste afstand is ongeveer 1.091426 megameter door de ruimte, en ongeveer 1.15448 megameter over de bol.

Bij het bewijs spelen combinatorische argumenten een rol. Men kan bijvoorbeeld eenvoudig bewijzen dat van vijf gegeven punten op de bol er altijd vier in één halfrond liggen (bij geschikte keuze der polen). En we moeten het aantal driehoeken in de configuratie tellen: 16 voor tien piraten.
Verder moeten we de hoeken tussen de ribben beschouwen. De som der hoeken in een gegeven hoekpunt kan niet groter of kleiner zijn dan 360 graden. Op de bol vertoont de som der hoeken in een veelhoek een exces (teveel), dat (in radialen gemeten) gelijk is aan de oppervlakte van de veelhoek. Beschouw bijvoorbeeld de driehoek gevormd door de evenaar en de meridianen op 0 en 90 graden oosterlengte. Die heeft drie rechte hoeken en dus een exces van 90 graden. De oppervlakte is pi/2.

Oplossing voor 12 piraten:

Het is 'bijna vanzelfsprekend' dat het regelmatig twintigvlak (de icosaëder) voor twaalf piraten de optimale configuratie geeft. Omdat het regelmatig twintigvlak uit gelijkzijdige driehoeken bestaat. Hierbij is van belang dat de afstand tussen twee punten binnen een gelijkzijdige driehoek hoogstens gelijk is aan de lengte van de zijde. Dat geldt niet voor een regelmatige vijfhoek. Het regelmatig twaalfvlak (de dodecaëder) geeft voor twintig piraten niet de optimale configuratie, omdat het uit regelmatige vijfhoeken bestaat. Het kan door flippen en schuiven verbeterd worden.

Mijn commentaar:

Het is nu duidelijk hoe jullie aan de optimale configuratie voor tien piraten zijn gekomen.
Ik heb dit met een Pascalprogramma nagedaan.
Eerst heb ik een goede configuratie gezocht met een punt in de noordpool, vijf in een horizontaal vlak in een regelmatige vijfhoek, en vier in een horizontaal vlak in een vierkant, het vierkant 9 graden gedraaid ten opzichte van de vijfhoek.
Vervolgens heb ik telkens twee punten op minimale afstand van elkaar gezocht, en die twee punten over de bol gemeten 0.0001 verder uit elkaar gezet.
Zo vond ik een configuratie met een minimumafstand van ruimtelijk bijna 1.0912 megameter en over de bol iets meer dan 1.154 megameter.

Ook het bewijs dat dit bijna optimaal is heb ik in het klein nagedaan. Heeft men zestien gelijkzijdige driehoeken die de bol overdekken, dan moet elk van die driehoeken oppervlakte pi/4 hebben. Volgens de bolmeetkunde zijn dan de hoeken 75 graden, en is de zijde ongeveer 1.214 megameter. Omdat deze ideale situatie niet bereikt wordt, is de maximale minimumafstand in feite nog wat kleiner.


Verdeling der prijzen:

Ik heb de mededingers die zich niet uitdrukkelijk als amateur hebben aangemeld, dan ook niet in de categorie amateurs ingedeeld.
Dat betekent dat Martien Luijcks als enige serieuze deelnemer in de categorie amateurs meteen ook de hoofdprijs bij de amateurs in de wacht sleept.
Professor Danzer heeft natuurlijk de allerbeste configuraties, maar hij behoort duidelijk tot een categorie apart. Hij krijgt van ons een aparte prijs.
Dan blijven er twee mededingers over in de categorie professionals. Van die twee vond ik Harrie Schreuders de beste (zie het bovenstaand commentaar bij zijn inzending). Hij krijgt dus de hoofdprijs bij de professionals.
De heer Peter Janssen krijgt een aanmoedigingsprijs.



NASCHRIFT


Na het uitreiken van de prijzen heb ik nog een beetje verder gestudeerd in het boekje van Danzer.
Zie eerst hierboven, mijn commentaar bij Danzer.
Danzer bewijst dat in de optimale configuratie met minimumafstand d bij elk punt P drie, vier, vijf of nul andere punten op afstand d liggen. Indien dat aantal nul is, noemt hij P geïsoleerd. Tussen elk tweetal niet-geïsoleerde punten is er een pad dat via louter niet-geïsoleerde punten loopt. Een regelmatige vijfhoek met zijde d omsluit precies dan een geïsoleerd punt als de hoek groter is dan 72 graden.

Verder kwamen na zoeken in zijn literatuuropgave de volgende gedachten bij mij op, die nogal afwijken van die van Danzer.
Voor twaalf piraten is elke hoek tussen twee geodeten in de configuratie 72 graden.
Voor tien piraten ligt dat veel ingewikkelder.
Dat er zestien driehoeken zijn, bewijst men als volgt. Stel dat er n driehoeken zijn. De som der oppervlakten van de driehoeken is 4*pi, dus de som van de hoekexcessen is 4*pi. Dus de som van alle voorkomende hoeken is (n+4)*pi. Maar de som van alle voorkomende hoeken is ook 10 keer 2*pi, dus 20*pi. Dus n=16.
Er zijn drie belangrijke hoofdgroepen van configuraties, ongeveer zoals Harrie Schreuders dat heeft aangegeven. Men kan ze kort aanduiden als 1-5-4, 1-3-3-3 en 1-4-4-1. De optimale zit in de groep 1-5-4.
In elke hoekpunt is de som der hoeken 2*pi. Dit geeft (in elke hoofdgroep) tien lineaire vergelijkingen met 16*3=48 onbekenden.
Voor elke driehoek zijn er drie vergelijkingen die het verband geven tussen de hoeken en de zijden. Dat zijn nog eens 48 (niet-lineaire) vergelijkingen met 72 onbekenden. (72 = 48 + 48/2)
Deze laatste vergelijkingen hebben de vorm cos(a) = cos(b)*cos(c) + sin(b)*sin(c)*cos(A), waarbij A de hoek tegenover zijde a is.
Het probleem kan dus beschreven worden als het maximaliseren van de minimale lengte van een zijde onder de nevenvoorwaarde dat aan deze 58 vergelijkingen met 72 onbekenden voldaan is.
Ik heb hier nog met professor Danzer over gecorrespondeerd. Hij merkt op dat de tangens van de minimale lengte in de optimale configuratie nulpunt is van een veelterm met gehele coëfficiënten. Deze veelterm heeft echter een nogal hoge graad. Men kan de lengte ook numeriek benaderen.
Voor nadere inlichtingen: mail reuversmtr@home.nl (thuis) of H.Reuvers@fontys.nl (werk).

Tot slot een leuke kleine opgave voor iedereen. Beschouw een gelijkzijdige driehoek in het platte vlak. Vind vier punten binnen die driehoek of op de zijden van de driehoek, zo dat de kleinste van de zes afstanden tussen twee van die punten maximaal is.
Hint: sommige vierhoeken zijn convex, andere niet.


Hennie Reuvers, Maastricht 2 februari 2004.



klik hier voor mijn hoofdpagina.