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.
This is a realy long winded way of solving it but will generalise to other coin tossing problems.
Define: f=probability of a knight from the smaller army winning=0.5.
For each round
P(Lose)=f
The knight of the larger army is still standing -0
P(win)=(1-f)
The knight of the larger army is dead -1
Goes on to fight the next knight
The question is "what is the expected number of rounds"
Define: n=number of rounds
The probability distribution of n is given by:
P(n)=f*(1-f)ⁿ
i.e. the probability of making it though n rounds without dying multiplied by the probability of dying in that round of combat.
The expected number of rounds is given by the sum 0→∞
E(n)=Σ nP(n)
i.e for this problem =0.5*Σ n*0.5ⁿ
This is a nasty infinite sum so we want to avoid having to do it.
Consider what happens if we limit our knight to a maxium of 2 rounds of
combat. The expectation for this is E(n)=f*0+(1-f)*1 since we have f
chance of dying and (1-f) chance of going on. But the expectation for
the next round of combat is the same!
this leads to the following recursive formular
E(n)=f*0+(1-f)*(E(n)+1)
thus by rearranging
E(n)=(1-f)/f
For our problem this is 1
Thus the number of knights in large army=500-E(n)*300
=200
Full generalised derivation
