Kvant Math Problem 392
Let the positions of the three pedestrians at time $t$ be represented by vectors $A(t), B(t), C(t)$ in the plane.
Verified: no
Verdicts: SKIP + SKIP
Solve time: 6m44s
Source on kvant.digital
Problem
Three pedestrians move along three straight roads with constant speeds. At the initial moment, they are not located on a single straight line. Prove that they can become collinear no more than twice.
N. B. Vasiliev
All-Union Mathematical Olympiad of School Students (1976, 10th grade)
Exploration
Let the positions of the three pedestrians at time $t$ be represented by vectors $A(t), B(t), C(t)$ in the plane. Since each pedestrian moves along a straight line with constant speed, each trajectory is of the form
$$A(t)=A_0+t\alpha,\quad B(t)=B_0+t\beta,\quad C(t)=C_0+t\gamma,$$
for fixed vectors $A_0,B_0,C_0,\alpha,\beta,\gamma$.
Collinearity of the three points is equivalent to the signed area of triangle $A(t)B(t)C(t)$ being zero, that is,
$$\det(B(t)-A(t),, C(t)-A(t))=0.$$
Expanding, each difference is affine in $t$, so the determinant becomes a polynomial in $t$ of degree at most $2$. Hence the number of times when it vanishes is bounded by the number of roots of a quadratic polynomial, suggesting at most two collinearity moments unless degeneracy forces the polynomial to be identically zero.
The key point is to exclude the possibility that the determinant vanishes for all $t$, which would imply perpetual collinearity, contradicting the initial condition.
Problem Understanding
This is a Type B problem: prove that three points moving with constant velocities in the plane can become collinear at most twice, given that they are not initially collinear.
The core difficulty is to translate a geometric condition, collinearity, into an algebraic condition in time and control its algebraic degree. The structure of affine motion suggests a polynomial constraint whose degree controls the number of solutions.
Proof Architecture
The motion of each pedestrian is expressed as an affine function of time in the plane, which implies that all relative position vectors are affine in $t$.
The determinant condition for collinearity is a polynomial equation in $t$ of degree at most $2$, since it is formed from a $2\times 2$ determinant of affine-linear expressions.
The polynomial is not identically zero because the points are not collinear at $t=0$, so it has at most two real roots.
The most delicate point is excluding degeneracy where the polynomial becomes identically zero; this corresponds exactly to permanent collinearity, which contradicts the initial condition.
Solution
Let the positions of the three pedestrians at time $t$ be
$$A(t)=A_0+t\alpha,\quad B(t)=B_0+t\beta,\quad C(t)=C_0+t\gamma,$$
where $A_0,B_0,C_0,\alpha,\beta,\gamma$ are fixed vectors in $\mathbb{R}^2$.
The points $A(t),B(t),C(t)$ are collinear if and only if the vectors $B(t)-A(t)$ and $C(t)-A(t)$ are linearly dependent, which is equivalent to
$$D(t)=\det(B(t)-A(t),,C(t)-A(t))=0.$$
We compute the structure of $D(t)$. We have
$$B(t)-A(t)=(B_0-A_0)+t(\beta-\alpha),\quad C(t)-A(t)=(C_0-A_0)+t(\gamma-\alpha).$$
Substituting into the determinant yields
$$D(t)=\det((B_0-A_0)+t(\beta-\alpha),, (C_0-A_0)+t(\gamma-\alpha)).$$
Using bilinearity of the determinant,
$$D(t)=\det(B_0-A_0,,C_0-A_0) +t\det(B_0-A_0,,\gamma-\alpha) +t\det(\beta-\alpha,,C_0-A_0) +t^2\det(\beta-\alpha,,\gamma-\alpha).$$
Thus $D(t)$ is a polynomial in $t$ of degree at most $2$.
At $t=0$, we have $D(0)=\det(B_0-A_0,,C_0-A_0)\neq 0$ since the initial positions are not collinear. Hence $D(t)$ is not the zero polynomial.
A nonzero polynomial of degree at most $2$ has at most two real roots. Therefore the equation $D(t)=0$ has at most two solutions in $t$, meaning the three pedestrians become collinear at most twice.
This completes the proof. ∎
Verification of Key Steps
The first delicate point is the determinant expansion. Each vector $B(t)-A(t)$ and $C(t)-A(t)$ is explicitly affine in $t$, so every term in the determinant expansion arises from bilinearity, producing exactly constant, linear, and quadratic contributions with no higher-order terms, since products of at most first-degree terms in $t$ appear only in the mixed $t^2$ term.
The second point concerns the possibility that $D(t)$ is identically zero. If this occurred, then $D(0)=0$, which contradicts the assumption that $A_0,B_0,C_0$ are not collinear. Hence the polynomial has nonzero constant term and cannot vanish identically.
The third point is the connection between roots of $D(t)$ and collinearity events. The determinant vanishes exactly when the two difference vectors are linearly dependent, which is equivalent to collinearity of the three points in the plane.
Alternative Approaches
One alternative approach uses projective geometry, interpreting motion as a curve in the Grassmannian of lines and studying intersection with the variety of degenerate configurations. The same conclusion emerges from degree counting in a more geometric setting.
Another approach uses barycentric coordinates: the signed area of triangle $A(t)B(t)C(t)$ evolves quadratically in time because each coordinate is affine in $t$, leading again to a quadratic equation whose roots correspond to collinearity times. The determinant method is preferable because it makes the degree bound immediate and avoids coordinate expansions.