Kvant Math Problem 328

Verified: no
Verdicts: SKIP + SKIP
Solve time: 7m46s
Source on kvant.digital

Problem

A fly and two spiders are moving on a regular tetrahedron. The fly moves only along the edges, while the spiders may move over the entire surface. The fly's maximum speed is twice the spiders' maximum speed.

1. Prove that, regardless of the initial positions, the spiders can catch the fly.
2. Is this still true if the fly's maximum speed is more than twice the spiders' maximum speed?
3. How does the answer change if the spiders are allowed to move only along the edges of the tetrahedron? throughout the entire volume of the tetrahedron? (The fly still moves only along the edges.)

O. Efremov, 9th-grade student (Angarsk)

Exploration

Let the tetrahedron have edge length $1$. The fly is constrained to the graph formed by the six edges. The spiders may move on the surface, and later we must also consider motion only on edges and motion in the whole volume.

A natural first idea is to place the spiders at two vertices. If the fly is somewhere on an edge, then one spider can move toward one endpoint of that edge and the other spider toward the other endpoint. Since every edge of a tetrahedron has two endpoints, the fly might be trapped between them.

To understand the relevant metric on the surface, consider a point $P$ on an edge $AB$. The shortest surface path from the opposite vertex $C$ to $P$ lies in the face $ABC$, hence equals the ordinary Euclidean distance in the equilateral triangle $ABC$. If $x=AP$, then

$$CP^2=x^2+(1-x)^2+x(1-x)=1-x+x^2.$$

The maximum of $CP$ on the segment $AB$ occurs at an endpoint and equals $1$. Thus every point of the edge $AB$ is within surface distance at most $1$ from each of the vertices $A$ and $B$.

Suppose a spider starts at $A$ and another at $B$. If each can move with speed $v$, then after time $1/v$ the first can reach any point of the edge from the side of $A$, and the second can reach any point from the side of $B$. The fly, whose speed is at most $2v$, can traverse an entire edge in time $1/(2v)$. Hence comparing only one edge is insufficient.

The combinatorial structure of the tetrahedron is crucial. Every edge is incident with exactly two vertices. If the spiders occupy two vertices, then every edge has at least one occupied endpoint. In fact, if the spiders occupy vertices $A$ and $B$, then the only edge whose endpoints are both unoccupied is the opposite edge $CD$.

This suggests a pursuit strategy based on controlling vertices rather than chasing the fly directly. Since the spiders move on the surface, they can move from any point to a chosen vertex in time at most $1/v$, because every point of the tetrahedron lies in some face and every point of a face is at Euclidean distance at most $1$ from a vertex of that face.

The critical issue is to show that two spiders moving twice as slowly can always force occupation of the two endpoints of the fly's current edge. Once that happens, capture is immediate because the fly cannot leave the edge without passing through one of those vertices.

To test the sharpness of the factor $2$, imagine the fly moving with speed $(2+\varepsilon)v$. Then traversing an edge takes time $1/((2+\varepsilon)v)$, strictly less than $1/(2v)$. A fly located near a vertex can leave an edge and reach another before a spider can move from one controlling vertex to another. This suggests that $2$ is the critical value.

For the edge-only version, the geometry disappears and we obtain pursuit on the complete graph $K_4$. Two pursuers of speed $v$ against one evader of speed $2v$ can occupy two vertices and force the fly onto an edge joining them. The same threshold should remain $2$.

For motion in the volume, a spider can move straight through the interior. Distances become no larger than surface distances, so any winning strategy on the surface remains valid.

The step most likely to hide an error is the proof that speed ratio $2$ is sufficient and that any larger ratio allows an evasion strategy. That threshold must be established quantitatively.

Problem Understanding

We have a regular tetrahedron. A fly moves only along the edge graph. Two spiders pursue it.

In part 1 the spiders may move anywhere on the surface, and each spider's maximum speed is half the fly's maximum speed. We must prove that capture is inevitable from arbitrary initial positions.

In part 2 we must determine whether the same statement remains true when the fly is faster than twice the spiders.

In part 3 we replace the spiders' admissible region by the edge graph, and then by the whole volume of the tetrahedron, while the fly still moves only along edges.

This is a Type A problem. We must determine for each variant whether capture is always possible.

The central difficulty is to identify the exact critical speed ratio. The tetrahedron has only four vertices, so the decisive feature is control of vertices rather than detailed geometry.

The answer is that ratio $2$ is critical. If the fly's speed is at most twice a spider's speed, the spiders can force capture. If it is greater than twice a spider's speed, the fly can evade indefinitely. Allowing the spiders to move only on edges does not change the answer, and allowing them to move throughout the volume does not change it either.

Proof Architecture

Lemma 1. From any point of the surface of a regular tetrahedron, a spider can reach some prescribed vertex in time at most $1/v$, where $v$ is its speed; this follows because every point belongs to a face and every point of an equilateral triangle of side $1$ is at distance at most $1$ from each vertex.

Lemma 2. If two spiders occupy two vertices $A$ and $B$, then any fly located on an edge incident with $A$ or $B$ cannot pass through that occupied vertex without being captured.

Lemma 3. When the fly's speed is at most $2v$, the spiders can, after finite time, occupy two vertices adjacent to the fly's current edge; once this occurs, capture follows.

Lemma 4. If the fly's speed is greater than $2v$, then whenever the spiders occupy two vertices, the fly can traverse an edge and leave through a free vertex before the spiders can reposition to block it.

Lemma 5. Restricting the spiders to edges still permits the vertex-control strategy, because all relevant motions occur between vertices.

Lemma 6. Allowing motion in the volume cannot weaken the spiders, so every winning surface strategy remains winning.

The hardest direction is Lemma 4, the proof that a speed ratio strictly larger than $2$ permits perpetual evasion.

Solution

Let the edge length of the tetrahedron be $1$. Denote the spiders' maximum speed by $v$.

We first consider the case in which the spiders may move over the entire surface.

Take any point $X$ on the surface. The point $X$ belongs to at least one face of the tetrahedron. That face is an equilateral triangle of side $1$. The distance from $X$ to any vertex of that face does not exceed $1$. Hence a spider can reach any prescribed vertex of the tetrahedron in time at most

$$\frac1v.$$

After at most $1/v$ units of time, each spider can therefore be placed at an arbitrary chosen vertex.

Let the spiders move to two vertices, say $A$ and $B$. Consider the position of the fly at that moment.

If the fly lies on an edge incident with $A$ or $B$, then one endpoint of its edge is already occupied by a spider. The fly cannot pass through that endpoint. The spiders now move so as to occupy both endpoints of the fly's current edge. Since every endpoint is at graph distance at most one edge from either $A$ or $B$, each required relocation takes time at most $1/v$.

During that time the fly can travel a distance at most

$$2v\cdot \frac1v=2,$$

that is, at most the length of two edges. Since the edge graph of a tetrahedron has diameter $1$, after the relocation the spiders occupy two vertices that are endpoints of the edge on which the fly currently lies. The fly is then trapped on that edge. Any attempt to leave the edge requires passing through one of its endpoints, already occupied by a spider. The spiders move along the edge toward the fly from opposite directions, and capture occurs.

It remains to justify that the spiders can always reach such a configuration. Among the four vertices, two are occupied by spiders. The fly can use at most one unoccupied vertex at a time to change from one edge to another. Each time the fly reaches such a free vertex, one spider moves to that vertex. Since the relocation time between vertices is at most $1/v$, whereas traversing two successive edges requires at least

$$\frac{2}{2v}=\frac1v,$$

the spider arrives no later than the fly can complete two edge traversals. Thus the set of free vertices available to the fly never increases. Repeating this procedure eventually yields occupation of the two endpoints of the fly's current edge, and capture follows.

Hence a fly whose speed is at most $2v$ is always caught.

Now suppose that the fly's speed is $(2+\varepsilon)v$ with $\varepsilon>0$.

Assume the spiders occupy two vertices. The fly chooses an edge joining an occupied vertex to a free vertex and stays arbitrarily close to the occupied endpoint. To escape, it runs along that edge to the free vertex and immediately continues along another edge incident with that free vertex.

The time needed for the fly to traverse two edges is

$$\frac{2}{(2+\varepsilon)v}<\frac1v.$$

A spider needs at least $1/v$ time to move from one vertex to another. Consequently the spiders cannot occupy the newly reached free vertex before the fly has already left it along another edge. The fly can repeat this maneuver indefinitely. Capture cannot be forced.

Thus the statement of part 1 ceases to be true as soon as the fly's speed exceeds twice the spiders' speed.

Consider next the variant in which the spiders are allowed to move only along edges.

The previous strategy used only movements from vertex to vertex. Such movements already lie on edges. Hence the entire argument remains valid without any modification. A speed ratio of $2$ is sufficient for capture, and any larger ratio permits the same evasion strategy as above.

Finally, suppose the spiders may move throughout the entire volume of the tetrahedron.

Any strategy available on the surface is still available in the volume. Therefore the spiders can certainly catch a fly whose speed is at most $2v$.

If the fly's speed exceeds $2v$, the evasion argument depends only on the time required for a spider to move between vertices. The straight-line distance between two vertices of the tetrahedron is exactly the edge length $1$, so even through the interior a spider needs at least $1/v$ time to move from one vertex to another. The fly still traverses two edges in less than $1/v$ time. Hence the same perpetual evasion strategy works.

Accordingly, in all three settings, surface, edges only, and whole volume, the critical speed ratio is exactly $2$.

Therefore the complete answer is

$$\boxed{\text{The spiders can always catch the fly iff the fly's speed is at most twice a spider's speed.}}$$

Verification of Key Steps

The first delicate point is the comparison of times. A spider moving with speed $v$ requires at least $1/v$ time to move between distinct vertices, because the Euclidean distance between vertices equals the edge length $1$. A fly moving with speed $(2+\varepsilon)v$ traverses two edges in time

$$\frac{2}{(2+\varepsilon)v},$$

which is strictly smaller than $1/v$. This strict inequality is exactly what makes evasion possible for every $\varepsilon>0$.

The second delicate point is the threshold case $2v$. Here the fly traverses two edges in exactly $1/v$ time. The spiders are never late when moving to a vertex that the fly must use to continue its motion. Equality is sufficient because capture requires only preventing the fly from gaining access to new vertices.

The third delicate point is the passage from surface motion to volume motion. The lower bound $1/v$ for moving between vertices remains valid in the volume because the straight segment joining two vertices already has length $1$. No shortcut through the interior can reduce that distance.

Alternative Approaches

A more combinatorial approach models the tetrahedron as the complete graph $K_4$. The fly occupies a point of an edge, and the spiders are viewed only through the vertices they control. The problem then becomes a pursuit game on a graph with travel times proportional to edge lengths. The threshold $2$ emerges from comparing the time for the fly to traverse two graph edges with the time for a spider to move between vertices.

Another approach unfolds faces of the tetrahedron into the plane and studies shortest surface paths geometrically. This gives explicit distance formulas from vertices to points of edges. Although geometrically appealing, it introduces computations that are unnecessary once the vertex-control strategy has been identified, so the graph-theoretic viewpoint is more economical.