Kvant Math Problem 1157

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

Problem

Three triangles—white, red, and green—have a common interior point $M$. Prove that it is possible to choose one vertex from each triangle so that the point $M$ lies inside or on the boundary of the triangle whose vertices are the chosen points of the three different colors.

Imre Bárány (Hungary)

Exploration

Let the three triangles be $T_W,T_R,T_G$, and let $M$ be a point lying in the interior of each of them.

Since $M$ is inside a triangle, every ray starting at $M$ meets the boundary of that triangle in exactly one point. Thus each triangle determines around $M$ three angular sectors corresponding to its vertices. If a vertex $A$ of a triangle is chosen, the set of directions from $M$ pointing into the cone bounded by the two sides through $A$ has angle less than $\pi$, because $M$ is interior to the triangle.

The desired conclusion is that one can choose a white, a red, and a green vertex whose convex hull contains $M$.

A standard characterization is useful: for points $A,B,C$, the point $M$ belongs to $\triangle ABC$ if and only if the three rays $MA,MB,MC$ are not contained in any open half-plane through $M$. Equivalently, the directions of $A,B,C$ around $M$ are not all contained in an arc of length $<\pi$.

This suggests translating the problem into a statement about points on a circle centered at $M$. Each triangle contributes three points on the circle. Because $M$ is inside the triangle, the three corresponding points are not contained in any semicircle.

Suppose, aiming at a contradiction, that every choice of one vertex from each color produces a triangle not containing $M$. Then every such triple of points on the circle lies in some open semicircle. The problem becomes purely circular.

The delicate step is to show that three color classes on a circle, each class consisting of three points not contained in a semicircle, must admit a rainbow triple that is not contained in any semicircle. This is essentially the planar case of Bárány's colorful Carathéodory theorem. In dimension $2$, however, a direct circular argument suffices.

Fix a white vertex. Since every rainbow triple is assumed bad, every red-green pair that together with this white point is chosen must lie in the semicircle opposite that white point. This imposes a strong separation of red and green points. Repeating the argument for different white vertices should force all red points into one semicircle, contradicting the fact that the red triangle contains $M$.

The core insight is that for a point $x$ on the circle, the set of points $y$ such that ${x,y,z}$ is contained in some semicircle is exactly a semicircle depending on $z$. Intersecting the constraints arising from three white vertices yields a common semicircle containing all red points or all green points, impossible.

Problem Understanding

We are given three triangles, colored white, red, and green, and a point $M$ lying in the interior of all three triangles. We must prove that one can select one vertex from each triangle so that the triangle formed by the three selected vertices contains $M$ in its interior or on its boundary.

This is a Type B problem: we must prove a stated existence theorem.

The difficulty is that the chosen vertices must come from three different triangles. Knowing that each individual triangle contains $M$ does not immediately relate the vertices of different colors. The essential task is to convert the condition "$M$ lies in a triangle" into a statement about directions around $M$, and then prove a combinatorial-geometric fact on the circle.

Proof Architecture

The first lemma states that for three points $A,B,C\neq M$, the point $M$ lies in $\triangle ABC$ if and only if the directions of the rays $MA,MB,MC$ are not contained in any open semicircle.

The reason is that $M\notin\triangle ABC$ precisely when a line through $M$ places all three vertices in the same open half-plane.

The second lemma states that if $M$ lies inside a triangle, then the three directions from $M$ toward its vertices are not contained in any semicircle.

The reason is an immediate application of the first lemma.

The third lemma states that if every rainbow triple of colored points on a circle is contained in some semicircle, then one color class is itself contained in a semicircle.

The proof uses the semicircle opposite a fixed point and a Helly-type argument on the circle.

The hardest part is the third lemma, because it is where the colorful condition must be converted into a contradiction with the fact that each color class comes from a triangle containing $M$.

Solution

Draw a circle centered at $M$. For every vertex $V$ of the three given triangles, let $v$ denote the intersection of the ray $MV$ with this circle. The vertices of each color thereby determine three points on the circle.

We begin with a standard characterization.

Lemma 1. Let $A,B,C\neq M$. Then $M\in\triangle ABC$ if and only if the points $a,b,c$ on the circle corresponding to $A,B,C$ are not contained in any open semicircle.

Proof.

Assume first that $a,b,c$ are contained in an open semicircle. The diameter bounding that semicircle determines a line through $M$. All three vertices $A,B,C$ lie in the same open half-plane bounded by this line. Hence $M$ cannot belong to $\triangle ABC$.

Conversely, suppose $M\notin\triangle ABC$. By the separating hyperplane theorem in the plane, there exists a line through $M$ such that all three vertices $A,B,C$ lie in the same open half-plane. The corresponding directions $a,b,c$ then lie in the open semicircle determined by that line. This proves the lemma.

Now consider any one of the original triangles, say the white triangle. Since $M$ lies in its interior, Lemma 1 implies that its three corresponding points on the circle are not contained in any semicircle. The same is true for the red and green triangles.

Thus we have three color classes $W,R,G$, each consisting of three points on the circle and not contained in any semicircle.

Suppose, for contradiction, that the theorem is false. Then every rainbow triple, consisting of one point from each of $W,R,G$, is contained in some semicircle.

Fix a white point $w\in W$. Let $I(w)$ be the closed semicircle centered at the point antipodal to $w$. A triple containing $w$ lies in a semicircle if and only if the other two points lie in a common semicircle of length $\pi$ whose boundary passes through $w$. Consequently every pair $r\in R$, $g\in G$ must satisfy

$$r\in I(w)\quad\text{or}\quad g\in I(w).$$

Indeed, if both $r$ and $g$ were outside $I(w)$, then the three points $w,r,g$ would wind around the circle through an angle exceeding $\pi$, and no semicircle could contain them.

Hence for each $w\in W$,

$$R\subseteq I(w)\qquad\text{or}\qquad G\subseteq I(w). \tag{1}$$

There are three white points. By the pigeonhole principle, at least two of them, say $w_1,w_2$, yield the same alternative in (1). Without loss of generality,

$$R\subseteq I(w_1),\qquad R\subseteq I(w_2).$$

Therefore

$$R\subseteq I(w_1)\cap I(w_2).$$

The intersection of two closed semicircles of the circle is again a closed arc of length at most $\pi$. Hence all red points lie in a semicircle.

This contradicts the fact proved above that the three red points are not contained in any semicircle.

The contradiction shows that our assumption was false. Therefore there exists a rainbow triple consisting of one white, one red, and one green vertex whose corresponding points on the circle are not contained in any semicircle.

Applying Lemma 1 to the original vertices, the triangle formed by those three chosen vertices contains $M$ in its interior or on its boundary.

This completes the proof.

∎

Verification of Key Steps

The first delicate point is Lemma 1. If $M\notin\triangle ABC$, one must justify the existence of a line through $M$ with all three vertices on the same side. Since $\triangle ABC$ is convex and does not contain $M$, a separating line exists. Translating this line parallel to itself until it passes through $M$ preserves the property that all three vertices remain in one open half-plane. This yields the required semicircle condition.

The second delicate point is the deduction of (1). Fix $w$. Suppose there exist $r\in R\setminus I(w)$ and $g\in G\setminus I(w)$. The complement of $I(w)$ is an open arc of length $\pi$ centered at $w$. Then $w,r,g$ cannot be contained in any semicircle, because any semicircle containing $w$ misses part of that opposite arc, while any semicircle not containing $w$ is impossible. Thus the rainbow triple $(w,r,g)$ would be good, contradicting the assumption.

The third delicate point is the use of two white points. From three white points, at least two force the same color class into their associated semicircles. The intersection of two semicircles is always an arc of length at most $\pi$. Hence that color class lies in a semicircle. A careless argument might overlook the possibility that the two semicircles coincide or meet only at endpoints; both cases still produce an arc of length at most $\pi$, which is enough for the contradiction.

Alternative Approaches

A more conceptual proof uses the planar case of the colorful Carathéodory theorem. Translate the picture so that $M$ becomes the origin. Each color class consists of three points whose convex hull contains the origin. Bárány's theorem states that from color classes whose convex hulls all contain the origin, one can choose one point from each class so that the origin belongs to the convex hull of the chosen points. In dimension $2$, the convex hull of three points is a triangle, giving the required conclusion immediately.

The proof above avoids invoking a general theorem. It reduces the problem to a statement about colored points on a circle and derives the result from elementary properties of semicircles and convexity. For a problem at the level of Kvant, this direct geometric argument is more self-contained.