Scholar Asked on 29th September 2015 in Interview Puzzles.
The missionaries and cannibals problem, and the closely related jealous husbands problem, are classic river-crossing problems
The missionaries and cannibals problem is a well-known toy problem in artificial intelligence
Source of solution – WIKIPEDIA
Amarel devised a system for solving the Missionaries and Cannibals problem whereby the current state is represented by a simple vector <a,b,c>. The vector’s elements represent the number of missionaries on the wrong side, the number of cannibals on the wrong side, and the number of boats on the wrong side, respectively. Since the boat and all of the missionaries and cannibals start on the wrong side, the vector is initialized to <3,3,1>. Actions are represented using vector subtraction/addition to manipulate the state vector. For instance, if a lone cannibal crossed the river, the vector <0,1,1> would be subtracted from the state to yield <3,2,0>. The state would reflect that there are still three missionaries and two cannibals on the wrong side, and that the boat is now on the opposite bank. To fully solve the problem, a simple tree is formed with the initial state as the root. The five possible actions (<1,0,1>, <2,0,1>, <0,1,1>, <0,2,1>, and <1,1,1>) are then subtracted from the initial state, with the result forming children nodes of the root. Any node that has more cannibals than missionaries on either bank is in an invalid state, and is therefore removed from further consideration. The valid children nodes generated would be <3,2,0>, <3,1,0>, and <2,2,0>. For each of these remaining nodes, children nodes are generated by adding each of the possible action vectors. The algorithm continues alternating subtraction and addition for each level of the tree until a node is generated with the vector <0,0,0> as its value. This is the goal state, and the path from the root of the tree to this node represents a sequence of actions that solves the problem.
The earliest solution known to the jealous husbands problem, using 11 one-way trips, is as follows. The married couples are represented as (male) and a (female), and b, and and c.
Trip number Starting bank Travel Ending bank (start) a b c 1 b c a → 2 b c ← a 3 bc → a 4 ← a b c 5 a → b c 6 a ← b c 7 a b → c 8 a b ← c 9 b a c → 10 b ← a c 11 b → a c (finish) a b c
This is a shortest solution to the problem, but is not the only shortest solution
If however, only one man can get out of the boat at a time and husbands must be on the shore to count as with his wife as opposed to just being in the boat at the shore: move 5 to 6 is impossible, for as soon as has stepped out b on the shore won’t be with her husband, despite him being just in the boat.
As mentioned previously, this solution to the jealous husbands problem will become a solution to the missionaries and cannibals problem upon replacing men by missionaries and women by cannibals. In this case we may neglect the individual identities of the missionaries and cannibals. The solution just given is still shortest, and is one of four shortest solutions.
If a woman in the boat at the shore (but not on the shore) counts as being by herself (i.e. not in the presence of any men on the shore), then this puzzle can be solved in 9 one-way trips:
Trip number Starting bank Travel Ending bank (start) a b c 1 b c a → 2 b c ← a 3 c ab → 4 c ← b a 5 c b → a 6 c ← b a 7 bc → a 8 ← c a b 9 c → a b (finish) a b c
- 8778 views
- 2 answers
- 1 votes
Scholar Asked on 18th July 2015 in Logic Puzzles.
A’s hat must be blue.
If it was white then either of B or C (who we are told are wise sages and presumably also reasonable logicians) would be able to work out that they have a blue hat.
Here’s how: If A’s hat is white then B can reason that if his own hat was also white, then C would see two white hats. Since they have all been told that at least one of them will be given a blue hat, C would know immediately that his must be the blue one. Since C has said nothing “for hours” B should be able to conclude quite quickly that his own hat was also blue.
Since B has also not said anything for hours, A must eventually conclude that the premise that his own hat is white is false and that he also has a blue one (although if these sages were any good they would reach this conclusion after a few minutes).
The logic fails if the reason for the other sage’s silence is because they have fallen asleep with their eyes open.
- 9282 views
- 4 answers
- 1 votes