File APIs for Java Developers
Manipulate DOC, XLS, PPT, PDF and many others from your application.
The moose likes Programming Diversions and the fly likes army problem ... Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login
JavaRanch » Java Forums » Other » Programming Diversions
Bookmark "army problem ..." Watch "army problem ..." New topic

army problem ...

R K Singh
Ranch Hand

Joined: Oct 15, 2001
Posts: 5382
Ahh.. .. was tired in MD
OK. It is well known problem of communication engineering.
The problem is.
There are two units of Green army, situated at peaks of two muntains.
The only medium of communication available is human messanger.
Between these two peaks there is Blue army.
Green army wants to attack on white army.
Green army can win only iff both units attack simultaneously.
Green Unit-1 (GU-1) sends a messanger to GU-2, with information that in the morning they will attack on Blue Camp.
Messanger has only one way to go GU-2. The way is to cross the Blue army Camp (BC).
If messanger(msger) get caught by BC, he will be killed.
Msger can be killed
1) while going to GU-2
2) while coming back to GU-1 after delivering the message to GU-2.
Now problem is:
1) If msger get caught while going to GU-2, GU-2 will never get message. And if GU-1 attacks on BC then they will get killed.
2) If msger get caught while coming back. GU-1 will never know that GU-2 has got the information.
GU-1 will wait for msger to come back.
GU-2 got the information, it wil atack as planed and get killed as GU-1 was waiting for msger.
How can one make sure that both Green units are in sync.
Means, how can they be sure that GU-2 and GU-1 both has got information[with confirmation] and both will attack at same time ?
Even if msger reaches GU-1, GU-2 has no way to know that GU-1 has got information.
Actually two units are transmitters/recievers and Blue army is noise which can corrupt data/info.

"Thanks to Indian media who has over the period of time swiped out intellectual taste from mass Indian population." - Chetan Parekh
R K Singh
Ranch Hand

Joined: Oct 15, 2001
Posts: 5382
And I thought its only me who is not getting solution ..
Timothy Chen Allen
Ranch Hand

Joined: Mar 16, 2003
Posts: 161
Originally posted by Ravish Kumar:
And I thought its only me who is not getting solution ..

Sorry about the wait. This can be seen as a kind of probabilities problem. First off, I believe there is no 100% sure way that the attack can go as planned. But the commander can maximize probabilities that the attack will go as planned.
Let's make some assumptions:
1) The green commander won't attack unless there is a 99% chance that the message has gone through and has been confirmed. This equates to the probability that at least *one* messenger out of all sent makes it to the friendly camp.
2) There is a 25% chance that any given messenger will make it through the enemy camp alive, or a 75% chance that he will be killed.
What is the probability that all the messengers sent will be killed? (.75)^n where n is the number of messengers.
What is the probability that at least one messenger will make it through? 1 - (.75)^n.
How many messengers have to be sent to ensure a 99% probability that one will make it without being captured and killed?
1 - (.75)^n > .99
(.75)^n < .01
1.33^n > 100
n > 16
So if the commander sends 17 or more messengers and there is a 25% chance that an individual soldier will make it alive through the enemy camp, there is a 99% chance that at least one soldier will make it through. I think.

Timothy Chen Allen
Learn Spanish in Washington, DC
I agree. Here's the link:
subject: army problem ...
It's not a secret anymore!