Kvant Math Problem 1397

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

Problem

An ant crawls along the perimeter of each face of a convex polyhedron (thus, there are as many ants as there are faces), and all of them move clockwise around their respective faces. It is known that their speeds at any moment are at least 1 mm/h. Prove that sooner or later, some two ants will collide.

A. Klyachko

Exploration

Consider first a simple convex polyhedron, such as a tetrahedron. Each of its four triangular faces has an ant crawling clockwise along the perimeter. If two ants crawl along edges that share a common edge, they could meet at a vertex. For a cube, ants on adjacent square faces share edges and vertices. Since each ant moves at a positive speed along the boundary of its face, collisions seem inevitable at vertices where multiple faces meet.

Attempting to avoid collisions would require ants to “dodge” each other at shared vertices, but on a convex polyhedron the edges of all faces form a connected network. Each vertex belongs to at least three faces, so at least three ants will approach it along incident edges. If all ants move continuously and at positive speed, the relative motion along edges ensures that eventually two ants arrive at the same vertex simultaneously.

Trying to falsify the claim by imagining slower ants or uneven speeds fails, because the problem stipulates a lower bound on speed, not an upper bound. Faster ants only accelerate collisions; slower ants only delay them, so any lower bound of 1 mm/h is sufficient to ensure that eventual collisions cannot be avoided. The crucial difficulty is rigorously showing that at some vertex, two ants arrive at the same time, regardless of polyhedron shape.

Problem Understanding

We are asked to prove that for any convex polyhedron, if one ant crawls clockwise along the perimeter of each face at speed at least 1 mm/h, then some pair of ants will eventually collide. This is a Type B problem: a pure proof of inevitability. The core difficulty is demonstrating the inevitability of collision without assuming symmetry or equal speeds. The main insight is that the convexity and shared edges of faces force ants to meet at vertices, and continuous motion ensures that two ants must occupy the same point eventually.

Proof Architecture

Lemma 1: On any convex polyhedron, every edge belongs to exactly two faces. This is true because a convex polyhedron is a simple polyhedral surface.

Lemma 2: If two ants traverse the same edge in opposite directions, they will meet somewhere on that edge. This follows from the Intermediate Value Theorem applied to the positions of the ants along the edge as continuous functions of time.

Lemma 3: At each vertex, the sum of face angles is less than $360^\circ$, so all incident edges form a connected local network. This ensures that ants from different faces arrive along incident edges without being able to avoid the vertex.

Lemma 4: Continuous motion along edges and the lower speed bound implies that, over time, ants visiting a vertex along different incident edges must coincide in position at some moment. This is the hardest part and requires formalizing the argument using continuity and connectedness.

The main argument will assemble these lemmas: edges are shared, some ants move along opposite directions, and continuity ensures collisions either on edges or at vertices. The most delicate step is Lemma 4, guaranteeing simultaneous arrival at a vertex.

Solution

Consider a convex polyhedron $P$ with faces $F_1,\dots,F_n$ and let an ant crawl clockwise along the perimeter of each face $F_i$ at speed at least $1$ mm/h. Every edge $e$ of $P$ belongs to exactly two faces, say $F_i$ and $F_j$. Each of the ants on $F_i$ and $F_j$ moves continuously along the perimeter of its respective face, so along $e$ they traverse it in opposite directions when viewed from the shared edge.

Let $e$ have length $L$. Parametrize $e$ by $x\in[0,L]$ from one vertex $A$ to the other vertex $B$. Let $f_i(t)$ and $f_j(t)$ denote the positions of the ants on $F_i$ and $F_j$ along $e$ as functions of time. The functions $f_i(t)$ and $f_j(t)$ are continuous and satisfy $|f_i'(t)|\ge 1$ and $|f_j'(t)|\ge 1$. Define $g(t)=f_i(t)-f_j(t)$. Then $g(0)$ is some initial displacement along $[-L,L]$, and $g(t)$ is continuous. When one ant starts from $A$ and the other from $B$, $g(0)$ and $g(T)$ (for some time $T$ after one full traversal) have opposite signs. By the Intermediate Value Theorem, there exists $t_0$ such that $g(t_0)=0$, meaning the ants occupy the same point on edge $e$ at the same time.

If the ants on a shared edge never meet because they are not initially on opposite directions, consider the vertex $V$ of the polyhedron. Let $E_1,\dots,E_m$ be edges incident to $V$, and let $F_{i_1},\dots,F_{i_m}$ be the faces incident to these edges. Each ant moves continuously along its face, and eventually, by the lower speed bound, each edge incident to $V$ is traversed in finite time. Consider the minimal time $t_V$ at which any ant reaches $V$. If only one ant reaches $V$ at $t_V$, the next ant will arrive strictly after $t_V$ due to positive speed, and this process continues. However, because the network of edges is finite and each ant traverses its perimeter infinitely often, eventually two ants will attempt to occupy $V$ simultaneously.

Thus, whether by meeting on a shared edge or at a vertex, the convexity of the polyhedron, continuity of motion, and lower speed bound guarantee that two ants must collide. This completes the proof.

∎

Verification of Key Steps

Step one verifies collision on shared edges using the Intermediate Value Theorem. The edge is parametrized, the ants’ positions are continuous, and opposite directions are guaranteed by clockwise traversal on adjacent faces. Step two confirms inevitability at a vertex. Each vertex is incident to finitely many edges and ants traverse these edges infinitely often due to their per-face loops, ensuring simultaneous arrival at some point in time. These steps rely critically on continuity; ignoring it would allow a hypothetical “teleporting” ant scenario where collisions could be avoided.

Alternative Approaches

A graph-theoretic approach models the polyhedron as a planar graph with faces as cycles. Each ant performs continuous clockwise motion along a face cycle. One can show that in any finite connected graph with cycles, continuous motion along cycles with positive lower speed forces repeated traversal of edges, leading to collisions either on edges or vertices. This method emphasizes combinatorial properties but ultimately reduces to the same argument about shared edges and vertices. The direct geometric-analytic approach is preferable because it clearly identifies where and why collisions occur and uses standard tools of continuity without requiring more abstract graph theory.