gietproblemen

© h.hofstede (h.hofstede@hogeland.nl)

Gietproblemen.

Het probleem lijkt eenvoudig:

Je hebt een fles van 7 liter en een fles van 11 liter.
Naast je staat een grote bak water.
Met deze twee flessen moet je precies twee liter water afmeten.
Je kunt de flessen alleen maar helemaal leeggieten of helemaal vullen.
Gedeeltelijk kan niet want er zit geen schaalverdeling op.
Hoe doe je dat?

Als knooppunten (toestanden) van de graaf die dit beschrijft zou je kunnen nemen het aantal liters in fles 1 en in fles 2.
Dat geeft zo'n rooster van 12 bij 8:

WAUW! Een graaf met 96 knooppunten!!
Punt A staat bijvoorbeeld voor de situatie met 5 liter in de grootste fles en 2 liter in de kleinste. En bij B is de grootste fles vol, en zit er 5 liter in de kleinste.

Hoe is het met de verbindingslijnen van deze graaf?

Vanuit een bepaalde toestand (knooppunt) kun je steeds 4 dingen doen:
1. De kleinste fles leeggooien of helemaal vullen
2. De grootste fles leeggooien of helemaal vullen
3. De kleinste fles in de grootste gieten.
4. De grootste fles in de kleinste gieten.

Laten we kijken wat dat in onze graaf betekent...

1 en 2 zijn simpel: maak de grootste fles leeg (en laat de kleinste gelijk) door helemaal naar rechts te gaan of vol door helemaal naar links te gaan (blauwe verbindingslijnen). Maak de kleinste leeg door helemaal omlaag te gaan of vol door helemaal omhoog te gaan (rode verbindingslijnen).

Als je de kleinste in de grootste giet, dan betekent dat, de grootste fles evenveel toeneemt als de kleinste afneemt. Dat is een verbindingslijn schuin naar rechts omlaag en die moet doorlopen totdat de kleinste leeg is of de grootste vol. Het zijn de paarse lijnen in de figuur hierboven.
De grootste in de kleinste gieten betekent op deze manier de groene verbindingslijnen.

Omdat alle verbindingslijnen steeds helemaal tot de zijrand moeten doorlopen zijn alleen de knooppunten aan die rand bereikbaar!!! De anderen kunnen we dus net zo goed weglaten.
Dat geeft de volgende graaf:

(Bedenk dat die verbindingslijnen aan de randen helmaal van het ene naar het andere einde lopen)
Het oorspronkelijke probleem is nu geworden: kun je van knooppunt (0,0) in dit rooster via de verbindingswegen een route maken naar (2, 0) of naar (0, 2)?

Die route is vrij eenvoudig te vinden (als je je maar bedenkt dat het niet handig is om naar een knooppunt te gaan waar je al geweest bent). Hierboven zie je een snelste route (er is ook eentje te vinden door vanaf (0,0) te beginnen omhoog te gaan).
De hier getekende route komt overeen met de volgende 17-staps oplossing voor het oorspronkelijke gietprobleem:

Wat zijn we eigenlijk aan het doen?

In deze oplossing vul je steeds de 11-liter fles (verbindingslijn naar rechts), en leegt hem in de 7-liter fles (alle schuine gevolgde verbindingslijnen in de graaf gingen van rechtsonder naar linksboven).
Elke keer als de 7-liter fles vol is leeg je hem weer (verbindingslijn van boven naar beneden).
Dat komt eigenlijk neer op het zoeken naar oplossingen van de vergelijking 7x + 11y = 2

Een oplossing is bijvoorbeeld x = -6 en y = 4 en dat vertalen we naar "Vul de 11-liter fles 4 keer en leeg hem steeds in de 7-liter fles. Gooi de 7-liter fles 6 keer leeg (steeds als hij helemaal vol is)"

Algemene andere oplossingen zijn: x = -6 + 11k en y = 4 - 7k
Voor k = 1 vinden we x = 5 en y = -3 en dat betekent "Vul de 7-liter fles 5 keer en leeg hem steeds in de 11-liter fles. Gooi de 11-liter fles 3 keer leeg (steeds als hij helemaal vol is)"

Dat is de oplossing die je vindt als je vanaf (0,0) begint omhoog te gaan (de 7-liter fles eerst vullen)

Laten we het moeilijker maken....

Stel nou dat we geen oneindig reservoir hebben, maar in plaats daarvan een derde fles
Die derde fles is de grootste van de drie en is in het begin helemaal gevuld.
Neem bijvoorbeeld het volgende raadsel:

Je hebt drie flessen van 8, 5 en 3 liter waarvan die van 8 gevuld is.
Kun je daarmee twee porties van 4 liter maken?

We gaan de "toestanden" weergeven door knooppunten in een graaf die aangeven hoeveel water er in de kleinste twee flessen zit (dan ligt de derde fles vast, want de totale hoeveelheid water blijft 8 liter). De derde fles doet dienst als reservoir.

Dat geeft de oplossing hiernaast

De vraag is alleen of het allemaal steeds klopt wat betreft de 8-literfles.

In de graaf hiernaast heb ik bij alle knooppunten de inhoud van de 8-literfles geschreven (blauw). Als je dat doet dan zie je meteen dat knooppunten met dezelfde inhoud op één lijn liggen.

De schuine blauwe lijn geeft de inhoud van de 8-literfles aan.
Je moet er dus voor zorgen dat je alleen knooppunten neemt waarvoor bij de blauwe lijn een getal tussen 0 en 8 hoort.

Dat klopt nu overal, maar het kan invloed hebben als de grootste fles kleiner is dan de andere twee samen.

Hieronder zie je een voorbeeld met flessen van 10, 7 en 5 liter.

De drie rode knooppunten vallen buiten het bereikbare gebied van de 10-literfles (er zou een negatieve hoeveelheid water in de 10-literfles moeten zitten) Die vallen dus af, en daardoor wordt punt P een nieuw toelaatbaar knooppunt op de rand. Je kunt nu bijvoorbeeld als er respectievelijk 6 - 0 - 4 liter in de flessen zit, de tweede fles vullen tot slechts 6 liter (door de eerste fles erin leeg te gieten).

Wat kan er mis gaan?

Je kunt niet altijd alle hoeveelheden water produceren.
Het kan mislopen als de route die je in de graaf volgt een cykel wordt, zonder alle knooppunten te hebben gehad.
Dat is zo als het aantal liters dat in de kleinste twee flessen past een gemeenschappelijke deler heeft.

Neem bijvoorbeeld flessen van 10 - 6 - 4 liter, dan krijg je dit:

Een cykel!
De aantallen 1, 3 en 5 liter kunnen niet gefabriceerd worden.

OPGAVEN


1.	Een heks moet een toverdrank maken die precies 30 minuten moet koken. Ze heeft echter alleen de beschikking over twee zandlopers: één van 9 minuten en één van 13 minuten. Hoe kan zij 30 minuten afmeten als zij pas mag beginnen als de drank kookt?

2.	Je hebt een 7-minuten en een 11-minuten zandloper en moet voor een ontbijt een ei precies 15 minuten koken. Hoe pak je dat aan?