1. Napoleon and his army are lost in the desert. They have four days of water le
ID: 3143248 • Letter: 1
Question
1. Napoleon and his army are lost in the desert. They have four days of water left. The edge of the desert is three days’ march in exactly one of the four cardinal directions (i.e., North, South, East, or West). The army has eight scouts and, additionally, Napoleon himself volunteers to be a scout (for a total of nine scouts). Since the scouts are on horseback, they can travel the entire distance to the edge of the desert and make it back to the army in just one day and since he has nine scouts, he can send multiple scouts in the same direction. Theoretically then, there is exactly enough time for the scouts to check out each of the four possible directions, report back, and then for the entire army to march out of the desert just as their water is running out.
However, Napoleon knows that exactly two of his scouts are enemy spies. If possible, the spies are ordered to mislead the army into heading in the wrong direction and march to their doom. To do so, the spies may choose to either lie or tell the truth about whatever they find on their scouting trip. For instance, they may collude with one another and decide they will both say they found the edge of the desert, even though they went in opposite directions. Or, if one finds the edge of the desert, he may lie. However, they will not hurt or otherwise reveal themselves to Napoleon or the other honest scouts.
How should Napoleon divide himself and his eight other scouts among the four cardinal directions to ensure he knows which way to direct his army? Explain exactly how you know your solution works.
Explanation / Answer
Obviously since Napolean can scout, he takes one of the directions alone. If this ends up at the edge of the desert, this is the direction the army takes.
The other three will split into three-three-two.
Clearly if the scouts are both in a group of three, the spies will lie but their lone comrade will tell the truth leading in contradicting suggestions and Napolean will know that the group of two has no spies. If the group of two says they found the edge of the desert, this is the direction the army takes. Otherwise he will check if the group of three who do not contradict with each other shall say if they found the edge of the desert. If they say they did, this is the direction the army takes. Otherwise the army takes the only direction left.
If on the other hand the scouts are in different groups, two groups will self contradict. First the group which shows no contradiction shall be asked. Then Napolean simply needs to check for the majority opinion within the group of three which contradicted and ignore the one scout (spy) who contradicts his own comrades. This way he will know which way the army shall take.
If the scouts are in the group of two, they will lie. If they found the edge of the desert, they will say they did not and the two groups of three will also say the same thing. Because the sayings of the scouts are consistent within the same group, Napolean will know that the spies are in the group of two and the direction in which they went is the direction the army will go. On the other hand if they did not find the edge of the desert, they will say they did and the group of three which actually found it will say likewise. Because the sayings of the scouts are consistent within the same group, Napolean will know that the spies are in the group of two and the group of three which said they found the edge of the desert is saying the truth. Theirs will be the direction the army shall take.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.