Foodletown has a Volunteer Emergency Response Team which assists the police and fire departments. The members are alerted by phone. The police or fire chief will notify the captain of the V.E.R.T., who will notify the members. The captain will call certain members, who may call other members, and so forth. Each caller gives the location and nature of the emergency, and also may give up to 2 pieces of information to direct the phoning process, such as "I have called Smith, but I have not called Jones," or "You call Smith next and I will call Jones next." Assume that each call lasts exactly 1 minute.
How should the calling be organized such that all V.E.R.T. members are notified within the shortest possible time?
You need to address two cases. In the ideal case, every member is reached, and the calling proceeds by a fixed plan.
In the real-world case, there is a 50% chance that any given member is reached. (The captain is always reached.)
In both cases, give the expected number of minutes if the squad has 100 members.
Note: No global database exists of who has been notified so far.
Here's a rule where no one is assigned more than 2 calls:
If you are person p, you are assigned to call 2p and 2p+1.
1 will call 2 then 3
2 will call 4 then 5 etc.
In the ideal case everyone will be called by minute 10.
[rule for when you are called, convert your number to binary. Count one minute for every 0 and two minute for every 1 beyond the leading one. Person 63=111111 gets called on minute 10. Person 100=1100100 gets called on minute 8.]
This is less efficient than before but seems better to me for the 'real-world case' since if you can't reach a person you only have to call 2 extra numbers. I wouldn't know where to start trying to calculate an expected value, though.
This tree can easily cascade, though, because 50% is pretty high. 1/4 of people might have to try 4 extra numbers. The problem doesn't state how long a missed call takes.
The best solution might balance fewer calls which takes longer but is more robust. I suspect e would show up with a fibonacci approach.
|
|
Posted by Jer
on 2023-12-25 12:51:34 |
Different tree with 'real-world' thought
