Kannibalen en
Missionarissen |
|
Laten we de mogelijke toestanden eerst eens schematisch
weergeven. We bekijken de toestanden waarin de boot niet op het water
is. Dat kan bijvoorbeeld als volgt in een 4x4 rooster: |
|
|
Op de horizontale as staat het aantal missionarissen op de
zuidoever, op de verticale as het aantal kannibalen op de zuidoever. Het
rode vakje komt overeen met 3 missionarissen en 2 kannibalen op de
zuidoever (en dus 0 missionarissen en 1 kannibaal op de noordoever).
Vervolgens maken we alle toestanden die niet toegestaan zijn (waarbij er
missionarissen worden gegeten) zwart: De startpositie (S)
en de finishpositie (F) kleuren we
rood. |
|
|
Het is nu de opgave geworden om van S naar F te gaan via
alleen maar witte vakjes (= toegestane toestanden).
Wat gebeurt er als we met de boot varen? Welke overgangen zijn mogelijk?
Stel dat we van zuid naar noord varen. Dan zijn er voor de boot 5
mogelijkheden die elk een overgang in ons rooster weergeven:
- er zit één missionaris in de boot: één vakje naar links.
- er zitten twee missionarissen in de boot: twee vakjes naar links
- er zitten een missionaris en een kannibaal in de boot: schuin naar
links en naar beneden
- er zitten twee kannibalen in de boot: twee vakjes omlaag
- er zit één kannibaal in de boot: één vakje omlaag.
Voor het van noord naar zuid varen kunnen we een zelfde redenering
houden. De mogelijke overgangen staan samengevat in de figuur hieronder. |
|
|
|
De opgave is geworden: ga in de linkerfiguur over de open
vakjes van S naar F. Doe dat door om en om een blauwe en een groene pijl
te gebruiken.
Een mogelijke oplossing staat hieronder: |
|
|
|
Zoals je ziet vereist deze oplossing dat de boot 11 keer
vaart (11 pijlen). Er blijken nog drie andere oplossingen te zijn met 11
keer varen. Zoek die zelf maar op. Sneller dan in elf keer kan niet.
Een stripverhaal van bovenstaande oplossing zou er zo uitzien: |
|
|
|
4 missionarissen en 4 kannibalen overvaren blijkt niet te
kunnen!
Het wil wel als er drie personen in de boot kunnen. De oplossing vergt
dan 9 keer varen (ook in de boot mogen nooit 2 kannibalen en 1
missionaris!).
Met 3 in de boot kunnen we zelfs 5 missionarissen en 5 kannibalen
overzetten (in 11 stappen). 6 kannibalen en 6 missionarissen kan nog
niet.
Als de boot 4 of hoger is, is elk aantal over te zetten: laat gewoon
continu 1 missionaris en 1 kannibaal heen en weer roeien met elke
keer op de heenweg als passagiers 1 andere missionaris en 1 andere
kannibaal. We gebruiken dan alleen de hoofddiagonaal van ons rooster.
Nogal een flauwe oplossing dus.
Een verwant probleem is het volgende:
3 jaloerse mannen met hun vrouwen staan op
de zuidoever.
Er passen twee personen in de boot.
Een vrouw mag nooit alleen zijn met een man die niet haar man
is...... |
Het grappige is dat dit probleem dezelfde vier oplossingen heeft als
ons oorspronkelijke missionarissenprobleem.
|
|