TOAD 18 - Spiders and a Fly

Problem

三只蜘蛛想要在一个立方体上抓住一只虫子。已知虫子的最大速度是蜘蛛的最大速度的三倍，且蜘蛛和虫子都只能在棱上活动。对于任意的初始局面，蜘蛛是否都能抓到虫子？

Solution

蜘蛛一定可以抓到虫子。其实只要想到蜘蛛的最优点不是在点上而是在棱上就可做了。

首先容易知道，如果虫子可以走的路径中没有环，也就是只是一棵树，那么显然蜘蛛赢，只管一路追过去就好了。可是有环怎么破？

我们先把三维空间放到二维平面上来。

现在，我们可以给出一个结论：一只蜘蛛可以同时控制一条边的两个点不让虫子经过。假设我们要控制的是 AB 这条边。则任意时刻，这只蜘蛛只要保证虫子到 A 的最短路长度比虫子到 B 的最短路长度等于自己到 A 的最短路长度比自己到 B 的最短路长度。由于虫子到 A 的最短路加上虫子到 B 的最短路至少是三条棱，而蜘蛛只有一条棱，两者最大速度比恰好是 3:1 ，所以这总是可以满足的。

所以，一只蜘蛛控制 DH 这条边，另一只蜘蛛控制 FB 这条边，则剩下的图是两棵孤立的树，还有一只蜘蛛追过去就好了。