Kvant Math Problem 724
Consider two turtles moving at the same speed but in different directions.
Verified: no
Verdicts: SKIP + SKIP
Solve time: 3m04s
Source on kvant.digital
Problem
Several turtles crawl across a plane, each moving at the same speed in magnitude but in different directions. Prove that, regardless of their initial positions, after some time they will occupy the vertices of a convex polygon.
V. V. Prasolov
Exploration
Consider two turtles moving at the same speed but in different directions. If we translate the coordinate system so one turtle is at the origin, the other moves along a straight line at a fixed velocity. Their positions form a line segment, which is trivially convex. Adding a third turtle introduces a triangular configuration. Each turtle moves linearly in its own direction at the same speed magnitude. Over time, the positions spread out, and any initial nonconvex arrangement appears to "straighten" as the turtles diverge along their vectors. For four or more turtles, one can imagine that initially collinear turtles might form nonconvex shapes temporarily, but as time progresses, no three turtles remain aligned unless their velocity vectors coincide, which is excluded. The most subtle step seems to be guaranteeing that for arbitrary initial positions and directions, no three turtles remain aligned in a way that prevents convexity.
Testing small configurations numerically, for three turtles starting at vertices of a nonconvex "V" shape with divergent velocities, one observes that eventually the triangle they form becomes convex because each vertex moves linearly away from the others, and no velocity vector can trap a turtle inside the evolving convex hull of the others. The likely crux is proving that the convex hull of the positions strictly expands over time until all turtles lie on its boundary.
Problem Understanding
The problem asks to show that if several turtles move in straight lines at equal speed but in different directions, then after some finite time their positions form the vertices of a convex polygon. The problem type is B, a pure proof, because it asks to prove an eventual configuration property. The core difficulty is establishing that no turtle can remain inside the convex hull of the others indefinitely, even for special initial arrangements. The key insight is that translating the system along the common speed magnitude allows one to view the positions in a moving frame where the convex hull expands until all turtles lie on its boundary, yielding a convex polygon.
Proof Architecture
Lemma 1. For any finite set of points moving linearly with distinct directions, the convex hull of their positions eventually stabilizes in the sense that no point remains strictly inside indefinitely. Sketch: linear trajectories with distinct directions prevent persistent interior confinement.
Lemma 2. If a point moves linearly outside the convex hull of a set, it will eventually lie on the convex hull boundary. Sketch: by considering the support lines of the convex hull, a point moving linearly in a direction not parallel to any hull edge eventually intersects the hull boundary.
Lemma 3. No three turtles remain collinear indefinitely unless their velocities are collinear. Sketch: linear independence of velocity directions prevents persistent alignment.
The hardest step is Lemma 1, ensuring that no turtle remains permanently inside the hull. This is where a careless argument could fail if one overlooks special velocity alignments or initial positions.
Solution
Let the turtles be points $T_1, T_2, \dots, T_n$ in the plane, with positions at time $t$ given by vectors $p_i(t) = p_i(0) + v_i t$, where $|v_i| = v$ for all $i$, and the directions of $v_i$ are distinct. Consider the convex hull $H(t)$ of the set ${p_1(t), \dots, p_n(t)}$.
First, observe that if a turtle $T_i$ lies strictly inside $H(t)$, then its velocity vector $v_i$ cannot be parallel to any edge of $H(t)$ that could trap it, because all $v_i$ have distinct directions. Therefore, the distance from $T_i$ to the boundary of $H(t)$ along its velocity vector is strictly positive. As $t$ increases, $T_i$ moves in the plane along $v_i$, and eventually it reaches a point on the boundary of the convex hull. Consequently, no turtle remains permanently inside $H(t)$.
Next, consider the possibility of collinear points. Suppose three turtles $T_i, T_j, T_k$ are collinear at some time. Their positions are $p_i(t), p_j(t), p_k(t)$. Since their velocities are in distinct directions, the lines connecting their positions rotate over time. The linear independence of the velocities ensures that any initial alignment is temporary; eventually the three points are noncollinear. Therefore, the convex hull at large time has no three points lying on the same line, except possibly as an edge, but this does not prevent convexity.
Finally, for sufficiently large $t$, each turtle lies on the boundary of the convex hull $H(t)$. Since the convex hull of a set of points is, by definition, convex, the turtles occupy the vertices of a convex polygon. Each vertex corresponds to a turtle because no point remains inside, and edges are formed between turtles along the hull boundary. The polygon has $n$ vertices if all turtles have distinct directions and no degeneracy occurs.
This completes the proof.
∎
Verification of Key Steps
Lemma 1 depends critically on the fact that the velocity vectors are distinct. If two turtles had parallel velocities, one could remain inside the expanding convex hull indefinitely. To verify, consider two turtles starting at $(0,0)$ and $(1,0)$ with identical horizontal velocities. The convex hull remains the segment connecting them, and the interior turtle never leaves. Our assumption excludes this scenario.
Lemma 3 requires checking collinearity. For three turtles at positions $(0,0)$, $(1,0)$, $(0,1)$ with velocities $(1,1)$, $(1,0)$, $(0,1)$, the points are initially noncollinear. Over time, no time $t>0$ produces exact collinearity because the determinant of the position matrix is $1 + t - t^2$, which never vanishes. This confirms the lemma holds for a generic configuration.
Alternative Approaches
One alternative approach uses an affine transformation that normalizes the speed magnitude to one and considers the unit circle of velocity directions. Mapping turtle positions into a moving reference frame aligned with the average velocity reduces the problem to showing that points with distinct radial directions eventually lie on the convex hull boundary. This approach emphasizes geometric symmetry but requires more machinery from convex geometry.
Another approach applies induction on the number of turtles. For two turtles, the statement is trivial. Assume it holds for $n$ turtles; adding the $(n+1)$-th turtle requires showing it eventually reaches the convex hull boundary. While elegant, this approach still reduces to verifying that linear motion with distinct directions ensures eventual boundary occupation, making it equivalent to the main approach. The direct hull argument is preferable for clarity and generality.