#WiskundePlantyn

Wiskunde in de Simpsons (5): over grafen en puzzels

De Simpsons is niet alleen ’s werelds meest iconische animatieserie, maar barst ook van wiskundige finessen. Tot de schrijvers behoren Stewart Burns (master in wiskunde), David X Cohen (master in informatica), Ken Keeler (PhD in toegepaste wiskunde) en Jeff Westbrook (PhD ininformatica), allen wiskundegeeks die het niet kunnen laten de Simpsons vol te proppen met al dan niet verborgen wiskundige concepten, grappen en puzzels. Elke maand lichten we in deze column zo’n wiskundig onderwerp nader toe vanuit de Simpsons.

De rivierpuzzel

In Gone Maggie Gone (seizoen 20, aflevering 13) moet Homer een beroemde puzzel oplossen. Hij heeft baby Maggie bij, zijn hond Santa’s Little Helper en een bokaal met rattenvergif in dat op snoepjes lijkt. Zijn tocht wordt belemmerd door een rivier, die enkel met een lichte boot kan worden overgestoken. De boot is echter zo licht dat Homer slechts één item per overtocht kan meenemen. Hij kan natuurlijk Maggie niet met het vergif of bij de hond achterlaten, want dan bestaat natuurlijk het risico dat ze de bokaal opent en vergif inneemt, of door de hond wordt gebeten. Kan Homer veilig oversteken?

Oplossing via grafen

Deze puzzel is allicht zo bekend dat de oplossing al gekend is, en dan nog is ze helemaal niet moeilijk. De klassieke variant vertelt het verhaal van een boer die wil oversteken met een wolf, een schaap en een kool, maar de versie uit the Simpsons is equivalent. Zelfs Homer vindt zonder veel moeite de oplossing: eerst Maggie overbrengen, dan alleen terugkeren en met de hond oversteken, Maggie opnieuw meenemen en met de bokaal oversteken, om ten slotte nog eenmaal alleen terug te keren om Maggie op te halen.

Een mooie werkwijze om het probleem op te lossen werkt via grafen. Je kan de mogelijke configuraties van de puzzel voorstellen door tripels (a,b,c) waarbij a, b en c de waarden nul of één kunnen aannemen. Nul betekent nog op de oever, één betekent al aan de overkant, en we laten a de positie van de hond voorstellen, b de positie van Maggie en c de positie van de bokaal. In totaal zijn er acht (23) configuraties mogelijk, die coördinaten in de ruimte voorstellen. Wanneer we configuraties verbinden die slechts één item verschillen, verkrijgen we een kubus! Nu kunnen we de zijden die een verboden overgang voorstellen, schrappen (dit zijn er vier), waarna we de legitieme oplossingen eenvoudig kunnen aflezen als de paden van begin- naar eindconfiguratie langsheen de niet-geschrapte zijden van de kubus.

Deze soort puzzels kan dus worden opgelost door alle mogelijke posities op te stellen en de mogelijke overgangen te vertalen naar verbindingen tussen deze posities, wat een graaf oplevert. In de klassieke versie ziet de graaf er zo uit:



Grafen zijn van een immens belang in de discrete wiskunde en de informatica. Er bestaan letterlijk honderden vraagstukken omtrent grafen. Zo onderzoekt men kleuringen op grafen, labelingen, tellingen, paden, stromingen, ontbindingen, maximale deelgrafen van een bepaald type ...

Enkele andere puzzels

Deze grafentactiek kan ook worden toegepast op soortgelijke puzzels, maar met meer items wordt de graaf natuurlijk groter en de methode vervelender. Toch enkele puzzels om over na te denken:

  • Een man, een vrouw en twee kinderen willen een rivier oversteken. Hoe geraken ze allen aan de overkant als ze enkel een bootje ter beschikking hebben dat hoogstens of één volwassene, of twee kinderen kan dragen?
  • Drie getrouwde koppels willen een rivier oversteken. De mannen zijn zeer jaloers en laten niet toe dat hun vrouw achterblijft bij een andere man als zij er zelf niet bij zijn. Het bootje kan deze keer hoogstens twee personen dragen.
  • Vier personen willen ’s nachts een smalle brug oversteken. De sportiefste kan naar de overkant lopen in één minuut, de volgende in twee minuten, de derde in vijf minuten en de laatste doet er acht minuten over. Er is één zaklamp ter beschikking, hoogstens twee personen kunnen tegelijk oversteken en het tempo wordt bepaald door de traagste. Ieder die overloopt (alleen of per twee) moet de zaklamp bij hebben. Hoe geraken ze allen aan de overkant binnen het kwartier?
     
Deel dit artikel

Reageer op dit artikel
(bekijk de commentaren)