Kvant Math Problem 89

Verified: no
Verdicts: SKIP + SKIP
Solve time: 3m39s
Source on kvant.digital

Problem

Insert illustration

Prove that in any convex polygon other than a parallelogram, one can choose three sides such that the extensions of their lines form a triangle containing the given polygon. (For example, in Figure 2, where the polygon is outlined in black, the three red lines satisfy the required condition, whereas the three blue lines do not.)

I. M. Yaglom

Exploration

For a triangle the statement is trivial, since the three sides themselves already form a triangle containing the polygon.

For a convex quadrilateral, the only obstruction is a parallelogram. If the quadrilateral is not a parallelogram, then some pair of opposite sides is not parallel. The four side lines determine a complete quadrilateral, and one can check on examples that three suitable side lines always bound a triangle containing the quadrilateral. Thus the statement is plausible.

A natural way to encode a convex polygon is as the intersection of the half planes bounded by its side lines. Every side line supports the polygon, and the polygon lies on the same side of the line as its interior. The problem asks whether three of these supporting lines already suffice to define a triangle still containing the whole polygon.

The crucial point is to find three supporting lines whose inward half planes contain all the other inward half planes. In dual language this becomes a statement about directions of sides. Let the side lines be ordered cyclically. Since the polygon is convex, the outward normals of the sides also occur in cyclic order around the circle.

Suppose three side lines are chosen. Their inward half planes form a bounded triangle exactly when the three corresponding outward normals are not contained in any semicircle. The triangle then equals the intersection of those three half planes. Hence the task becomes: find three side normals such that every side normal of the polygon lies in the convex cone generated by two consecutive chosen normals. Then the corresponding three half planes imply all the others.

A convenient choice suggests itself. Consider the convex hull of the set of outward normals on the unit circle. Since the polygon is not a parallelogram, there are at least three distinct normal directions. Take three extreme directions of this convex hull. Every other normal direction lies in one of the three arcs between them. Geometrically this should imply that the corresponding supporting half plane contains the intersection of the two half planes associated with the endpoint directions. The verification of this implication is the delicate step.

Problem Understanding

We are given a convex polygon which is not a parallelogram. Each side determines a supporting line. The goal is to select three sides such that the three supporting lines of those sides are pairwise nonparallel, hence form a triangle, and this triangle contains the entire polygon.

This is a Type B problem. We must prove the stated existence claim.

The core difficulty is to pass from the many supporting lines of the polygon to only three supporting lines while preserving containment of the polygon. The essential geometric fact is that a supporting half plane corresponding to an intermediate side direction is redundant once the supporting half planes corresponding to two surrounding extreme directions are present.

Proof Architecture

Let $P$ be the polygon and let $H_1,\dots,H_n$ be the inward half planes bounded by its side lines.

First, choose three side directions whose outward normal vectors are vertices of the convex hull of all outward normal vectors on the unit circle. These three directions are distinct because the polygon is not a parallelogram.

Second, prove that every outward normal vector of the polygon lies in the positive cone generated by two consecutive chosen normals.

Third, prove the key lemma: if an outward normal $u$ is a positive linear combination of outward normals $u_1$ and $u_2$, then the corresponding inward half plane contains the intersection of the inward half planes corresponding to $u_1$ and $u_2$.

Fourth, deduce that every side half plane of the polygon contains the intersection of the three chosen half planes.

Finally, conclude that the intersection of the three chosen half planes is a triangle containing the polygon.

The lemma involving positive linear combinations of normals is the step most likely to fail under scrutiny, because it must connect a relation among directions with a containment relation among supporting half planes.

Solution

Let $P$ be a convex polygon. For each side of $P$, let $L_i$ be its supporting line and let $H_i$ be the closed half plane bounded by $L_i$ that contains $P$.

Then

$$P=\bigcap_{i=1}^{n} H_i .$$

For each side choose the unit outward normal vector $u_i$. Since $P$ is convex, the vectors $u_i$ occur in cyclic order around the unit circle.

Consider the convex hull of the set ${u_1,\dots,u_n}$. Because the polygon is not a parallelogram, the set of outward normal directions contains more than two opposite directions. Hence the convex hull has at least three vertices. Choose three vertices of this convex hull and denote the corresponding outward normals by $a,b,c$, listed in cyclic order.

Every vector $u_i$ lies in one of the three cones

$$\operatorname{cone}(a,b), \qquad \operatorname{cone}(b,c), \qquad \operatorname{cone}(c,a),$$

because $a,b,c$ are vertices of the convex hull and all normals lie on its boundary.

Let $H_a,H_b,H_c$ be the inward half planes corresponding to the sides whose outward normals are $a,b,c$.

We prove the following lemma.

Suppose an outward normal $u$ satisfies

$$u=\lambda u_1+\mu u_2, \qquad \lambda,\mu\ge 0,$$

where $u_1$ and $u_2$ are outward normals of two sides of $P$.

Let the corresponding supporting half planes be

$$H_{u_1}={x:u_1\cdot x\le \alpha_1}, \qquad H_{u_2}={x:u_2\cdot x\le \alpha_2}, \qquad H_u={x:u\cdot x\le \alpha}.$$

Since each line supports $P$,

$$\alpha_1=\max_{p\in P} u_1\cdot p,\qquad \alpha_2=\max_{p\in P} u_2\cdot p,\qquad \alpha=\max_{p\in P} u\cdot p .$$

For every $p\in P$,

$$u\cdot p = \lambda(u_1\cdot p)+\mu(u_2\cdot p) \le \lambda\alpha_1+\mu\alpha_2.$$

Taking the maximum over $P$ gives

$$\alpha\le \lambda\alpha_1+\mu\alpha_2.$$

Now let $x\in H_{u_1}\cap H_{u_2}$. Then

$$u\cdot x = \lambda(u_1\cdot x)+\mu(u_2\cdot x) \le \lambda\alpha_1+\mu\alpha_2.$$

Using the previous inequality,

$$u\cdot x\le \alpha,$$

hence $x\in H_u$.

Therefore

$$H_{u_1}\cap H_{u_2}\subseteq H_u.$$

The lemma is proved.

Now let

$$T=H_a\cap H_b\cap H_c.$$

Take any side normal $u_i$. As observed above, $u_i$ belongs to one of the cones generated by two consecutive vectors among $a,b,c$. Assume, for instance,

$$u_i\in\operatorname{cone}(a,b).$$

By the lemma,

$$H_a\cap H_b\subseteq H_i.$$

Since $T\subseteq H_a\cap H_b$, we obtain

$$T\subseteq H_i.$$

The same argument applies to every side of the polygon. Consequently,

$$T\subseteq \bigcap_{i=1}^{n} H_i=P.$$

Reversing the inclusion obtained from the definition of $P$,

$$P=\bigcap_{i=1}^{n} H_i \subseteq H_a\cap H_b\cap H_c=T.$$

Thus $P\subseteq T$.

The three normals $a,b,c$ are not contained in a semicircle, because they are three distinct vertices of the convex hull of all outward normals. Hence the three supporting lines corresponding to $a,b,c$ are pairwise nonparallel, and the intersection of the three inward half planes is a bounded region. Therefore $T$ is a triangle.

The three chosen side lines form a triangle $T$ containing the polygon $P$. This completes the proof.

∎

Verification of Key Steps

The first delicate step is the lemma. The inequality

$$\alpha\le \lambda\alpha_1+\mu\alpha_2$$

must be derived from the definition of support numbers as maxima over the polygon. If one replaced $\alpha$ by an arbitrary constant defining the same line, the argument would fail. The support function of the polygon is the exact ingredient that makes the comparison valid.

The second delicate step is the claim that every normal lies in one of the three cones determined by $a,b,c$. This uses the fact that $a,b,c$ are vertices of the convex hull of all outward normals and are taken in cyclic order. A point on the boundary arc between two consecutive vertices belongs to the positive cone generated by those vertices. Without choosing extreme directions, the statement need not hold.

The third delicate step is the boundedness of $T$. Three arbitrary supporting lines can intersect in an unbounded wedge. Boundedness follows because the outward normals $a,b,c$ are not contained in any semicircle. Equivalently, the origin lies in the interior of the triangle with vertices $a,b,c$, which is the standard criterion ensuring that the intersection of the corresponding inward half planes is a bounded triangle.

Alternative Approaches

A dual projective proof is possible. Associate to each side line its point in the dual plane. The side lines of a convex polygon correspond to points lying on a convex polygonal chain in the dual picture. The problem becomes the statement that, unless the original polygon is a parallelogram, the dual set has at least three extreme points, and the triangle formed by these extreme dual points determines three primal side lines whose supporting triangle contains the polygon. This approach is conceptually elegant but requires familiarity with duality.

Another approach uses support functions directly. Let $h(u)$ be the support function of the polygon. Choose three extreme outward normal directions $a,b,c$. Since every normal direction lies in one of the cones generated by two consecutive chosen directions, the sublinearity of $h$ implies that every supporting inequality of the polygon is a consequence of the three inequalities corresponding to $a,b,c$. The intersection of those three half planes is then a triangle containing the polygon. The proof given above is essentially an elementary version of this support function argument.