How many ants make a collision almost certain?

Question

On a regular n-gon, n ants each pick one of their two edges uniformly at random and walk at the same speed. How large must n be for the probability of no collision to drop below 1\%?

Accepted Answer

The ants avoid all collisions only when they all rotate the same way, which is 2 of the 2^n equally likely configurations: P(	ext{no collision}) = \frac{2}{2^n} = \frac{1}{2^{\,n-1}}. Require this below 0.01: \frac{1}{2^{\,n-1}} < 0.01 \quad\Longleftrightarrow\quad 2^{\,n-1} 100. Since 2^{6} = 64 < 100 and 2^{7} = 128 100, we need n - 1 \ge 7, i.e. n \ge 8. Eight ants already push the no-collision probability below 1\%: at n = 8 it is 	frac{1}{128} \approx 0.78\%. The safe outcomes are always exactly the two unanimous rotations, a fixed numerator of 2, while the number of possible configura…

How many ants make a collision almost certain?

Your answer

More Probability questions