A puzzle by Andrei Zelevinsky

While I was reading Tanya Khovanova‘s blog I came across this problem which Andrei Zelevinsky reportedly put in his list of important problems that undegraduate students should think of. The problem reads:

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.

I’d like to present one solution in the rest of this post.

One way to solve this problem is to use complex coordinates. Denote by z_1,...z_n \in \mathbb{C} the points. One iteration of the process yields the points (\frac{z_1+z_2}{2},\frac{z_2+z_3}{2},...,\frac{z_{n-1}+z_n}{2},\frac{z_n+z_1}{2}). More generally, the m-th iteration yields the points \Big( \sum_{l=1}^n a_{i,l}^{(m)} z_l  \Big)_{1\leq i\leq n}, where
a_{i,l}^{(m)}= \frac{1}{2^m} {\displaystyle \sum_{\begin{array}{c} 0\leq k\leq m\\ i+k\equiv l[n]  \end{array} }}\binom{m}{k}.

Now we can prove that the a_{_i,l}^{(m)} tend to \frac{1}{n} as m\to \infty, independently of i and l. To see this let us take the example of i,l=0, WLOG. A straightforward calculation using the m-th roots of unity gives a_{0,0}^{(m)}=\frac{1}{2^m}\sum _{0 \leq k \leq n-1}(1+\omega ^k)^m=  \frac{1}{K}{\displaystyle \sum_{k=0}^{n-1}}\cos^{m}\frac{k\pi}{n}e^{\frac{ik\pi m}{n}};

This means that the procedure converges to a unique point which is the barycenter of the n original points, which concludes the proof.

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.

Advertisements

One thought on “A puzzle by Andrei Zelevinsky”

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s