Definition:River Crossing Problem

From ProofWiki
Jump to navigation Jump to search


A river crossing problem concerns a group of people, who may or may not have a collection of objects, which need to cross a river.

The constraints of the problem are generally of the form:

$(1): \quad$ The boat can carry only a limited cargo, thereby making it impossible for the crossing to be made in one go
$(2): \quad$ Certain combinations of people or objects or both may not be left alone or in combination on either bank of the river.

In some versions of the problem, there are one or more islands midstream at which people or objects may be left for a while.

Also see

  • Results about river crossing problems can be found here.

Historical Note

The earliest known occurrences of river crossing problems appear in Propositiones ad Acuendos Juvenes by Alcuin of York.

There appear to be $3$ main types:

$(1): \quad$ A number of jealous men and their sisters, or missionaries and cannibals, where there are constraints on who can be left alone with whom
$(2): \quad$ A person trying to transport livestock and foodstuffs, where there are constraints on which may be left alone with what
$(3): \quad$ A person trying to transport goods or people, where there are constraints on the weight which can be transported at one time.

Various versions of each of these have been published, but apart from a few where the action is set in Africa, all seem to be of European origin.