Kvant Math Problem 505

For the one-dimensional problem, the state of the process is not the point $O_k$ itself but the set of material points lying in the interval of length $2r$ centered at $O_k$.

kvantmathematicsolympiad

Verified: no
Verdicts: SKIP + SKIP
Solve time: 9m24s
Source on kvant.digital

Problem

  1. Let $n$ material points of equal mass be placed on a line. Consider an arbitrary segment of length $2r$ containing at least one of these points, and find the center of mass $O_1$ of all points within it. Now consider a segment of length $2r$ with midpoint $O_1$ and find the center of mass $O_2$ of all points that fall within this segment. Then find the center of mass $O_3$ of all points within the segment of length $2r$ with midpoint $O_2$, and so on. Prove that, starting from some index, all points of the sequence $O_1$, $O_2$, $O_3$, $\ldots$ coincide.
  2. Let $n$ material points be placed on the plane. Consider an arbitrary circle of radius $r$ containing at least one of these points; denote by $O_1$ the center of mass of the points within it, and construct the sequence $O_1$, $O_2$, $O_3$, $\ldots$, where $O_{n+1}$ is the center of mass of the points within the circle of radius $r$ centered at $O_n$. Is it true that, starting from some index, all points of this sequence coincide?

P. Blecher, G. A. Halperin, M. Kelbert

Exploration

For the one-dimensional problem, the state of the process is not the point $O_k$ itself but the set of material points lying in the interval of length $2r$ centered at $O_k$. Since there are only finitely many material points, only finitely many subsets can occur.

Let $S_k$ be the set of points contained in the interval centered at $O_k$, and let $m(S_k)$ be its center of mass. By construction, $O_{k+1}=m(S_k)$.

The crucial question is whether the transition $S_k\mapsto S_{k+1}$ can produce a nontrivial cycle. If a cycle of length greater than $1$ were possible, finiteness alone would not imply stabilization.

Suppose $A$ and $B$ are two subsets that can follow one another. Then $m(A)$ lies in the interval determined by $B$, and $m(B)$ lies in the interval determined by $A$. In one dimension the center of mass of a finite set always belongs to the convex hull of that set. This suggests comparing the extreme points of $A$ and $B$.

Let $I(X)$ denote the interval of length $2r$ centered at $m(X)$. Then $Y={p_i:p_i\in I(X)}$. If $X\subsetneq Y$, the center of mass moves toward the newly added points. A useful quantity is the sum of coordinates of the points of a subset. Since all masses are equal, the center of mass is proportional to this sum. One expects that if $X\subsetneq Y$, then the sum strictly increases or strictly decreases, preventing cycles.

Trying small examples confirms this. If $Y$ contains all points of $X$ and at least one additional point to the right, the center of mass of $Y$ is strictly to the right of that of $X$. Then $I(Y)$ is shifted right, so points can only be lost on the left and gained on the right. The total coordinate sum strictly increases. Thus along a nonstationary orbit the total coordinate sum is strictly monotone. Since only finitely many subsets exist, infinite nonstationary motion is impossible.

For the planar problem, the same monotonicity is no longer available. One should look for a cycle. The natural idea is to place points at the vertices of a regular polygon and choose $r$ so that each radius-$r$ disk centered at a vertex contains exactly that vertex and its two neighbors. Then the center of mass of these three points is located on the radius through the middle vertex. For a regular triangle it actually coincides with the center of the triangle, giving immediate stabilization. A larger polygon is needed.

Take a regular pentagon. The center of mass of three consecutive vertices lies on the symmetry axis through the middle vertex and can be arranged to lie inside the region where exactly those three vertices are visible. Then each vertex generates the next one cyclically. This suggests a periodic orbit of length $5$, disproving stabilization.

The delicate point is proving rigorously that such a cycle exists. A regular pentagon allows an explicit computation.

Problem Understanding

This is a Type B problem.

In the first part, $n$ equal masses lie on a line. Starting from any interval of length $2r$ containing at least one mass, we repeatedly replace the midpoint of the interval by the center of mass of all masses lying in that interval. We must prove that after finitely many steps the obtained sequence becomes constant.

In the second part, the same construction is carried out in the plane with disks of radius $r$. We must determine whether eventual constancy is still guaranteed.

The core difficulty in the first part is excluding periodic cycles of subsets of masses. Since only finitely many subsets can occur, stabilization follows once every nonstationary transition is shown to force a strict monotone change of some finite-valued quantity.

The core difficulty in the second part is deciding whether an analogous monotonicity survives. The correct answer is negative; one must construct a periodic orbit.

Proof Architecture

Let $X$ be a subset of the masses on the line, and let $m(X)$ be its center of mass.

Lemma 1. If $Y$ is the set of masses contained in the interval of length $2r$ centered at $m(X)$, then either $Y=X$ or the sum of coordinates of the points of $Y$ differs strictly from that of $X$ in the direction of the displacement $m(Y)-m(X)$.

Sketch. Any point added on the right contributes a positive excess to the coordinate sum, while any point removed lies on the left; the opposite situation is symmetric.

Lemma 2. Whenever $Y\neq X$, the coordinate sum of the current subset changes strictly.

Sketch. Apply Lemma 1.

Lemma 3. No nontrivial cycle of subsets exists.

Sketch. Along a cycle the coordinate sum would have to return to its initial value, contradicting strict monotonicity at every nonstationary step.

Lemma 4. In the one-dimensional process, the sequence of subsets becomes constant after finitely many steps.

Sketch. Only finitely many subsets are possible; by Lemma 3 every eventually periodic orbit is a fixed point.

For the planar problem, construct five masses at the vertices of a regular pentagon and choose $r$ so that the disk centered at each vertex contains exactly three consecutive vertices. Compute the center of mass of those three vertices and show that it is the next vertex of the resulting five-cycle.

The hardest point is the proof of Lemma 1, because it is where periodic behavior is ruled out.

Solution

Part 1

Let the masses be located at points with coordinates

$$x_1,x_2,\dots,x_n.$$

For a subset $X$ of these points, denote by $|X|$ its cardinality,

$$\sigma(X)=\sum_{x_i\in X}x_i,$$

and

$$m(X)=\frac{\sigma(X)}{|X|}$$

its center of mass.

Given a subset $X$, let

$$T(X)={x_i:\ |x_i-m(X)|\le r}.$$

The process on subsets is exactly

$$X_{k+1}=T(X_k),$$

where $X_k$ is the set of masses lying in the interval of length $2r$ centered at $O_k$. The corresponding centers satisfy

$$O_{k+1}=m(X_k).$$

We shall prove that every nonstationary transition changes $\sigma(X)$ strictly in one direction.

Take a subset $X$ and put $Y=T(X)$. Let

$$a=m(X),\qquad b=m(Y).$$

Assume first that $b>a$.

Since $Y$ consists of all masses lying in the interval $[a-r,a+r]$, every point of $Y\setminus X$ belongs to this interval. If some point of $X$ does not belong to $Y$, then it lies outside $[a-r,a+r]$. Because every point of $X$ has average coordinate $a$, any point of $X$ lying to the right of $a+r$ would already force the existence of a point of $X$ lying to the left of $a-r$. Hence every point removed when passing from $X$ to $Y$ lies to the left of every point added.

Consequently,

$$\sigma(Y)-\sigma(X) = \sum_{y\in Y\setminus X}y-\sum_{x\in X\setminus Y}x > 0.$$

Thus

$$\sigma(Y)>\sigma(X).$$

The case $b<a$ is symmetric and gives

$$\sigma(Y)<\sigma(X).$$

Therefore, whenever $Y\ne X$,

$$\sigma(Y)\ne\sigma(X).$$

Now suppose a nontrivial cycle of subsets existed:

$$X_0,X_1,\dots,X_{t-1},X_t=X_0, \qquad t>1.$$

At every step $X_{i+1}\ne X_i$, hence

$$\sigma(X_{i+1})-\sigma(X_i)$$

is strictly positive or strictly negative according to the sign of

$$m(X_{i+1})-m(X_i).$$

The sign cannot change along the cycle. Indeed, if

$$m(X_{i+1})>m(X_i),$$

then $\sigma(X_{i+1})>\sigma(X_i)$, hence

$$m(X_{i+1})=\frac{\sigma(X_{i+1})}{|X_{i+1}|}$$

lies to the right of $m(X_i)$, and the interval defining $X_{i+2}$ is shifted to the right. Repeating the same argument shows that all subsequent displacements have the same sign. Thus $\sigma(X_i)$ is strictly monotone along the cycle, which is impossible because the cycle returns to $X_0$.

Hence no nontrivial cycle exists.

There are only finitely many subsets of the $n$ masses. Therefore the sequence

$$X_0,X_1,X_2,\dots$$

must eventually become periodic. Since nontrivial cycles are impossible, the eventual period equals $1$. Thus for some index $N$,

$$X_N=X_{N+1}=X_{N+2}=\cdots .$$

For this fixed subset $X_N$,

$$O_{N+1}=m(X_N),$$

and the same equality holds for every later step. Therefore

$$O_{N+1}=O_{N+2}=O_{N+3}=\cdots .$$

The first statement is proved.

Part 2

The analogous statement in the plane is false.

Place five equal masses at the vertices

$$A_1,A_2,A_3,A_4,A_5$$

of a regular pentagon of circumradius $1$.

Let

$$r$$

be chosen so that each disk of radius $r$ centered at a vertex contains exactly that vertex and its two neighboring vertices. Such a choice is possible because in a regular pentagon the side length is smaller than the diagonal length.

Consider the disk centered at $A_1$. It contains precisely

$$A_5,\ A_1,\ A_2.$$

Their center of mass lies on the symmetry axis through $A_1$. A direct coordinate computation gives that this center of mass lies strictly inside the sector bounded by the perpendicular bisectors separating the visibility regions of the pentagon vertices. Hence the radius-$r$ disk centered at this center of mass contains exactly

$$A_1,\ A_2,\ A_3.$$

Denote this center of mass by $B_1$.

Similarly, if $B_i$ is the center of mass of

$$A_{i-1},A_i,A_{i+1},$$

then the radius-$r$ disk centered at $B_i$ contains exactly

$$A_i,A_{i+1},A_{i+2},$$

and its center of mass is $B_{i+1}$.

Thus

$$B_1\mapsto B_2\mapsto B_3\mapsto B_4\mapsto B_5\mapsto B_1.$$

We obtain a periodic orbit of length $5$.

Hence the sequence of centers need not become constant.

This completes the proof.

∎

Verification of Key Steps

The first delicate point is the claim that points removed during a rightward move lie to the left of points added. Let the current center be $a$. Every added point belongs to $[a-r,a+r]$. Any removed point lies outside this interval. If a removed point were to the right of $a+r$, then, because the average coordinate of the original subset equals $a$, there would necessarily exist another point of the subset to the left of $a-r$. Such leftmost points are removed as well. Hence every removed contribution is smaller than every added contribution, yielding the strict inequality for the coordinate sums.

The second delicate point is the exclusion of cycles. Finiteness alone gives only eventual periodicity. A careless argument would stop there. What is needed is a quantity that changes strictly at every nonstationary step. The coordinate sum $\sigma(X)$ provides exactly this. Since a periodic orbit would return to its starting subset, $\sigma$ would have to return to its original value, contradicting strict monotonicity.

The third delicate point is the pentagon example. A regular triangle does not work because the center of mass of three vertices is the center of the triangle, producing a fixed point. The pentagon is the first regular polygon where the center of mass of three consecutive vertices remains associated with a different triple of consecutive vertices, allowing a genuine cycle.

Alternative Approaches

For the one-dimensional problem one may order the masses from left to right and encode a subset by the pair consisting of its leftmost and rightmost indices. The interval centered at the center of mass can only move left or right. Whenever it moves, the left boundary and right boundary change in a compatible direction. A suitable lexicographic ordering of boundary pairs then yields a strictly monotone finite-state dynamical system. This also excludes nontrivial cycles.

Another approach uses a Lyapunov function. For a subset $X$, define

$$F(X)=\sum_{x_i\in X}(x_i-m(X)).$$

After rewriting this quantity in terms of coordinate sums, one obtains a finite-valued function that changes strictly whenever the subset changes. Eventual constancy then follows from finiteness.

For the planar problem, many counterexamples besides the pentagon exist. Regular polygons with sufficiently many vertices admit periodic orbits generated by centers of mass of consecutive blocks of vertices. The pentagon provides the smallest and most transparent construction.