Naar de content

De beste manier om 50.000 vormen in te pakken

bighornplateau1, Flickr

Hoe pak je de meeste sinaasappels in een fruikist? En watermeloenen? Dankzij het werk van wiskundigen van de Amerikaanse Michigan University en Harvard weten we nu van 50.000 vormen hoe je ze het beste kan verpakken.

Al deze sinaasappels wil je in zo min mogelijk dozen naar de supermarkt brengen. Wiskundigen houden zich al eeuwen bezig met dit sinaasappelprobleem, maar hebben het in 2005 opgelost.

bighornplateau1, Flickr

Het inpakken van dingen is niet makkelijk. Alles zomaar in een doos gooien is zelden efficiënt. In een ideale wereld zou alles dat een verpakking nodig had vierkant zijn, maar ook dat lijkt niet erg realistisch. Dus moet je door slim te rekenen manieren vinden om iets goed in te pakken. Daarbij komen veel keuzes kijken. Bijvoorbeeld: als je bollen in een vierkant pakt, begin je dan met inpakken aan de rand van de doos? Of leg je eerst een piramidevormig bodempje om daarop te bouwen?

Exotische figuren

Bollen zijn een relatief eenvoudige vorm, omdat ze aan alle kanten hetzelfde zijn. De Amerikaanse onderzoekers gingen verder: voor hen geen bollen, maar allerlei andere exotische vormen, zoals de icosaëder, octaëder en alle figuren die ‘familie’ zijn van deze vormen. Die families zijn behoorlijk groot; in totaal behelsde het onderzoek meer dan 50.000 verschillende figuren. Nog indrukwekkenderis dat ze van al deze vormen voorlopig de beste verpakkingsmanier vonden.

Dat betekent echter niet dat ze voor al die vormen een perfecte methode hebben gevonden. Sterker nog, van alle 50.000 is de manier aantoonbaar niet perfect. Een perfecte inpakmanier, waarbij je wiskundig kan bewijzen dat er geen methode bestaat die nog efficiënter is, is ontzettend moeilijk te berekenen. Voor de bol vermoedde de beroemde astronoom Johannes Kepler vierhonderd jaar terug al een perfecte methode. Pas in 2005 bewees iemand dat Keplers manier inderdaad de optimale inpakmanier is.

Enorme puzzel

De bol is, naast de ‘makkelijke’ vormen zoals kubussen, de enige 3D-figuur waarvoor het probleem wiskundig geen mysteries meer heeft. Voor alle andere figuren ligt er nog een enorme puzzel klaar. Dat is ook één van de redenen dat verpakkingsproblemen zoveel aandacht krijgen van wiskundigen: het probleem is simpel uit te leggen, maar moeilijk op te lossen. Bovendien heeft een perfecte inpakmethode iets magisch, in ieder geval voor de zeventiende-eeuwse wiskundigen: die deden het in het bijzonder voor de esthetische waarde van een perfect volgepakte doos.

Maar tegenwoordig zijn er ook steeds meer praktische toepassingen. Bedrijven zouden bijvoorbeeld geld kunnen besparen als ze hun goederen efficiënter kunnen inpakken, omdat ze dan minder opslagruimte nodig hebben en een vrachtwagen voller kunnen laden.

Inpakproblemen komen ook in de natuur regelmatig voor. Dit koraal, bijvoorbeeld, geeft (waarschijnlijk zonder het te weten) een benadering van een bekend probleem: hoe krijg je een bol vol met zo veel mogelijk cirkeltjes? De benadering is verrassend goed; blijkbaar voldoet de natuur ook aan de regels van efficiëntie.

Wikimedia Commons

Inpakrecord

Mede door die toepassingen dachten de Amerikaanse onderzoekers dat het wel eens nuttig kon zijn om met computerprogramma’s en schattingen een zo goed mogelijke inpakmethode te vinden. Dat algoritme was goed genoeg om met veel verschillende vormen te kunnen rekenen en gaf voor al die vormen een ‘record’: de inpakmethoden waren ruimtezuiniger dan de voorheen bekende manieren. Naarmate de computers krachtiger worden, worden de inpakmethoden steeds nauwkeuriger te berekenen.

Daarmee zouden de mensen die op zoek zijn naar de perfecte vulmanieren ook een hint kunnen krijgen; zoals Kepler al een vermoeden had van de ideale manier op bollen in te pakken, zo geeft de computer een aanwijzing in welke hoek je moet zoeken om een icosaëder of ander vreemd veelvlak perfect in te pakken.

Zo ver is het echter nog lang niet. Of het, net als met de bol, 400 jaar gaat duren om een bewijs te vinden voor andere vormen, zal alleen de tijd leren.

Bron

Elizabeth R. Chen e.a, Complexity in Surfaces of Densest Packings for Families of Polyhedra, Physical Review X, 25 februari 2014, doi:10.1103/PhysRevX.4.011024