The missionary and cannibal task is the classic task of crossing the river. Closely related to her is the task of jealous husbands , she is also the task of knights and squires .
Formulations
- The mission of the missionaries and cannibals. Three missionaries and three cannibals must cross the river in a boat capable of supporting no more than two people. At the same time, there are no more cannibals left on one side than missionaries (otherwise they will eat the missionaries). The boat also can not cross the river without people on board.
More difficult option:
- The task of jealous husbands. Three married couples must cross the river in a boat with the same conditions and with the restriction that no wife can be without her husband in the presence of another man.
Note that on the same bank there can be no more men than women. Thus, if men are replaced by cannibals and women are missionaries, any solution to the task of jealous husbands will also be a solution to the problem of missionaries and cannibals.
The latter task is also known in the formulation of knights and squires - a squire in the absence of his knight offend other knights.
History
The first known mention in the version of jealous husbands is found in the medieval text , attributed to Alquin , who died in the 804th year. In this formulation, there are three pairs of brothers and sisters, but the restrictive factor is still the same: none of the women can be in the company of another man without his brother. The same text contains the wolf-goat and cabbage problem .
From the 13th to the 15th centuries, the task became known throughout northern Europe, already with wives and husbands in the formulation. In a later formulation, three pairs of masters and servants or knights and squires appear. A simplified version of the missionaries and cannibals appears in the late nineteenth century.
Variations
An obvious generalization is the change in the number of jealous couples, the capacity of the vessel, or both.
- If the boat accommodates two people, then
- two couples require five trips,
- for four or more pairs, the problem has no solution.
- If the boat can accommodate three, then you can carry up to 5 pairs.
- If the boat can withstand four people, then it is possible to transport any number of pairs.
- If in the middle of the river to add an island, then any number of couples can cross the river in a double boat.