Two ants on a triangle puzzle

Question

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?

Answer 1

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.

Answer 2

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.