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:
  1. er zit één missionaris in de boot:  één vakje naar links.
  2. er zitten twee missionarissen in de boot: twee vakjes naar links
  3. er zitten een missionaris en een kannibaal in de boot: schuin naar links en naar beneden
  4. er zitten twee kannibalen in de boot: twee vakjes omlaag
  5. 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.