Problem of the Week-1: Can The Generals Attack?
There are two allied generals A and B whose camps are on the opposite sides of a ridge. They can communicate with each other only by carrier pigeon. The pigeons sometimes get lost or killed by birds of prey.
The generals must decide whether or not to attack the enemy the next morning. Whatever they decide, either they both attack or neither attacks, because an attack by just one would lead to a disaster.
Suppose general A decides that the moment is propitious, so he sends a message via carrier pigeon to general B, saying "Attack at dawn". Without receiving confirmation, general A won't attack, so asks general B to acknowledge the message. General B sends his acknowledge.
Question 1: How many successful carrier pigeon trips does it take for the generals to attack?
Now consider the following variation of the problem: Suppose the armies have scouts on top of the ridge who light a beacon for a few seconds each time a carrier pigeon successfully makes a trip from one general to the other. Suppose both generals can see the beacon.
Question 2: How many successful carrier pigeon trips are required then?
Justify your answers.
Submit your answers (by e-mail or hard copy) before 4 pm on 1/28/05 to Noah Aydin.