WisFaq!

Polyhedra en mieren

Een vriend heeft me de volgende vraag voorgelegd maar vindt hemzelf vrij complex.

Als er op elke vertex van een dodecahedron zich een mier bevindt die zich simultaan naar de volgende vertex doen bewegen, zijn pad willekeurig kiezend. Wat is dan de kans dat geen twee mieren zich kruisen, en route of op de nieuwe vertex?

Ikzelf weet wel de oplossing bij een driehoek, namelijk: 2/8, omdat de enige 2 mogelijkheden waarin zich geen botsing voordoet, is wanneer alle mieren links, dan wel rechts gaan; bij de andere 6 mogelijkheden-rrl,rlr,rll,llr,lrl en lrr doet zich die wel voor. Maar ik kan dit niet generaliseren naar andere polyhedra of eventueel in de 4de dimensie, enige handreikingen?

Bij voorbaat dank,

Dirk Broeder
18-1-2004

Antwoord

Mieren op Veelvlak. Een mooi probleem.

Op ieder hoekpunt van het veelvlak zit een mier. Op een gegeven moment lopen ze allemaal via een ribbe naar een naburig hoekpunt. Ieder kies onafhankelijk van de anderen een van de ribben die uit zijn hoekpunt vertrekken met gelijke kansen.

Wat is de kans dat:

1. Er geen botsingen optreden, dwz op geen enkele ribbe komen twee mieren elkaar tegen en
2. Dat alle mieren op verschillende hoekpunten terecht komen.

Antwoord: Dit is dus een soort boompje verwisselen, waarbij het verboden is dat er paarsgewijs geruild wordt (wegens a)) Dit betekent dat er alleen in kringen van minstens 3 opgeschoven wordt.

Voorbeeld 1: Kubus.
Eerste mogelijkheid: 2 kringen van 4
Bijvoorbeeld één kring in het bovenvlak en één onder. Of één links en één rechts. Of voor en achter.
Ieder van die 2 kringen kan linksom of rechtsom doorlopen worden Dat geeft 3 keer 2 keer 2 = 12 verhuisplannen, routes.

Tweede mogelijkheid: Een kring van 8
Deze kan op 6 manieren geplaatst worden en dan in twee richtingen doorlopen. Dus 12 mogelijke routes.
In totaal dus 24 routes. Is de route bekend dan moeten alle mieren de juiste keuze doen: kans dat gebeurt: (¹/₃)⁸
Resultaat: Voor de kubus is de gevraagde kans 24/3⁸ = tamelijk klein.

Nu maar meteen maar de dodecaëder.
20 mieren, 30 ribben. Maak een model. Het netwerk van de 20 hoekpunten en 30 ribben ziet er zo uit:


(Dit zou je zien als je een draadmodel dat op tafel ligt van boven bekijkt van uit een punt vlak boven het midden van het bovenvlak. Het bovenvlak is dan de grote vijfhoek)

Er zijn 2 mogelijkheden:

Twee kringen van 5 en een kring van 10. De kringen van 5 liggen in twee overstaande zijvlakken, 6 mogelijkheden. De omlooprichtingen kunnen op 8 manieren gekozen worden. Er zijn dus 48 routes van dit type.

De tweede mogelijkheid is een kring van 20. In 1857 beschreef W.R.Hamilton zo’n kring. Daarom noemt men het wel een “Hamiltonpad”( In het algemeen is dat een gesloten pad in een netwerk waarbij ieder knooppunt precies 1 keer bezocht wordt.) Het blijkt dat bij de dodecaëder zo’n pad het oppervlak in twee gelijke delen verdeelt, die als je ze uitknipt en plat legt er zo uitzien:



Ieder van die delen bestaat uit 6 vijfhoeken (en het pad loopt daar omheen).Er zijn 15 mogelijke plaatsingen van het pad op de dodecaëder en nog 15 voor degespiegelde,dus 30 mogelijkheden. Met omlooprichting 60 routes. Dus in totaal 108 (48+60). Dat er geen andere kringen mogelijk zijn is nog even puzzelen, maar daar kom je wel uit. De gevraagde kans wordt dus 108/3²⁰, heel erg klein dus.

Hoe het bij andere veelvlakken is, is ook nog een leuke opgave. Veel plezier ermee.

JCS
21-1-2004