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?

  • $\begingroup$ When you say "scattered", are the initial positions of the ants independent and uniformly distributed? $\endgroup$ Jul 2 '15 at 23:36
  • $\begingroup$ @randal'thor The only thing you know about the initial positions is that no two ants are on top of each other. For all you know, they were chosen by a mad hatter $\endgroup$ Jul 2 '15 at 23:37
  • 2
    $\begingroup$ @xnor There are 25 ants $\endgroup$ Jul 2 '15 at 23:38
  • 11
    $\begingroup$ @MikeEarnest Wow, I read twenty fire ants. $\endgroup$
    – xnor
    Jul 2 '15 at 23:39
  • 3
    $\begingroup$ Fire ants having a cold? $\endgroup$
    – Vajura
    Jul 3 '15 at 7:29

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}}$.

  • $\begingroup$ Well said! Can't think of a better answer $\endgroup$ Jul 3 '15 at 0:38
  • $\begingroup$ Perfect, thanks. Now I only have to get the picture of a sneezing ant out of my head again... $\endgroup$
    – BmyGuest
    Jul 3 '15 at 6:43
  • $\begingroup$ @MikeEarnest If the answer is satisfactory, you should accept it. $\endgroup$ Jul 3 '15 at 23:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.