18
$\begingroup$

The problem:

Three scorpions are chasing a single ant on the edgegraph of a cube. The scorpions have the same speed ($v$), while the ant is $3$ times as fast ($3v$). They can move in any direction and instantly turn around. Additionally, the scorpions are dumb, meaning that they always go after the ant on the shortest possible path.

Three scoprions chasing ant ant on a cube

The scoprions and the ant can be thought of as a point, they have no volume.

They can be thought of as points

And the edges of the cube can be thought of as a planar graph, with all sidelengths being $1$.

The cube can be thought of as a graph with sidelengths 1

Question: Is there a strategy the ant can use to forever avoid the scorpions? In what positions can the ant accomplish that?

My attempt:

There is definitely a position where the scorpions win, and that's when they can corner the ant:

Ant cornered

Also, if the scoprions are $1+ \frac{1}{3}$ edge away from the corner where the ant sits, they can still get into the position drawn above to catch the ant.

Otherwise it gets really complicated and messy. It seems though that if the ant just goes as far away as possible from the scoprions at every moment, they won't be able to catch it. Obviously this would need a mathematical proof though.

I tried to write up the distance function between scorpions and the ant, but since even if $1$ scoprion touches the ant, it's over, we have to take the $\min$ of them.

First of all, this is the area they can move in:

$$C = \{(x_1,x_2,x_3) \in \Bbb{R}^3| \\ |(i_1,i_2,i_3) \in \{1,2,3\}, x_{i_1} \in \{0,1\}, x_{i_2} \in \{0,1\}, x_{i_3} \in [0,1]\}$$

And this is the distance from the ant to the closest scoprion, which we always want to maximize as the ant:

$$d_{\text{closest scorpion}}(x \in C) = \\ = \min (d_{\text{scoprion 1}}(x,s_1),d_{\text{scoprion 2}}(x,s_2),d_{\text{scoprion 3}}(x,s_3))$$

And

$$d_{\text{scoprion i}}(x,s_i) = \text{Metropolis distance}(x,s_i)$$

where

$$\text{Metropolis distance}(x,y) = |x_1-y_1|+|x_2-y_2|+|x_3-y_3|$$

Maximizing $d_{\text{closest scorpion}}$ is tough, because neither $\min$ nor the $\text{Metropolis distance}$ can be differentiated. But if that's done, we could look at the gradient vector to help the ant decide where to go.

I'm kinda stuck at this point, so any help would be appreciated!

$\endgroup$
  • $\begingroup$ What's the source of the problem? This information could help in gauging the intended level of difficulty. $\endgroup$ – Blue Apr 17 at 9:09
  • $\begingroup$ My university "Graphs and Algorithms" teacher. I'm in the last semester of my mathematics major. Note: This was given to us as a puzzle, not as a homework. :) $\endgroup$ – Daniel P Apr 17 at 9:11
  • 1
    $\begingroup$ There are definitely positions where the ant can be forever safe—if all three scorpions are on its edge on the same side of it, for example. If the three scorpions and the ant are all at distance 2 from one another (occupying four corners), then, depending on which directions the scorpions choose to start their pursuit, it's quite likely that the ant can lure them into the above position. $\endgroup$ – Greg Martin Apr 17 at 9:13
  • $\begingroup$ @orlp They can't move on faces, just edges. If all are on the same side, they have to go around to meet each other. $\endgroup$ – Daniel P Apr 17 at 9:29
  • 3
    $\begingroup$ I have seen a variant of this puzzle where the scorpions are smart, in which case they can catch the ant. cs.cmu.edu/puzzle/puzzle18.html $\endgroup$ – Mike Earnest Apr 17 at 14:52
4
+50
$\begingroup$

The distance you proposed, called the Manhattan distance or $L_{1}$ distance:

$$ d_{L_{1}}(x, y) = \sum_{i=1}^{3} |x_{i} - y_{i}| $$

is not the distance the ant needs, to walk from point $x$ to point $y$ on the cube. Distance the ant needs to walk $d_{G}(x,y)$ is the length of the shortest path between $x$ and $y$, for example if $x=(0.1, 0, 0)$ and $y= (0.2, 0, 1)$: $$ d_{G}(x,y) = 1.3 \neq 1.1 = d_{L_{1}}(x,y). $$

Ant starts on some edge $v_{1}v_{2}$ of the cube or graph $G$, let's say $\delta \geq 0$ away from the vertex $v_{1}$ and $1 - \delta$ from the vertex $v_{2}$. Ant can wait for the scorpions, or it can move to one of the four edges nearby. You can use the line graph $L(G)$ of the graph $G$ drawn in red in the Figure below to derive a state space:

Line graph of G

Each red vertex of $L(G)$ is an edge in $G$ and has 4 neighbors. If $d_{G}(S, v_{1}) \leq \frac{\delta}{3}$, for some scorpion $S$, then ant can not cross $v_{1}$ and these two edges (incident to $v_{1}$) are not accessible to the ant and corresponding two vertices are not present in the state space. Similar for vertex $v_{2}$ if $d_{G}(S, v_{2}) \leq \frac{1 - \delta}{3}$.

To show your intuition:

"Otherwise it gets really complicated and messy. It seems though that if the ant just goes as far away as possible from the scoprions at every moment, they won't be able to catch it. Obviously this would need a mathematical proof though."

is true, you could try do case analysis of how state space depends on the initial positions. Positions that make state space a tree, means that scorpions win. Otherwise state space has cycles and ant can just walk endlessly in a cycle. (Line graph of a cycle is a cycle, so a cycle in state space corresponds to a cycle on the cube.)

$\endgroup$
1
$\begingroup$

Let's consider starting positions to be at the corners.

As you already found, if the S's start at the positions cornering A, then A has no hope.

Ant_Scorpion_1

On the contrary, we can always individuate a face of the cube with max $2$ S and an opposite face with max $1$ S , with A being at most one non-blocked edge away from the face with less scorpions.
At $t=1/3$, we can still associate the S positions to the nearest corners, so same as the original configuration, and A is quick enough to position herself on the less crowded face, as far as possible from the scorpion there.

If the Ant plays wisely that strategy she can always survive.

$\endgroup$
0
$\begingroup$

We prove a stronger statement: we find all positions where the ant can survive indefinitely, and furthermore show that if the scorpions are “smart” they can kill the ant regardless of initial position.

Suppose that the ant can safely reach two different vertices of the cube. (Safely means there exists a path from the ant to the vertex such that no scorpion can intercept this path regardless of their movements.

Note: Suppose the ant can only ever reach one vertex. Then the scorpions will move towards the ant and the ant will get cornered and die on that vertex.

Now suppose the ant can safely reach vertices A and B, with A and B being the closest safe vertices to the ant (pick randomly if there is a tie). The ant could possibly currently be at A or B. I prove that if it can reach two vertices at any time step, then it will always be able to guarantee that it can reach two vertices a finite time in the future, provided the scorpions are dumb.

Suppose that if the ant raced straight for the closest safe vertex A, it would not be able to reach any other vertex. That means that the three vertices around A, one of which is B and the other two called X and Y, each have a scorpion within distance 1/3. Thus if the ant raced for B, since B is the next closest safe vertex, by definition of “safe”, the ant does not pass through A to reach B, because the scorpion within 1/3 of B cannot reach B before the ant. Therefore the ant is on the line segment joining A and B with no scorpions on this line segment. Thus the ant can race to B. and The other two vertices connected to B are called P and Q, which are not X, Y, A or B, where P is adjacent to X and Q is adjacent to Y.

There is exactly one position in which two scorpions can prevent the ant from reaching any of P, Q, X and Y. This is when the scorpions mirror the movements of the ant along AB along the middle thirds of the lines PX and QY. This actually outlines a strategy for smart scorpions to win, in which the ant is confined to the five edges AB, AX, AY, BP and BQ, which forms a tree allowing the third scorpion to kill the ant regardless of how slow the third scorpion is (and in fact, this is the only way for the scorpions to win, proven in the same way).

However, for dumb scorpions which travel directly towards the ant, even if they are in the perfect positions to catch the ant, then they fail by moving in the shortest path towards the ant. The ant can simply wait until one of P, X, Q and Y is reachable, and to A or B, whichever is adjacent (smart scorpions would hold their perfect positions). At this point the ant can now safely reach two vertices, one of which is not A or B. The ant can now repeat this strategy infinitely.

I’m on mobile right now so I can’t currently provide diagrams; they will be added soon.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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