DEV Community

Cover image for Marching Ants Puzzle

Marching Ants Puzzle

bandagedg profile image Bandaged Group ใƒป1 min read

Suppose there is an ant at each vertex of a triangle (cube, regular tetrahedron / octahedron / dodecahedron / icosahedron / general planar graph / any graph).

Suddenly each ant randomly (with equal probability) picks a neighboring edge and crawls along it to the next vertex. What is the probability that no two ants collide, neither on a vertex, nor en route on an edge?

Example solution for triangle.
Each ant can move either Left, or Right. That gives 8 options: LLL, LLR, LRL, LRR, RLL, RLR, RRL, RRR. However, only in LLL and RRR no ants collide. Two options out of eight give probability 2/8 = 1/4.

Give your numeric solutions for the mentioned polyhedra or an algorithm for a sufficiently general case!

Discussion (0)

Editor guide