14
$\begingroup$

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?

enter image description here

Improve this question
$\endgroup$
23
  • 1
    $\begingroup$ Does "any starting positions" mean either: 1) I put the spiders first, the ant then be anywhere; or 2) the ant and the spiders are all "anywhere"? $\endgroup$
    – iBug
    Commented Sep 15, 2021 at 14:43
  • 1
    $\begingroup$ @iBug it's 2. "Any starting positions" means: no matter where the spiders and the ant are in the beginning. $\endgroup$
    – Eric
    Commented Sep 15, 2021 at 14:49
  • 1
    $\begingroup$ Can one turn around at any time or can turns be made only when reaching a vertex (junction)? $\endgroup$
    – iBug
    Commented Sep 15, 2021 at 15:00
  • 3
    $\begingroup$ I strongly suspect that even two spiders of speed 1 can't catch the ant. I thought I had a proof but it doesn't quite work out. So I don't think the spiders need to transfer speed, as long as neither is faster than the ant they need a third one to catch the ant. $\endgroup$
    – quarague
    Commented Sep 16, 2021 at 7:25
  • 2
    $\begingroup$ @Shufflepants No, that's not what I intended. I only meant distribution of initial positions. Sorry for misreading your question $\endgroup$
    – Eric
    Commented Sep 17, 2021 at 19:26

7 Answers 7

Reset to default
9
$\begingroup$

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:

  1. Both spiders are slower than the ant: The ant can avoid forever
  2. At least one spider is as fast as the ant: The spiders can catch the ant
  3. 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:

  1. Start at a corner that does not contain a spider
  2. 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)
  3. Travel to that corner
  4. 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.

Improve this answer
$\endgroup$
7
  • $\begingroup$ Do the spiders catch the ant if both move at the speed of 1? $\endgroup$
    – Eric
    Commented Sep 17, 2021 at 1:03
  • $\begingroup$ No the ant can always reach its target corner before a same speed spider because the target corner is distance 1 from the ant and distance greater than one from all spiders. $\endgroup$
    – Kyle Parsons
    Commented Sep 17, 2021 at 2:57
  • $\begingroup$ @KyleParsons suppose the ant is in bottom left corner, and one spider is at the top corner. The other spider is at the bottom back corner, opposite of the ant. The top spider basically closes one corner for the ant to move to, while the other spider mirrors the ant movement. Then the ant is caught. $\endgroup$
    – justhalf
    Commented Sep 17, 2021 at 4:43
  • 1
    $\begingroup$ Oh, but that's only applicable when the starting position allows the spiders to be positioned like that (or we need to prove that the ant can always avoid that position) $\endgroup$
    – justhalf
    Commented Sep 17, 2021 at 4:51
  • $\begingroup$ @justhalf This is the scenario where it makes a big difference whether the spiders have speed strictly smaller than one or equal to one. If the speed is strictly smaller than one, in your scenario the spider would not block either vertex because the ant could get there first. If the spider has speed 1 it can block 2 vertices the way you described. $\endgroup$
    – quarague
    Commented Sep 17, 2021 at 10:23
13
$\begingroup$

Not a definite answer but I narrowed it down to 2 possibilities.

It's either

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

1

Because

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

Improve this answer
$\endgroup$
9
  • 1
    $\begingroup$ I thought about something like your proof for speed below 1 but it doesn't quite work. Ant sits at bottom front left vertex, Spider 1 sits at top front left vertex. Spider 2 sits at bottom back right vertex. Spider 1 starts moving towards the ant. Ant can head for either bottom back left or bottom front right. Once the ant made its decision Spider 2 also heads towards that vertex. If the ant is faster than spider 2 it will get there first but even then spider 2 will get quite close to the ant. So it is not quite clear that the ant will get away. $\endgroup$
    – quarague
    Commented Sep 16, 2021 at 14:36
  • 2
    $\begingroup$ @quarague it doesn't matter how close the spider can come. Because no matter what the state is. Once the ant is in a corner there always a corner he can run to before any of the spiders. $\endgroup$
    – Ivo
    Commented Sep 16, 2021 at 14:49
  • 2
    $\begingroup$ This is actually a complete solution to the two-spider case. You have shown that if the combined speed is more than 1, then there is a speed distribution which can catch the ant, namely, (1 + e/2, e/2). If the combined speed is 1 or less, then you either have two spiders which are less than 1, or one spider of speed 1 and the other of speed zero. In the first case, you gave a strategy, and in the second case, the fly just plays ring-around-the-rosie on some face not including the stopped spider. $\endgroup$
    – Mike Earnest
    Commented Sep 16, 2021 at 15:21
  • 1
    $\begingroup$ You start out with a state where both spiders are at least distance 1 away from the ant. After a bit of running around the spiders are much closer than that. To get a full proof you need to show you can get back to a state where both spiders are at least distance 1 away. $\endgroup$
    – quarague
    Commented Sep 16, 2021 at 17:10
  • 1
    $\begingroup$ @quarague I realized later that my explanation about waiting for them to be 1 edge away is completely unnecesary. Just make sure to get to a corner and after that it doesn't matter at all where the spiders are or how close they are because there's 3 possible directions and there's always at least 1 direction the ant can run to before any of the other 2 spiders. After that you are in the initial state and can repeat this forever $\endgroup$
    – Ivo
    Commented Sep 17, 2021 at 7:57
8
$\begingroup$

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

Improve this answer
$\endgroup$
5
  • 1
    $\begingroup$ Does that answer apply? I was under the impression that the speeds may be assigned in a "worst case scenario" for whatever is most beneficial to the ant. What if 2/3 + ε is distributed as: v1=2/3-ε, v2=ε, v3=ε? I'm not sure that works anymore since the two ε spiders are essentially non-moving walls, and 2/3 isn't fast enough on its own to corner the ant I don't think as there will still be a connected loop no matter where you move your two "walls" to. $\endgroup$
    – Shufflepants
    Commented Sep 16, 2021 at 14:21
  • 2
    $\begingroup$ I'm operating under the assumption of worst case starting positions, and either best case speed assignment or a consistent speed assignment that works for all starting positions $\endgroup$
    – StephenTG
    Commented Sep 16, 2021 at 14:28
  • $\begingroup$ Op confirmed that the catch plan must work for any possible distribution. Which means that this upper bound is insufficient or insufficiently proved. If you specify a total of 2/3 + ε, then it has to work for v1=ε, v2=ε, v3=2/3-ε as well. Which this does not prove and I suspect there is no strategy that works for that total/distribution. $\endgroup$
    – Shufflepants
    Commented Sep 17, 2021 at 16:10
  • $\begingroup$ Actually, another answer shows that v1=ε v2=ε v3=2/3-ε would indeed work, but you also have to account for v1=2/9, v2=2/9, v3=2/9+ε. Can the ant be caught in that scenario? $\endgroup$
    – Shufflepants
    Commented Sep 17, 2021 at 19:20
  • 1
    $\begingroup$ @Shufflepants I'm sorry I misunderstood your question in the comment. I thought you were asking about distributions of initial position. My answer there only meant distribution of positions. $\endgroup$
    – Eric
    Commented Sep 17, 2021 at 19:24
6
$\begingroup$

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:

enter image description here

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.

Improve this answer
$\endgroup$
4
  • 2
    $\begingroup$ I think the fast spider can get away with the slower speed of 1/3. The ant cannot get from one end of the fast spider's edge to the other in less than 3 units of time, so the fast spider needs at most 1/3 speed to guard both end points of its edge. $\endgroup$
    – Jaap Scherphuis
    Commented Sep 17, 2021 at 11:59
  • $\begingroup$ You are correct, in my mind the spider only started moving once the ant is at one of the opposite vertices, but it can start moving earlier $\endgroup$
    – Pepper
    Commented Sep 17, 2021 at 12:30
  • $\begingroup$ But what's the strategy if the speed is distributed as v1=1/6, v2=1/6, v3=ε? Your specified total speed has to work for all possible distributions. $\endgroup$
    – Shufflepants
    Commented Sep 17, 2021 at 16:13
  • $\begingroup$ @Shufflepants That is not how I understand the question (and doesn't seem to be what OP intended either, looking at comments on the question itself) $\endgroup$
    – Pepper
    Commented Sep 20, 2021 at 7:02
4
$\begingroup$

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.

Four Spiders

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.

Improve this answer
$\endgroup$
3
$\begingroup$

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.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Oh, well, I just saw that Pepper gave essentially the same strategy yesterday for the 3 spider case. $\endgroup$
    – Florian F
    Commented Sep 18, 2021 at 14:03
  • $\begingroup$ Actually Pepper gave an answer of 1/2+e and yours is 1/3+e. $\endgroup$
    – JS1
    Commented Sep 18, 2021 at 19:49
  • $\begingroup$ Yes, but in the comments they correct the value. $\endgroup$
    – Florian F
    Commented Sep 19, 2021 at 18:43
-1
$\begingroup$

To start with, there's an intuitive upper bound of

1 + ε, where ε is any positive real number (think about your calculus course)

Improve this answer
$\endgroup$
5
  • 2
    $\begingroup$ Could you expand on the reasoning for intuition? $\endgroup$
    – bobble
    Commented Sep 15, 2021 at 15:45
  • 1
    $\begingroup$ (... so how does this contribute toward a solution? As this stands, it's Not an Answer, not even a partial one. Having fragmentary thoughts on aspects of a puzzle might be comment-worthy, but you probably want at least a germ of an idea that seems to lead forward before you should post as even a partial answer. Here, as an "upper bound" that is literally unconstrained, this provides no information whatsoever.) $\endgroup$
    – Rubio ♦
    Commented Sep 15, 2021 at 16:18
  • 1
    $\begingroup$ @Rubio "Upper bound" literally means "here's my valid answer, so any solution should not go over this". It is an answer, though. $\endgroup$
    – iBug
    Commented Sep 15, 2021 at 17:44
  • 4
    $\begingroup$ You should add a sentence explaining (even though it's simple) how that upper bound guarantees the spiders can catch the ant. $\endgroup$
    – Rob Watts
    Commented Sep 15, 2021 at 18:34
  • 2
    $\begingroup$ A proper answer (almost always) requires explanation. $\endgroup$
    – Avi
    Commented Sep 16, 2021 at 22:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.