- #1
- 352
- 87
The fox, sheep, cabbage problem is too complicated of a task for a person to figure out. Someone should design a simple battery operated computer for this guy so he doesn't have to think.
Let the high from the battery equal the left side of the river and the low from the battery equal equal the right side of the river. The computer will have 4 switches (one each for the person, fox, sheep, and cabbage). The person can flip the switches to try out different combinations. A light will light up if the decision would be a bad one. In essence, you have a truth table
P S F C L
0 0 0 0 0 Every one is on the right side, person can control chaos
0 0 0 1 0 Cabbage is alone, person can keep fox from eating sheep
0 0 1 0 0 Fox is alone, person can keep sheep from eating cabbage
0 0 1 1 0 Fox doesn't eat cabbage, no problem
0 1 0 0 0 Sheep is alone, no problem
0 1 0 1 1 Now we have a problem - sheep can't be left alone with cabbage
0 1 1 0 1 Problem, fox will eat sheep on left side of river
0 1 1 1 1 Big problems, major chaos - who knows what will happen
1 0 0 0 1 Still big problems, just on right side of river instead of left
1 0 0 1 1 Fox will eat sheep on right side of river
1 0 1 0 1 Sheep will contentedly eat cabbage on right side of river
1 0 1 1 0 No problem, as long as sheep doesn't get lonely
1 1 0 0 0 Now nobody's lonely
1 1 0 1 0 Foxes don't get lonely
1 1 1 0 0 Neither does cabbage
1 1 1 1 0 Mission accomplished, everyone's on other side of river
The six possible problems can be reduced to four logical combinations via Boolean logic. Letting '!' represent 'not', the circuitry of the computer can be reduced to:
(P!)SC + (P!)SF + P(S!)(F!) + P(S!)F(C!)
Now the person can tell if a certain combination will cause him a problem. Unfortunately, this doesn't give the person a combination that will carry him from 0000 to 1111. A binary counter won't work - it will have some people swimming and sometimes will have no one bringing the boat back (plus it will count right through the problem). A Gray Code counter also has some problems - it only moves one person at a time, sometimes having the boat move the same direction two times in succession (plus it will count right through the problem).
How do you design a counter that will count the proper combinations in succession, avoiding situations which will light the light?
Let the high from the battery equal the left side of the river and the low from the battery equal equal the right side of the river. The computer will have 4 switches (one each for the person, fox, sheep, and cabbage). The person can flip the switches to try out different combinations. A light will light up if the decision would be a bad one. In essence, you have a truth table
P S F C L
0 0 0 0 0 Every one is on the right side, person can control chaos
0 0 0 1 0 Cabbage is alone, person can keep fox from eating sheep
0 0 1 0 0 Fox is alone, person can keep sheep from eating cabbage
0 0 1 1 0 Fox doesn't eat cabbage, no problem
0 1 0 0 0 Sheep is alone, no problem
0 1 0 1 1 Now we have a problem - sheep can't be left alone with cabbage
0 1 1 0 1 Problem, fox will eat sheep on left side of river
0 1 1 1 1 Big problems, major chaos - who knows what will happen
1 0 0 0 1 Still big problems, just on right side of river instead of left
1 0 0 1 1 Fox will eat sheep on right side of river
1 0 1 0 1 Sheep will contentedly eat cabbage on right side of river
1 0 1 1 0 No problem, as long as sheep doesn't get lonely
1 1 0 0 0 Now nobody's lonely
1 1 0 1 0 Foxes don't get lonely
1 1 1 0 0 Neither does cabbage
1 1 1 1 0 Mission accomplished, everyone's on other side of river
The six possible problems can be reduced to four logical combinations via Boolean logic. Letting '!' represent 'not', the circuitry of the computer can be reduced to:
(P!)SC + (P!)SF + P(S!)(F!) + P(S!)F(C!)
Now the person can tell if a certain combination will cause him a problem. Unfortunately, this doesn't give the person a combination that will carry him from 0000 to 1111. A binary counter won't work - it will have some people swimming and sometimes will have no one bringing the boat back (plus it will count right through the problem). A Gray Code counter also has some problems - it only moves one person at a time, sometimes having the boat move the same direction two times in succession (plus it will count right through the problem).
How do you design a counter that will count the proper combinations in succession, avoiding situations which will light the light?