Twenty-five ants are scattered on a meter stick. At the same time, they each pick a random direction (east or west) and start marching at 1cm/second. Whenever two ants meet, they turn around. When an ant reaches the end it falls off.
The ant in the middle is infected with a cold. An infected ant will spread the disease to any ant he bumps into.
On average, by the time every ant has fallen off, how many will be sick?
Answer
The average number of sick ants will be
$13 - \frac{6}{2^{12}}$
We start with the classic ant-on-a-stick observation that
we can imagine two ants as bouncing off each other as though they passed through each other, since their identities don't matter. So, in an equivalent problem, ants don't bounce, and an ant is infected by passing through another infected ant.
Now, make an observation about how ants get infected:
The infected range spreads at most as fast as an ant walks. So any ants the start moving away from the center ant cannot be infected. Any ants that start going towards the center get infected as long as an infected ant going the other way touches the center point. Usually, that's all ants that start going towards the center ant (expected $12$), since the center ant infects all such ants in front of him, and any such ant infects all such ants behind him. But, if all ants in front of the center ant are going the same way (probability $2^{-12}$), no ants behind him are infected, decreasing the expectation by $6$. Counting the $1$ infected center ant, this gives an expectation of $1+12-2^{-12}\times 6 = 13 - \frac{6}{2^{12}}$.
No comments:
Post a Comment