Kvant Math Problem 330

Let $M_0$ and $M_1$ be convex polygons.

kvantmathematicsolympiad

Verified: no
Verdicts: SKIP + SKIP
Solve time: 4m41s
Source on kvant.digital

Problem

In the plane there are two convex polygons $M_0$ and $M_1$. Let $M$ denote the set of points that can be the midpoint of a segment whose one endpoint belongs to $M_0$ and the other to $M_1$. Prove that $M$ is a convex polygon.

  1. How many sides can $M$ have if $M_0$ has $n_0$ of them, and $M_1$ has $n_1$?
  2. What can be the perimeter of $M$ if the perimeter of $M_0$ is $P_0$, and that of $M_1$ is $P_1$?
  3. What can be the area of $M$ if the area of $M_0$ is $S_0$, and the area of $M_1$ is $S_1$?

N. B. Vasiliev

Exploration

Let $M_0$ and $M_1$ be convex polygons. A point $x$ lies in $M$ if and only if there exist $a\in M_0$ and $b\in M_1$ such that $x=\frac{a+b}{2}$. This identifies $M$ as a scaled Minkowski sum:

$$M=\frac{1}{2}(M_0+M_1).$$

Thus all structural questions reduce to properties of Minkowski sums and linear scaling.

For edges, Minkowski sums of polygons behave by adding edge vectors in cyclic order. This suggests that the number of edges depends on how edge directions from $M_0$ and $M_1$ interleave.

For perimeter, edge vectors add directly, so lengths should combine linearly before scaling.

For area, the situation is quadratic; a mixed area term appears, and different shapes with the same areas can produce different mixed terms, suggesting non-uniqueness.

The main risk is overclaiming uniqueness for area and failing to control degeneracies when edges are parallel.

Problem Understanding

The problem asks to prove that the midpoint set

$$M=\left{\frac{a+b}{2}\mid a\in M_0,\ b\in M_1\right}$$

is a convex polygon, and then determine what can be said about its number of sides, perimeter, and area in terms of those of $M_0$ and $M_1$.

This is Type A for convexity and side count, and Type C for perimeter and area ranges.

The key structural fact is that $M$ is a homothetic image of a Minkowski sum, so its geometry is governed by vector addition of boundary edges.

The final results will be:

the number of sides lies between $\max(n_0,n_1)$ and $n_0+n_1$,

the perimeter is fixed as $\frac{P_0+P_1}{2}$,

and the area satisfies a sharp lower bound but no upper bound.

Proof Architecture

The first lemma states that $M$ equals $\frac12(M_0+M_1)$, where the right-hand side is a Minkowski sum followed by scaling, establishing convexity immediately from closure of convex sets under Minkowski addition and scaling.

The second lemma asserts that the boundary of a Minkowski sum of convex polygons is obtained by cyclic concatenation of edge vectors sorted by direction.

The third lemma identifies that the number of sides equals the number of distinct edge direction changes in this concatenation, yielding the bound between $\max(n_0,n_1)$ and $n_0+n_1$.

The fourth lemma computes perimeter additively under Minkowski sum and scaling.

The fifth lemma describes area via mixed area:

$$S(A+B)=S(A)+S(B)+2A\cdot B,$$

with the mixed term depending on geometry, and applies the Brunn–Minkowski inequality for the lower bound.

The most delicate point is controlling the variability of the mixed area term in the final part.

Solution

Every point of $M$ has the form $x=\frac{a+b}{2}$ with $a\in M_0$ and $b\in M_1$, hence

$$M=\left{\frac{a+b}{2}\mid a\in M_0,\ b\in M_1\right}=\frac12(M_0+M_1),$$

where $M_0+M_1={a+b\mid a\in M_0,\ b\in M_1}$ is the Minkowski sum.

Convexity of $M_0+M_1$ follows from convexity of $M_0$ and $M_1$, since for $x_i=a_i+b_i$ with $a_i\in M_0$, $b_i\in M_1$ and $t\in[0,1]$,

$$tx_1+(1-t)x_2=(ta_1+(1-t)a_2)+(tb_1+(1-t)b_2),$$

and both bracketed terms lie in $M_0$ and $M_1$ respectively. Scaling by $\frac12$ preserves convexity, so $M$ is convex.

Each convex polygon is determined by its cyclic sequence of edge vectors. Let the edge vectors of $M_0$ be ordered cyclically as $u_1,\dots,u_{n_0}$ and those of $M_1$ as $v_1,\dots,v_{n_1}$. The boundary of $M_0+M_1$ is obtained by merging these sequences according to the ordering of their directions on the unit circle, producing a cyclic sequence consisting of all $u_i$ and $v_j$ in sorted angular order, with collinear consecutive vectors merged into a single edge.

Every direction of an edge of $M_0+M_1$ coincides with a direction occurring in either $M_0$ or $M_1$, and every such direction appears at least once. Hence the number of edges of $M_0+M_1$ is at least $\max(n_0,n_1)$ and at most $n_0+n_1$, with every intermediate value attainable by arranging parallelisms so that merges occur.

Since $M$ is obtained from $M_0+M_1$ by homothety with factor $\frac12$, it has the same number of sides, and these bounds hold for $M$ as well.

The perimeter satisfies additivity for Minkowski sums. Each edge of $M_0+M_1$ is a sum of an edge from $M_0$ and an edge from $M_1$ in the same direction ordering, so the total variation of support in any fixed direction adds. Equivalently, summing the lengths of all edges in the merged cyclic sequence gives

$$P(M_0+M_1)=P_0+P_1.$$

Scaling by $\frac12$ multiplies all lengths by $\frac12$, so

$$P(M)=\frac{P_0+P_1}{2}.$$

For area, write $A=M_0$, $B=M_1$. The area of Minkowski sums satisfies

$$S(A+B)=S(A)+S(B)+2I(A,B),$$

where $I(A,B)$ is the mixed area, symmetric and bilinear in $A$ and $B$ under Minkowski addition. Therefore

$$S(M)=\frac14 S(M_0+M_1)=\frac14\bigl(S_0+S_1+2I(M_0,M_1)\bigr).$$

The mixed term is not determined by $S_0$ and $S_1$. It satisfies the Brunn–Minkowski inequality

$$\sqrt{S(A+B)}\ge \sqrt{S(A)}+\sqrt{S(B)},$$

which implies

$$S(A+B)\ge (\sqrt{S_0}+\sqrt{S_1})^2.$$

Dividing by $4$ yields the lower bound

$$S(M)\ge \frac{(\sqrt{S_0}+\sqrt{S_1})^2}{4}.$$

Equality holds when $M_0$ and $M_1$ are homothetic.

No upper bound depending only on $S_0$ and $S_1$ exists, since by fixing two polygons of prescribed areas and stretching one of them into a long thin shape while preserving area, the mixed area term $I(M_0,M_1)$ can be made arbitrarily large, which forces $S(M)$ to grow without bound.

Thus the possible values of the area are all

$$S(M)\in \left[\frac{(\sqrt{S_0}+\sqrt{S_1})^2}{4},\ \infty\right).$$

Verification of Key Steps

The identification $M=\frac12(M_0+M_1)$ follows directly from distributing the scaling over the sum; no hidden assumption is used.

In the perimeter computation, the key point is that the boundary construction of a Minkowski sum preserves total edge length by concatenation of edge vectors in ordered direction. The potential failure case is cancellation, but convexity prevents opposite-direction cancellation within a polygonal boundary representation.

For the area range, the critical point is variability of the mixed area. Fixing areas does not constrain aspect ratios, and scaling one polygon in one direction while inversely scaling in the perpendicular direction preserves area but increases interaction with the other polygon, which increases the mixed term without bound.

Alternative Approaches

One alternative derivation uses support functions. The support function of $M$ is

$$h_M(\theta)=\frac12(h_{M_0}(\theta)+h_{M_1}(\theta)),$$

from which convexity, perimeter additivity via integration of $h$, and area formulas via Fourier expansion follow systematically.

Another approach for the number of sides tracks normal fans of the polygons, interpreting $M$ as the Minkowski sum of fans and counting resulting angular partitions. This gives the same bounds but makes the combinatorics of edge merging more transparent.