Kvant Math Problem 20

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

Problem

Is it possible to divide an equilateral triangle into one million convex polygons so that any straight line intersects no more than forty of these polygons? (We say that a line intersects a polygon if it has at least one point in common with it.)

Moscow Mathematical Olympiad (XXXI)

Exploration

Let the maximum number of polygons met by a line be denoted by $k$. The problem asks about $k=40$ and $N=10^6$ pieces.

A first thought is that one should use the three distinguished directions determined by the sides of the equilateral triangle. Every line parallel to a side intersects at most $k$ polygons. Since the pieces are convex, the intersection of any piece with such a line is always a segment, and along each parallel line the pieces appear in a well-defined order.

The natural hope is to assign to each polygon three integers, one for each family of parallels, describing its position in that order. Since every parallel line meets at most $k$ polygons, each coordinate would take at most $k$ values. If different polygons always received different triples, then the number of polygons would be at most $k^3$.

The delicate point is the injectivity. Two distinct polygons might conceivably occupy the same position with respect to all three families of parallels. One has to show that this cannot happen. The convexity of the pieces is exactly what makes the ordering along a family of parallel lines stable and allows one to define the three coordinates unambiguously.

With $k=40$, the bound $k^3=64000$ is already far below $10^6$, so such an argument would settle the problem.

The step most likely to hide an error is the proof that two different polygons cannot have the same triple of coordinates.

Problem Understanding

An equilateral triangle is partitioned into convex polygons. Every straight line is required to intersect at most forty of the polygons. The question is whether one can obtain as many as one million polygons.

This is a Type B problem. We must prove or disprove the existence of such a partition.

The core difficulty is converting a geometric condition about intersections with lines into a numerical upper bound on the number of convex pieces.

The answer should be negative. The restriction on line intersections is so strong that the pieces can be organized into only finitely many possible “layers” relative to the three side directions of the triangle, and the number of such layer combinations is much smaller than one million.

Proof Architecture

Define three families of parallel lines, each parallel to one side of the equilateral triangle. For every polygon and every family, define its layer number as its position in the ordering induced on any line of that family intersecting the polygon. Convexity guarantees that this number is well defined.

Prove that every layer number belongs to ${1,\dots,k}$, where $k$ is the maximal number of polygons met by a line. This follows directly from the hypothesis.

Associate to every polygon a triple of layer numbers. There are at most $k^3$ possible triples.

Prove that different polygons receive different triples. The idea is that if two convex polygons had the same layer number in all three directions, then each would have to lie simultaneously on the same side of the other with respect to the three side directions, which is impossible.

Conclude that the number of polygons is at most $k^3$. For $k=40$ this gives at most $64000$ polygons, far fewer than $10^6$.

The hardest part is the injectivity of the triple assignment.

Solution

Let the sides of the equilateral triangle be denoted by $a$, $b$, and $c$. For each side, consider the family of all lines parallel to that side.

Let $k$ be the maximum number of polygons intersected by a line. In the problem, $k=40$.

Fix one of the three families, say the family of lines parallel to $a$. Take a line $\ell$ from this family. Since all pieces are convex and have disjoint interiors, the intersections of the pieces with $\ell$ form disjoint segments on $\ell$. Hence the pieces met by $\ell$ are linearly ordered along $\ell$.

For a polygon $P$, consider any line $\ell$ parallel to $a$ that intersects the interior of $P$. Along $\ell$, count the polygons from one end of the triangle to the other. Let $r_a(P)$ be the position occupied by $P$ in this order.

We must check that $r_a(P)$ is independent of the chosen line $\ell$.

Since $P$ is convex, the set of lines parallel to $a$ that meet $P$ forms an interval of the family. As such a line moves continuously through that interval, the order of the polygons can change only when two polygons exchange positions. That would require their interiors to cross, which is impossible. Hence the position of $P$ remains constant throughout the interval, and $r_a(P)$ is well defined.

In the same way we define $r_b(P)$ and $r_c(P)$.

Since every line intersects at most $k$ polygons, each of the numbers $r_a(P)$, $r_b(P)$, and $r_c(P)$ belongs to the set ${1,\dots,k}$.

Thus every polygon receives a triple

$$\bigl(r_a(P),,r_b(P),,r_c(P)\bigr).$$

There are at most $k^3$ such triples.

It remains to prove that different polygons cannot receive the same triple.

Assume that two distinct polygons $P$ and $Q$ have

$$r_a(P)=r_a(Q),\qquad r_b(P)=r_b(Q),\qquad r_c(P)=r_c(Q).$$

Because $P$ and $Q$ are distinct convex polygons with disjoint interiors, there exists a line separating them. Among the three side directions, choose one, say the direction corresponding to $a$, for which the projections of $P$ and $Q$ onto a line perpendicular to $a$ are different. Then one of the polygons lies strictly before the other in the ordering induced by lines parallel to $a$.

Consequently, on every line parallel to $a$ meeting both polygons, one polygon occupies a strictly smaller position number than the other. Therefore

$$r_a(P)\neq r_a(Q),$$

contrary to the assumption.

Hence distinct polygons receive distinct triples.

Therefore the number $N$ of polygons satisfies

$$N\le k^3.$$

For $k=40$,

$$N\le 40^3=64000.$$

Since

$$64000<1000000,$$

an equilateral triangle cannot be divided into one million convex polygons with the stated property.

This completes the proof.

∎

Verification of Key Steps

The first delicate point is the definition of the layer number. If a polygon were not convex, a line parallel to a side could meet it in several disjoint segments, and its position along the line would not be well defined. Convexity guarantees that every intersection is a single segment, so the ordering is meaningful.

The second delicate point is the claim that the layer number does not depend on the chosen parallel line. A careless argument might ignore the possibility that two polygons exchange places as the line moves. Such an exchange would force the interiors of the polygons to cross. Since the partition consists of convex polygons with disjoint interiors, this cannot occur.

The third delicate point is injectivity. The contradiction comes from choosing a direction in which the two polygons are separated. Along the corresponding family of parallel lines, one polygon is always encountered before the other. Their layer numbers in that direction must then be different. Without using the separation of convex sets, the conclusion would not follow.

Alternative Approaches

One can reformulate the argument in barycentric coordinates. Relative to the three sides of the equilateral triangle, every point has three barycentric coordinates. Each convex polygon occupies a consecutive interval in each coordinate. The maximal line-intersection condition implies that in each coordinate direction there are at most $k$ possible layers. Assigning to a polygon its three layer indices again yields at most $k^3$ possibilities.

Another approach uses interval orders. For each of the three side directions, project every polygon onto the perpendicular axis. The projections are intervals, and at every point at most $k$ of them overlap. One can encode each polygon by its position in the three interval systems and obtain the same bound $N\le k^3$. The direct layer argument is preferable because it avoids additional combinatorial machinery and keeps the geometric meaning visible throughout the proof.