Enigmatic Code

Programming Enigma Puzzles

Puzzle #34: Ant on a tetrahedron

From New Scientist #3259, 14th December 2019 [link] [link]

Three short-sighted spiders are clustered at the vertex of a wire frame in the shape of a tetrahedron. The spiders know that there is an ant walking around the frame, but they have no idea where it is. They will only be able to spot it when they are practically on top of it. The ant, on the other hand, has excellent eyesight and can plan its route accordingly to avoid the spiders. Given that the ant walks slightly slower than the spiders, is there a way for the ant to escape the spiders indefinitely? Or can the spiders find a strategy to be certain of catching the ant?


2 responses to “Puzzle #34: Ant on a tetrahedron

  1. Jim Randell 14 December 2019 at 9:38 am

    If the spiders start at the upper vertex, and agree to meet at one of the base vertices, so one spider traverses one edge and the remaining two traverse two edges each to arrive at their destination. Then the spiders will have swept 5 of the 6 edges, and the only way the ant can evade capture is to have taken refuge on the unswept edge.

    The ant will see the spiders approaching the base and must choose one of the three base edges to position itself on. One of them will be safe, but for the other two the ant is trapped between two spiders and cannot escape.

    So the spiders have a 2/3 chance of capturing the ant before they meet up, and the ant has a 1/3 of evading capture.

    If the spiders have not caught the ant, they can just pick another vertex to convene at. If they do so randomly without divulging their choice to the ant, then the ant’s chances of evading capture for each time the manoeuvre is carried out is only 1/3, so the probability of the ant evading capture approaches zero as the number of times the manoeuvre is executed increases. By the time the spiders have executed their manoeuvre 5 times they have a greater than 99% chance of having caught the ant.

    The plan falls down if the ant is incredibly lucky, or can determine the spiders meeting point, then it can wait on the edge that is not traversed and move to the next safe edge once the spider’s next move is determined.

    So depending on your point of view the answer to the puzzle is either: No; the chance of the ant escaping indefinitely is zero; or: Yes; an incredibly lucky, or incredibly well informed ant could escape indefinitely.

    • Jim Randell 17 December 2019 at 1:34 pm

      Actually I think there is a strategy the spiders can adopt so that they can guarantee to catch the ant in a finite time. So the ant cannot escape indefinitely.

      The following diagram shows the tetrahedron viewed from above:

      If one of the spiders follows the red path: ABCD, and the other two patrol the blue and green edges: AC, BD, the the following way:

      [1] red: A→B; green: D→B
      [2] red: B→C; blue: A→C
      [3] red: C→D; green: B→D
      [4] red: D→A; blue: C→A

      When we start if the ant is on AB, then it has to hurry towards B to avoid being caught by red, and green is traversing DB, it is forced onto BC, pursued by red. If it can keep ahead of red along BC it is forced onto CD as blue is traversing AC. Again if it can keep ahead of red on CD it is forced on to DA as green is approaching along BD. If it can stay ahead of red along DA, then it is forced onto AB as blue is approaching along CA. The ant thus returns to its starting position, and if red has not caught it, it has gained ground on the ant, will eventually catch up with it.

      If the ant starts on either of the edges patrolled by blue or green then it will be forced onto the red circuit, which it must follow in the same direction as red, and eventually be caught.

      If the ant starts on one of the red edges it is forced into following the circuit in the same direction as red, and is eventually caught.

      And if red gets tired, it can swap jobs with one of the other spiders when they meet.

Leave a Comment

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.

%d bloggers like this: