speelgoedzakprobleem (voor de Sint en de Kerstman)

Het zijn weer hoogdagen voor deze weldoeners. Vannacht hebben de Sint en zijn pieten de daken van de lage landen bewandeld, en binnen enkele weken is het de beurt aan de kerstman om alle schoorstenen te bezoeken. Soms moeten ze natuurlijk even hun grote zak met speelgoed bijvullen. Daarom moeten ze dikwijls af en op de daken klimmen, heen en weer naar hun stoomboot of slede,… Tijd en energie rovend dus. Misschien eens een goede moment om te kijken hoe deze kindervrienden wiskunde in hun voordeel kunnen gebruiken…
Image
Het speelgoedzakprobleem is eigenlijk een breder bekend probleem dat normaal door het leven gaat als “het knapzak-probleem”. Het probleem is zoals vaak met moeilijke wiskundige problemen, heel gemakkelijk te definiëren:
Je hebt een grote (knap)zak die een bepaald gewicht kan dragen, en een verzameling goederen met bepaald gewicht en een toegekende waarde. Welke goederen steek ik in de zak zodat hij de meeste waarde bezit (zonder dat je het maximum gewicht van de (knap)zak overschrijdt).
Meestal wordt er een voorbeeld gegeven met een dief die juwelen wil stelen, … maar laten we het gezien de tijd van het jaar, even bekijken met de Sint die zijn speelgoedzak vult.

ImageStel dat de Sint een zak heeft waar hij (of zijn paard) 20 kg mee kan sleuren. Het speelgoed waartussen hij kan kiezen is een spelbord, een voetbaltafel, een pop, een spelconsole, een puzzel, en een breinbreker…(gewichten en prijzen kunnen afwijken… het is slechts een voorbeeld). Hij kan alvast de hele dure voetbaltafel van 250€ meenemen, zo heeft hij meteen het voorwerp met de meeste waarde én hij heeft het maximum gewicht niet overschreden. Maar hij kon natuurlijk ook voor 2 spelconsoles kiezen… zo heeft hij voor een gewicht van 20 kg, een waarde van 400€ mee de daken op. 
Als je de definitie van het knapzak probleem iets strenger maakt kan je kijken naar het 0-1-knapzak probleem. Het enige verschil met het originele is dat voorwerpen niet 2 maal mogen voorkomen in de zak. De Sint kan dus weer stellen dat zijn originele idee met de voetbaltafel de betere keuze is. Maar nog steeds zou hij mis zijn, want hij kan ook de combinatie: 1 spelbord + 1 breinbreker + 1 spelconsole + 1 puzzel kiezen! Zo heeft hij een waarde van 256€ bij elkaar gesprokkeld, en dat voor slechts 19 kg!
Image
Natuurlijk hebben de pieten en hulp-elven van de weldoeners gezorgd voor een veel ruimere keuze aan speelgoed… Voor slechts 6 speeltjes zoals hierboven is het probleem snel op te lossen, maar het wordt wederom snel moeilijker tot zelfs nagenoeg onoplosbaar, als je keuze groter wordt. Het feit dat dit zo moeilijk wordt is zelfs de aanleiding geweest om de wiskunde achter dit probleem te gebruiken als codeersysteem. Aangezien de wiskunde hierachter moeilijk is, komt dit namelijk overeen met een moeilijk te breken code. 

Er zijn wel enkele manieren waarop je het probleem kan benaderen, je kan eerst de goederen rangschikken op
1. gewicht (van klein naar groot)
2. waarde (van groot naar klein)
3. op verhouding waarde/gewicht (van groot naar klein).

Oplossingsmethode 1 zal je zak zoveel mogelijk vullen met alle kleine spullen. Dit heeft als effect dat je heel veel zult kunnen meenemen. Hoe meer spullen hoe meer waarde zou je denken, dus waarom zou dit niet de beste techniek zijn? Wel doorgaans zijn kleinere dingen ook minder waard dan grotere… bijvoorbeeld 20 breinbrekers van 1 kg (kleinste gewicht) wegen evenveel als de voetbaltafel, maar 20 x 6€ = 120€ wat nog steeds een pak minder is dan de voetbaltafel van 250€.
Oplossingsmethode 2 is diegene die de Sint eerst toepaste wanneer hij enkel de voetbaltafel meenam. We zagen eerder al dat dit in bovenstaande voorbeeld niet de beste methode was.
Oplossingsmethode 3 is in ons geval de beste. Je neemt steeds het voorwerp met de beste verhouding en stopt het in je zak, daarna zoek je 2de beste verhouding, … enzovoort, zolang je het maximum gewicht niet overschrijdt. Voor ons zijn de verhoudingen in €/kg: spelbord 6, voetbaltafel 12,5, pop 3, spelconsole 20, puzzel 6.66 en breinbreker 6. We nemen eerst de spelconsole met verhouding 20, dan de puzzel met verhouding 6.66 (niet de voetbaltafel met verhouding 6.66 want dan overschrijden we ons gewicht), dan het spelbord, en dan de breinbreker.
Zoals je kan zien heb ik in bovenstaande methodes enkele woorden in het vet getypt. Deze moeten erop nadrukken dat elke oplossingsmethode de beste kan zijn… het hangt gewoon van geval tot geval af. Zelfs voor oplossingsmethode 3 bestaan er situaties waarin deze niet de beste is! Bijvoorbeeld in het geval je slechts 6 kg kan meenemen en je hebt de keuze tussen een spelbord en 2 poppen… de derde oplossingsmethode zal je de verkeerde keuze laten maken.
Image
Moraal van het verhaal is dat voor kleine aantallen speeltjes en pleziertjes de goede mannen door eens diep na te denken, te tellen en te rekenen, de juiste keuze kunnen maken. Voor grotere aantallen heeft zelfs de wiskunde nog niet de juiste antwoorden… Sommige kinderen hechten natuurlijk ook andere waarden aan speelgoed. niet zozeer de prijs maar het plezier is voor hen meer waard. Maar de oude wijze mannen zullen hier met hun jarenlange ervaring wel een antwoord op hebben denk ik…

Daarom de Sint, de Pieten en de Kerstman

Giedts Tom

 

 

Advertisements

Leave a comment

Filed under andere

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s