Rivieroversteekpuzzel

Rivieroversteekpuzzels zijn een soort logische puzzels waarbij een groep beschreven leden in zo weinig mogelijk overtochten een rivier moet oversteken.

Wolf, geit en kool

Bij het oversteken kan de boot niet de hele groep in één keer vervoeren, doordat bepaalde combinaties van groepsleden elkaar uitsluiten. De oudste schriftelijke vermelding van dit soort problemen is te vinden in het late 9e eeuwse Propositiones ad acuendos iuvenes, die vier van dergelijke problemen bevat. De bekendste daarvan is het probleem van de wolf, de geit en de kool.

Wolf, geit en kool bewerken

Een boer is op weg naar de markt met een wolf, een geit en een kool bij zich. Gelukkig voor de boer ligt er een boot, want hij kan niet zwemmen. De boot kan naast hem echter maar één andere passagier bevatten. De boer kan de geit niet alleen met de wolf laten (dan eet de wolf de geit op) maar ook de kool kan niet alleen met de geit gelaten worden (dan eet de geit de kool op). De opgave is om een plan te bedenken dat aan deze voorwaarden voldoet en in zo min mogelijk oversteken lukt.

Om het probleem op te lossen, moet de man eerst de rivier oversteken met de geit, hem op de andere oever achterlaten en alleen terugkeren. Vervolgens brengt hij de wolf naar de overkant, laat hem daar en keert terug met de geit. Hij laat dit achter op de uitgangsoever, steekt over met de kool en keert alleen terug. Ten slotte brengt hij de geit voor de tweede keer naar de bedoelde oever, wat het probleem oplost. Een alternatieve oplossing is om wolf en kool in bovenstaande volgorde om te wisselen.

Het raadsel komt in veel culturen voor, waarbij de passagiers zich aanpassen aan de plaatselijke omstandigheden. Het probleem komt dus ook voor bij 'vos, kip en granen'. De puzzel is ook wijdverbreid in Afrika, bijvoorbeeld 'cheeta, kip en rijst'. In de Aarne-Thompson-Uther Index staan onder ATU 1579 verhalen met dit thema vermeld, maar ook in moderne entertainmentmedia wordt wel verwezen naar deze puzzel.

De jaloerse echtgenoten bewerken

Het probleem van jaloerse echtgenoten is ook bekend uit de Propositiones: Drie echtparen (in de Propositiones zijn ze broers en zussen) willen een rivier oversteken, maar de boot kan maar twee mensen bevatten. De echtgenoten zijn jaloers op elkaar, dus geen van beiden zal toestaan dat zijn vrouw op een oever of in een boot zit met een andere man als hij er niet zelf bij is.

Een eenvoudigere variant van dit raadsel wordt verkregen als de toestand een beetje wordt afgezwakt: de vrouwen mogen natuurlijk nooit in de meerderheid zijn (tenzij er helemaal geen mannen bij zijn), want anders is een van hen met een vreemde man zonder dat haar eigen man erbij is. In deze versie wordt de taak het probleem van de missionarissen en kannibalen. Het achtergrondverhaal wordt daarbij anders geformuleerd: Drie missionarissen en drie kannibalen willen een rivier oversteken, maar de boot biedt slechts plaats aan twee personen. Om niet bang te zijn om opgegeten te worden, mogen de missionarissen nooit in de minderheid zijn van de kannibalen.

De brug bewerken

Een variatie op het probleemtype is te vinden in Saul X. Levmore's en Elizabeth Early Cook's bridge crossing problem: vier mensen, gelabeld A, B, C en D, willen 's nachts een brug oversteken, maar ze hebben slechts een lantaarn bij zich. Zonder de lantaarn is het onmogelijk om de brug in het donker over te steken, maar de gloed ervan is slechts voldoende om met twee mensen om de brug tegelijk over te steken. A heeft 5 minuten nodig om over te steken, B 10 minuten, C 20 minuten en D 25 minuten. Omdat de lantaarn niet lang meer zal branden, moeten ze een manier vinden om zo snel mogelijk de brug over te steken.

Hier neemt de lantaarn de rol van de boot over, in plaats van het aantal overtochten te verminderen, moet de duur ervan worden geminimaliseerd. In de naïeve oplossing brengt A achtereenvolgens de andere drie naar de andere kant en keert hij zelf twee keer terug naar het startpunt. Dit duurt 10 + 5 + 20 + 5 + 25 = 65 minuten. Er is echter een snellere oplossing: A en B steken de brug over, A komt terug met de lantaarn. Dan gaan C en D, de twee langzaamste, samen over, de lantaarn brengt B terug voordat hij de brug weer oversteekt met A. Dit plan duurt slechts 10 + 5 + 25 + 10 + 10 = 60 minuten.

Varianten bewerken

Naast deze bekende voorbeelden zijn er nog veel meer rivieroversteekpuzzels. Zo is het probleem van jaloerse echtgenoten ook gesteld voor een groter aantal paren, met de toevoeging van een eiland in het midden van de rivier. Een systematische studie met een volledige oplossing voor dit probleem is van Ian Pressman en David Singmaster .

Een kleine verzameling van verschillende rivieroversteekpuzzels is ook te vinden in het puzzelboek Amusements in Mathematics van Ernest Dudeney.