[OT] Retreating from Iraq

[Andrei Alexandrescu]

Andrei Alexandrescu wrote:
> Suppose that a miracle happen and the decision is taken at the highest 
> level to retreat all of US military presence from Iraq. That will take a 
> while, but sending the orders quickly is a must.
> 
> For utmost certainty, all orders are to be sent via phone and down the 
> command chain, and only to direct subordinates. Each officer has a 
> variable number of subordinates. Initially the president calls his 
> immediate subordinates, who call their immediate subordinates, etc. Each 
> call can be assumed to take the same amount of time.
> 
> Devise an algorithm that ensures every foot soldier gets the news as 
> quickly as possible, show it is correct, and show it is fast.

Thanks for all the answers! Whew, it's been a wild ride. A few notes:

* Solutions that focused on the number of sub-subordinates without 
taking into consideration global structure are, alas, wrong.

* Looking over the thread in increasing order of date, I see Russell 
Lewis was the first to give the correct algorithm, and also sketched a 
proof. Kudos! Benji and Sergey also gave correct answers.

* Sorry Bjoern, I did not have the time to follow the Propagator pattern.

* I couldn't follow Nick's solution, but given that the right answer is 
rather simple, there may be some issues there.

The next problem also concerns retreating from Iraq, with a twist.


Andrei