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.

Hmm. The expected number of fights is therefore:

(i=300 to 799) Σ (i! / ( (2^i) * (i-300)! ))
divided by
(i=300 to 799) Σ ((i-1)! / ( (2^i) * (i-300)! ))

(Eliminating the unneccessary 299! since it cancels out in the division, being a constant)

Here's a counter-example to the intuitive solution

As an interesting experiment, try 200 knights vs. 201 knights. You'll find (if my values are accurate) that the expected value is closer to 385 "battles", and therefore an average of 16 knights remaining in the larger army (with the given assumption that the larger army won)

Edited on August 25, 2005, 7:45 am

Posted by Dimmeh on 2005-08-25 07:16:12