Consider two opposing armies of knights armed only with swords. The sizes of these armies are 500 and 300 knights.

When locked in combat with an enemy each knight has even odds of winning or losing. Knights, being chivalrous, prefer single combat and will not double up on their enemies. The extra knights in the larger army will wait until there is a free enemy to fight.

[Essentially the killing power of the larger army is proportional to the size of the smaller army.]

When the dust settles the smaller army is eliminated. How many knights (are expected to) remain in the larger army?

Generalize for two armies of size A and B where A>B.

The probability of the smaller army dying after n jousts
(300≤n≤799) is (n-1)-choose-299 * (1/2)^n.
Choose is kCr=k!/(r!*(k-r)!) btw.

Why this formula? because the last knight to die must obviously die on the last mini-fight (a mini-fight being where either of two knights kills the other), or the small knights technically died earlier :). So it's 299 knights dead up to that point, then the last on the last As such, it's just binomial probability with one knight already decided.

799 is the upper limit because if there are 800, then all of the  knights have died, which can't work.


Here's the proper solution then:
Every time you add 1 to n, you multiplty the probability by (n)/2(n-299)

Where can this value equal one? When
n=2(n-299)
n=598

For n<598 the value is larger than 1. For n>598 the value is smaller than 1

This means that, for all n<598, adding one will increase the probability.At n=598, adding one to the number of "fights" will make no change to the probability (multiply by 1). Adding another one after that point will begin to decrease the probability.

This means that there is an equal probability of either 598 or 599 fights, or 298 or 299 dead knights from the larger army.

This means that there is an equal probability of either
201 or 202 knights remaining from the larger army.

The general case: number of fights is either
j=2*(B-1)
 =2B-2
or 2B-1.

Number of knights dead from from larger knight group:
B-2 or B-1

As such, the number of knights remaining in the larger group of knights is either of these two:
A-B+1
A-B+2

Edited on August 24, 2005, 12:13 pm

Posted by Dimmeh on 2005-08-24 09:04:01