Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Last Saturday's Guardian newspaper contained the following puzzle:

Two soldier ants start on different vertices of an equilateral triangle. With each move, each ant moves independently and randomly to one of the other two vertices. If they meet, they eliminate each other. Prove that mutual annihilation is eventually assured. What are the chances they survive... exactly N moves.

I understand that the probability of a collision on any one move is 1/4, but I don't understand the quoted proof of eventual annihilation:

If the chances of eventual mutual annihilation are are P, then P = 1/4 + 3/4 P, so P = 1.

I scratched my head for a while but I still couldn't follow it. Do they mean the probability in the limit of an infinite number of moves? Or is there something crucial in that calculation of P that I'm not getting?

share|improve this question
    
Like davin stated in his answer, I think the proof makes sense only if two ants do not eliminate each other if they meet on an edge, meaning that they only die if they meet at vertices. I wanted to add that for people who are trying to solve the problem without looking at the answers :) –  marvinthemartian Feb 7 '12 at 14:21
    
I think "is eventually assured" should be "happens almost certainly". That means the probability is $1$, but it does not mean the opposite is impossible. –  Marc van Leeuwen Feb 7 '12 at 15:08

3 Answers 3

up vote 1 down vote accepted

It's a simple geometric distribution (worth a google/wiki), which in and of itself is a justification why eventual annihilation occurs with probability 1. It's worth noting that the question assumes they can pass by each other without dying - i.e. they only die at vertices.

However their argument is simpler; it simply says that at any given stage of the scenario P(eventually die) = P(die on this move) + P(don't die this move)*P(eventually die), which can be solved algebraically as they did. The argument is simply additivity and multiplicity of probabilities.

share|improve this answer
    
Okay, so it's Bernoulli trials and they're just noting that the cdf tends to 1 "eventually"? I guess I was getting hung up on the language; the salesman assuring me of delivery, but forgetting to mention it might take an infinitely long time. Thanks. –  Deditos Feb 7 '12 at 17:59
    
@Deditos, kind of. The Bernoulli trials/geometric distribution aspect is how to prove that with certain probability the event (annihilation) will occur. However like I said, their method is simpler because they don't prove that, what they say, is that assuming the probability is well-defined, its value will satisfy the given relation, and therefore be 1. But yes, the idea is that of infinite here; i.e. That with certainty the event occurs at some finite point between now and infinity (indeed no "time of delivery" is guaranteed). –  davin Feb 7 '12 at 18:17

Note that the fact that it's a triangle is irrelevant. The ants could move to random vertices on any $n$-gon and the result would be the same.

Put another way, if two people repeatedly choose random integers from $1$ to $n$, they will eventually choose the same number.

share|improve this answer
    
While what you say might be true, your reasoning does not seem right. There are only $2$ possible choices at each move. –  Aryabhata Mar 3 '12 at 17:47
    
@Aryabhata Ah, right. Thanks. My answer should specify that $n \geq 2$ and that the people choosing random numbers are forbidden to choose the same number twice in a row. Still, the original problem seems trivial, in the sense that regardless of the probability $k$ of collision, the equation $P = k + (1-k)P$ will always give $P = 1$. –  Théophile Mar 3 '12 at 19:59
    
This argument does not work in full generality: the configuration after one step with no collision must be the same than before, or at least give rise to the same P. This is true on a triangle and on a square but not on the polygons with more vertices, hence the argument, as it is, is not sufficient. –  Did Mar 3 '12 at 20:27

If they do not meet then they are on different vertices, and so you are at the equivalent of the starting position. So $P$, the probability of eventual annihilation at the start is the probability of annihilation on the first move plus the probability of non-annihilation on the first move times the probability of eventual annihilation after the first move given it has not happened yet. The last is the same as the probability at the start.

To me the harder question is why $1/4$ is correct for the probability of annihilation on the first move. I would have thought that $1/2$ is arguable: either they both move to the third point, or they meet when trying to swap places.

share|improve this answer
    
If they start at (1,2), they can move to (2,3), (3,3), (2,1), or (3,1). Only the second leads to annihilation. –  Ross Millikan Feb 7 '12 at 13:55
1  
@Ross: I think if they try to move from $(1,2)$ to $(2,1)$ they should meet inbetween, even if they travel at different speeds. –  Henry Feb 7 '12 at 14:04

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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