Pour franchir une rivière,3 missionnaires et 3 cannibales doivent utiliser une barque qui ne peut supporter plus de 2 personnes. Si à tout moment les cannibales sont plus nombreux que les missionnaires sur l'une des deux rives, les missionnaires seront tués et mangés. Les six protagonistes peuvent-ils traverser la rivière sains et saufs ? S'ils le peuvent, comment y arrivent-ils avec un minimum de traversées et quel est le nombre de façons de parvenir à ce minimum? Que se passe-t-il avec 4 missionnaires et 4 cannibales ?
Généraliser le problème avec a missionnaires et a cannibales, a=4,5 et 6 et une barque supportant p personnes (p=2,3,4,5). Dans la barque comme sur chacune des deux rives, les cannibales ne peuvent pas être plus nombreux que les missionnaires.

Source : d'après Martin Gardner- Pour la Science n° 31 -  Mai 1980

 Solution