Skip to main content
Post Made Community Wiki
Source Link
Qiaochu Yuan
  • 118.2k
  • 40
  • 447
  • 741

Adam Hesterberg told me this one ages ago. It apparently used to circulate around MOP.

Three spiders and a fly are placed on the edges of a regular tetrahedron, and travel only on those edges. The fly travels at the rate of $1$ edge/s, whereas the spiders travel at the rate of $1 + \epsilon$ edge/s for some $\epsilon > 0$. The spiders want to agree beforehand on a deterministic strategy for capturing the fly, whose location they do not know (but they do know each others' locations). The fly is invisible and omniscient; in particular, it is aware of the locations of the spiders and of their strategy at all times. (It also cannot fly.)

Can the spiders guarantee that they will catch the fly in finite time, regardless of the initial positions of the spiders and the fly? Does the answer depend on the value of $\epsilon$?