Two spiders are trying to catch an ant. All are constrained to move along the edges of a transparent cube. The speed of the ant is $1$. The speeds of the spiders are $v_1$ and $v_2$ respectively. What's the minimum value of $v_1+v_2$ if the spiders can catch the ant for any starting positions? What's the minimum value of $v_1+v_2+v_3$ if there're three spiders?
For two spiders, one of the spiders has to be at least as fast as the ant in order for the spiders to catch the ant.
There are 3 situations:
- Both spiders are slower than the ant: The ant can avoid forever
- At least one spider is as fast as the ant: The spiders can catch the ant
- At least one spider is faster than the ant: The spiders can catch the ant
Situation 2: At least one spider is faster
This is the simplest situation of the 3. The faster spider can simply go to the ant's starting position by any path. At this point it can simply follow the ant's path and it will eventually catch up.
Situation 1: Both spiders are slower
If both spiders are slower than the ant then the ant can employ the following strategy:
- Start at a corner that does not contain a spider
- Pick one of the three adjacent corners that is distance at least 1 from both spiders (we will see that such a corner must exist)
- Travel to that corner
- Goto (2)
The ant can always reach its destination corner before any spider because the destination corner is distance 1 from the ant and distance >= 1 from the spiders and the ant is faster than the spiders.
If the spiders wanted to defeat this strategy they would need to be distance < 1 from all three of the corners that the ant is choosing from. However each of those corners is distance 2 from each of the others, so by the triangle inequality the spiders cannot be distance < 1 away from two of them at one time and there are only two spiders.
Situation 3: At least one spider is as fast as the ant
Here assume one spider has speed 1 and the other has speed e < 1. We will see the spiders can catch the ant.
Call the spider with speed 1 the guard spider and the spider with speed e the pursuit spider. Note the vertices of the cube form a bipartite graph, that is we can color half the vertices black and the other half white so that no edge connects two vertices of the same color (i.e. we can checkerboard color the vertices).
The guard spider will start by taking position at a white vertex. The pursuit spider will make its way toward the ant. The ant will eventually need to move. If the ant starts on an edge it will need to move to a vertex. If it moves to a white vertex the spiders move to phase 2. If it moves to a black vertex the pursuit continues. Eventually the ant will have to move off the black vertex and onto a white vertex (because black vertexes are only connected to white vertexes and vice versa).
At this point we have both the ant and the spider on a white vertex. If it's the same vertex than the spiders have caught the ant so lets suppose it isn't. This means the ant and the spider are diagonal from each other across one face of the cube. Call that face f_1 and the opposite parallel face f_2. The guard spider will now mirror the ant's movements. If the ant approaches either of the other two corners of f_1, the spider will approach as well. If the ant moves to f_2, the spider will as well and the spider will continue to mirror on f_2. If the ant moves to any vertex that is not the vertex it is currently on or the corresponding vertex on f_2, the guard ant will catch it there.
This guarding restricts the ant to 5 edges that have no cycles. The pursuit ant can now chase and corner the ant no matter how slow it travels.
In a way this answer is slightly disappointing since the combined speed is 1 + e the same as if we just had one spider that was faster than the ant and one spider with speed 0 and that situation was much easier to analyze, haha.
Not a definite answer but I narrowed it down to 2 possibilities.
1 + ε, where ε is any positive real number
In this case
you just assign that full speed to one of the spiders and the other will have speed 0 and then the first spider just follows the ant's path and he'll catch up eventually.
or the second possible answer is
it can't be any lower. Even if both spiders had speed 1 - ε, where ε is any positive real number, the ant can outsmart them with a simple strategy. The ant needs to wait in a corner until one (or both) spiders are exactly 1 edge away. He has 3 possible paths from there, so he just takes the path furthest away from the second spider and walks completely until he is in a corner again. Then he just repeats that strategy. Because there is is always 3 options from each corner there must logically be one option that's 2 or more edges' length away from any spider, so he can beat any spider to the next corner. I'm not sure if this is proof enough but it seems trivial to me
An upper bound for the 3 spider case:
2/3 + ε (for any positive real ε), using the strategy listed in this answer. We assign speeds as v1 = 1/3, v2 = 1/3, v3 = ε. The 1/3 speed spiders prevent the ant from crossing from one half of the cube to the other. The ε spider slowly but surely forces the ant towards one of the others
I feel like 1/2+ε is enough for the 3 spider case. The spiders can start (or take their sweet time to get) in this configuration:
And then the two slow spiders can follow the red arrows to ensure the ant will be trapped, while the "fast" spider keeps watch on its edge.
Unless I overlooked something, this seems to work, but doesn't prove there isn't a lower possible speed sum.
For my analysis, I will assume that all we get to specify is the sum of the speeds of the spiders and that the sum we specify must work for any possible assignment of that total speed to the spiders where each spider must be given a non-zero speed.
It wasn't asked, but first lets take a look at the case of 4 spiders. With 4, any positive sum will work. If each spider has speed ε, the spiders can first move to each of the 4 corners of a single square face A. At that point, either the ant is already on an edge between two of the spiders and is therefore already trapped and doomed, or else it's on one of the edges of the face opposite that square, face B, or one of the edges connecting face A and B. If it's on face B or one of the connecting edges, the spiders can then each move along each of the connecting edges at the same time until they reach face B, at which point the ant is now trapped between two of the spiders who can now collapse on the ant, or was already dumbly caught as they swept from A to B.
Two Spiders: An Upper Bound of 2
It should be obvious that if any single spider has a speed greater than 1, then it doesn't matter how fast the other spiders are, that single spider can just head directly toward the ant and will eventually catch it.
So, if we specify a sum of 2 + ε for two spiders, by the pigeonhole principle, we're guaranteed to get at least one spider with speed greater than 1 and can necessarily catch the ant without any further strategy considered.
Edit: This bound is refined slightly further by Situation 3 of this answer. It shows that to catch the ant, it is sufficient to have just 1 spider that is at least as fast as the ant. Therefore, the upper bound can be refined from 2 + ε, to just 2.
Two Spiders: a Lower Bound of 2
Situation 1 of this answer shows that if neither spider has at least a speed of 1, then the ant can evade forever. So, to guarantee that at least 1 spider has a speed of at least 1, we must choose a total speed of 2. Anything less than 2 i.e. 2 - ε, and the spider speeds could be assigned at v1=1-ε/2 v2=1-ε/2, and they would be unable to catch the ant.
Two Spiders: Minimal Total Speed of 2
Since we've shown both that 2 is a sufficient total speed, and that anything less is insufficient, 2 is the minimal total speed that will allow the 2 spiders to catch the ant no matter how that speed is distributed between them.
Three Spiders: an Upper Bound of 1
For 3 ants, if we specify a total speed of 1 + 2/3 + ε, then we are guaranteed to either have 1 spider with speed greater than 1 which can catch the ant on its own, or we will have at least 2 spiders with speed at least 1/3, at which point, the spiders can employ the strategy laid out in this answer.
Edit: The three spiders case can be refined down. Based on this answer and one of its comments, if at least 1 spider has a speed of at least 1/3, the ant can be caught no matter how slow the other 2 spiders are. But to ensure we have at least 1 spider with speed 1/3, we'll need to specify a total speed sum of 1 so that by the pigeonhole principle we'll have at least 1 spider of speed 1/3 or greater and can use that strategy.
Here is a strategy giving an upper bound of exactly 1 for the sum for the 3 spider case.
If one spider has speed 1/3 and the others are arbitrarily slow, say speed ε, then the spiders can still catch the ant.
As explained in another solution, one spider can guard a complete edge including its 2 ends. Whenever the ant is on a square adjacent to the guarded edge, the spider maps the 3 other edges onto the guarded edge. It can mirror the movement of the ant with a speed of 1/3. If the ant attempts to cross one end of the guarded edge, it will meet the spider. In effect, the guarded edge is off-limits for the ant.
The strategy for the 2 other spiders is to place themselves on the two vertices opposite to the guarded edge. This cuts the cube into 2 H-shaped regions and one edge between the spiders. If the ant is between the slow spiders then it is doomed. If not, the spiders can slowly crawl along the bars of the H towards the ant and eventually catch it.
What it means for the upper bound is that there is a strategy for a total speed of 1/3+ε. If the attribution of the speeds is not under our control, but guaranteed non-zero, then we need a total speed of exactly 1. This guarantees that one spider has speed 1/3 or better and the others have a non-zero speed.
And there is a strategy for two spiders, one with speed exactly 1 and one with speed ε.
A spider with speed 1 can guard 3 adjacent edges up to the end.
The spider sits at a corner. As soon as the ant is on an edge on the way to one of the 3 adjacent corners, the spider moves to that corner. If the ant tries to reach that corner it meets the spider. If the ant turns back, the spider has the time to return to its base corner.
Removing these 3 edges and 4 corners has the effect of removing all loops from the alowed region. The remaining edges form a simple graph. It is 3 Y shapes connected by the bases. In this case the ant has no escape possibility, the slow spider just needs to move towards the ant to catch it eventually.
So with 2 spiders or more, if one spider has speed 1 then they can catch the ant. If you do not choose the spider speeds, you need a total speed of 2 to guarantee a spider has speed 1.
It has been shown that with a total speed <2 the ant can sometimes evade the spiders. So 2 is the actual limit from where the spiders are guaranteed to win.