Kvant Math Problem 1023

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

Problem

Is it always true that among 100 triangles there is at least one that can be completely covered by the other 99?

G. A. Gurevich

Exploration

For small numbers of triangles the statement is false. Take two disjoint triangles. Neither can be covered by the other. Thus no purely combinatorial principle of the form “among many triangles one is contained in the union of the others” is automatically true.

The question asks specifically about $100$ triangles. A natural attempt is to place many triangles so that each possesses a point not belonging to any other triangle. If this can be done for arbitrarily many triangles, then no triangle is covered by the remaining ones.

Consider triangles having a common interior point and very narrow angular sectors around it. Let the directions of the sectors be different. If each triangle extends far in its own direction, then the distant vertex of a triangle may lie outside all the others. Since a triangle contains all its vertices, such a vertex would be a private point of that triangle.

The issue requiring the greatest care is to ensure that every triangle indeed has a point not contained in any of the others. It is not enough to draw a picture. One must verify that the chosen distinguished vertex of each triangle lies outside every other triangle.

A convenient model is obtained by placing points $A_1,\dots,A_{100}$ on a circle and taking a small disk around the center $O$. For each $i$, let $T_i$ be the convex hull of $A_i$ and a short chord of the disk opposite to $A_i$. Then each $T_i$ is a thin triangle pointing toward $A_i$. If the chord is chosen sufficiently short, the angular width of $T_i$ at $O$ is very small. Since the directions $OA_i$ are distinct, each vertex $A_i$ can be made to lie outside all other triangles. Then $A_i$ is a point belonging only to $T_i$.

This produces not merely $100$ triangles but arbitrarily many.

Problem Understanding

We are asked whether every collection of $100$ triangles must contain a triangle that is completely covered by the union of the other $99$ triangles.

This is a Type B problem. The statement to be proved or disproved is universal. To solve it, one must determine whether a counterexample exists.

The core difficulty is constructing many triangles so that each triangle has a point that belongs to no other triangle. If such a configuration exists for $100$ triangles, then no triangle can be covered by the remaining $99$.

Proof Architecture

The proof uses one construction and two claims.

First, choose $100$ rays from a common point $O$, equally spaced in direction, and place a point $A_i$ on the $i$-th ray at distance $1$ from $O$.

Second, around $O$ choose a very small circle of radius $\varepsilon$. On the two rays making angles $\pm\delta$ with $OA_i$, take their intersections $B_i,C_i$ with that small circle. Let $T_i=\triangle A_iB_iC_i$.

The first claim is that for sufficiently small $\delta$, every triangle $T_i$ is contained in the angular sector bounded by the rays through $B_i$ and $C_i$. This follows from convexity.

The second claim is that if $\delta$ is smaller than half the angular separation between consecutive rays, then $A_i$ does not belong to any triangle $T_j$ with $j\neq i$. The reason is that every $T_j$ lies inside an angular sector that does not contain the ray $OA_i$.

The hardest point is the second claim, because one must convert the geometric picture into a precise containment argument.

Solution

The answer is negative.

Let $O$ be a point in the plane. Draw $100$ rays from $O$ whose directions are

$$0,\ \frac{2\pi}{100},\ \frac{2\cdot2\pi}{100},\ \dots,\ \frac{99\cdot2\pi}{100}.$$

On the $i$-th ray choose a point $A_i$ with $OA_i=1$.

Let

$$\delta=\frac{\pi}{300}.$$

Around $O$ draw a circle of radius $\varepsilon$, where $\varepsilon>0$ is arbitrary. For each $i$, let $B_i$ and $C_i$ be the points where this circle meets the rays forming angles $-\delta$ and $+\delta$ with the ray $OA_i$. Define

$$T_i=\triangle A_iB_iC_i .$$

We shall show that no triangle $T_i$ is covered by the other $99$ triangles.

Consider a fixed index $i$. The points $B_i$ and $C_i$ lie on rays issuing from $O$ at angles differing from the direction of $OA_i$ by at most $\delta$. Since $T_i$ is the convex hull of $A_i,B_i,C_i$, every point of $T_i$ lies in the closed angular sector bounded by those two rays. Hence every point of $T_i$ has direction from $O$ lying between the directions of $OB_i$ and $OC_i$.

The angular width of this sector equals

$$2\delta=\frac{\pi}{150}.$$

The angle between two consecutive rays $OA_k$ equals

$$\frac{2\pi}{100}=\frac{\pi}{50}.$$

Since

$$\frac{\pi}{150}<\frac{\pi}{100},$$

the sector associated with $T_j$ does not contain the direction of any ray $OA_i$ with $i\neq j$. Consequently the point $A_i$ cannot belong to $T_j$ whenever $j\neq i$.

On the other hand, $A_i$ is a vertex of $T_i$, so $A_i\in T_i$.

Therefore

$$A_i\notin \bigcup_{j\ne i} T_j .$$

Thus each triangle $T_i$ contains a point, namely $A_i$, that is not contained in any of the other $99$ triangles. Hence no triangle $T_i$ is contained in the union of the remaining triangles.

We have constructed $100$ triangles for which none can be completely covered by the other $99$. The proposed statement is therefore false.

This completes the proof.

∎

Verification of Key Steps

The first delicate point is the assertion that every triangle $T_i$ lies inside its angular sector. A triangle is the convex hull of its three vertices. All three vertices lie in the closed sector bounded by the rays through $B_i$ and $C_i$. Every convex combination of points in a convex set remains in that set, and a sector is convex. Hence the whole triangle lies in the sector.

The second delicate point is the exclusion of $A_i$ from every other triangle. The direction of $OA_i$ differs from the direction of $OA_j$ by at least

$$\frac{2\pi}{100}=\frac{\pi}{50}.$$

Each triangle $T_j$ is confined to a sector of half-width

$$\delta=\frac{\pi}{300}.$$

Since

$$\frac{\pi}{50}>2\delta=\frac{\pi}{150},$$

the direction of $OA_i$ lies outside the entire sector containing $T_j$. Thus $A_i\notin T_j$.

A careless argument might say merely that the triangles are “thin” and point in different directions. Such wording does not prove that a vertex of one triangle cannot enter another. The comparison of the sector width $\pi/150$ with the directional separation $\pi/50$ is the exact quantitative fact needed.

Alternative Approaches

Instead of arranging the triangles around a circle, one may choose $100$ distinct directions from a common point and construct extremely long, narrow isosceles triangles whose apices are at that common point. Each triangle is concentrated in a tiny angular sector. If the sectors are pairwise disjoint except for the common apex, then a point near the far end of each triangle belongs to no other triangle. This again yields a counterexample.

The circular construction is preferable because the separation of directions is explicit and symmetric. The proof reduces to a simple comparison between the angular spacing of the rays and the angular width of the triangles.