Two weeks ago, my friend Ismael wrote a blog post about this problem:
Consider a procedure: Given a polygon in a plane, the next polygon is formed by the centers of its edges. Prove that if we start with a polygon and perform the procedure infinitely many times, the resulting polygon will converge to a point. In the next variation, instead of using the centers of edges to construct the next polygon, use the centers of gravity of k consecutive vertices.
I did not like his solution because he uses heavy computations on complex numbers. I think that when the problem is simple to explain, its solution should be trivial to understand without a pen or a paper.
In this article, I’ll first analyze a defectuous solution found in the comments, then correct it. Finally, I’ll give my own solution.
An incomplete solution
There is a solution in the comments of the original blog post:
Here is a solution to problem 2 received from Dan Klain:
First, to show a limit exists: Since the sequence P_0, P_1, P_2, … is bounded (all contained in P_0), compactness tells us there is a convergent subsequence. But since the sequence is also monotone P_0 > P_1 > … the original sequence must have the same limit as the subsequence. Call this limiting set Q.
If the original polygon has k vertices, then so do all its successors in the sequence. In the limit the number of vertices will stay the same or decrease, but cannot increase. So Q is a polygon with at most k vertices.
Applying the operation to the whole sequence just shifts it forward one step, so the tail is the same, and Q must be invariant under the operation. This is impossible unless Q is a single point. Moreover, the operation preserves the mean of the (original) vertices, so Q must be that point.
As all polygons have the same center of gravity, the limiting point is the centroid.
I loved the use of compactness. But there are some holes:
“the sequence is also monotone”
It is not clear what they mean with “monotone”. A lot of people assume the polygon is regular or convex, but it is not. Its area is not necessarily decreasing.
But its perimeter is: it is easy to see by triangular inequality that every new edge is less that the mean of the two edges its vertices come from, and then you sum. But it is not sufficient to prove the convergence because of special cases when two points are the same.
At first, I told Ismael it was possible to consider some function of the convex hull because the problem is much simpler on convex polygons. But the procedure is not monotone for the inclusion of the convex hulls, so I couldn’t make this idea work.
I found that there is another decreasing quantity than the perimeter that makes the proof work (see below).
“This is impossible unless Q is a single point.”
It is absolutely not obvious. We will thus prove that below.
A correct solution
Instead of the perimeter, take the sum of the distances between the vertices $x_i$:
\[\sum\limits_{i, j} \left| x_i - x_j \right|\]When you apply the procedure, it becomes
\[\sum\limits_{i, j} \left| \frac{x_i + x_{i+1}}{2} - \frac{x_j + x_{j+1}}{2} \right|\]But
\[\left| \frac{x_i + x_{i+1}}{2} - \frac{x_j + x_{j+1}}{2} \right| \le \frac{ \left| x_i - x_j \right| + \left| x_{i+1} - x_{j+1} \right| }{2}\]So this quantity is decreasing too.
Take the convergent subsequence. The sum of the distances will converge as well.
Since it is stationnary, then all inequalities are equalities, so all non-zero edges are positively colinear. That is impossible. If you want to be perfectly rigorous, merge the identical adjacent vertices, you obtain $n$ vertices and sum the angles between the $n$ edges. The sum of the angles of a polygon is $(n-2) \pi$ but you have $n$ $\pi$ angles.
This solution works as well with the variation using the centers of gravity of $k$ consecutive vertices.
My solution with linear algebra ❤
What I don’t like about the solution above is that it requires one to consider the right quantity. Of course, it is nice to find such solutions because it proves that one has great creativity and intuition. But having more systematic solutions allows to better generalize the results.
Let us consider the procedure as a linear transformation on the vertices. There are $n$ vertices in the beginning.
You can either think of it as an endomorphism of $(\mathbb{R}^2)^n$ or $\mathbb{C}^n$, but I prefer to see the points as formal variables $X_i$ and the transformation as a linear endomorphism of $Sp({X_i \mid 1 \le i \le n })$ ($Sp$ is the linear span).
Let $I$ = $I_n$ and
\[J = \left( \begin{array}{ccccc} 0 & 1 & 0 & \cdots & 0\\ 0 & 0 & \ddots & \ddots & \vdots \\ \vdots & \ddots & \ddots & \ddots & 0 \\ 0 &\ddots & \ddots & 0 & 1 \\ 1 & 0 & \cdots & 0 & 0 \end{array} \right)\]Then the procedure is simply $ F = \frac{ I + J }{2} $. $F$ has $n$ different eigenvalues: $ \{ \frac{ \omega_n^i + 1}{2} \mid 1 \le i \le n \} $.
It is interesting to see that $F$ is invertible iff $n$ is not even, and if $n$ is even, the kernel has 1 dimension (alternating $1$ and $-1$ coefficients).
In any case, 1 is an eigenvalue, and the others have moduli less than $1$. The eigenspace with eigenvalue $1$ is the space of vectors with identical coordinates, because it works and by multiplicity.
Thus, the polygon converges to a single point.
To generalize, you have to show the same results on
\[\frac{1}{k}\sum\limits_{i=0}^{k-1} J^i\]I first used the triangular equality on the spectral norm, but applying the triangle inequality on the eigenvalues is straightforward.
Conclusion
Don’t trust proofs posted on the Internet. Everybody makes mistakes, but nobody rereads their old comments.