Several triangles are intersecting if any two of them have non-empty intersections. Show that for any two finite collections of intersecting triangles, there exists a line that intersects all the triangles. Proposed by usjl
Problem
Source: 2024 Taiwan Mathematics Olympiad
Tags: combinatorial geometry, Taiwan
sn6dh
31.01.2024 10:07
Take an arbitrary point $O$ as the origin, and $r$ be sufficient large such that all triangles are in the circle $C$ with center $O$ and radius $r$. For any point $P$ on $C$ and a triangle $T$, $f(P, T):=$ the set of $\theta$ such that the line that passes through $P$ with directed angle $\theta(0\leq\theta<\pi)$ (with respect to the tagent line of $P$ on $C$) passes through $T$. One can see that $f(P, T)$ is continuous, and since any two of the triangles $T_1, T_2$ in an interesting set have intersection, $f(P, T_1)\cap f(P, T_2)\neq\emptyset$. $\therefore t(P, S):=$ the intersection of $f(P, T)$ of all triangles $T$ in an interesting set $S$, and it is a non-empty continuous range. Let the two interesting sets be $S_1, S_2$. There are two cases: Case 1: $\forall T_1\in S_1, T_2\in S_2$, $T_1\cap T_2\neq\emptyset$. In this case $S=S_1\cap S_2$ is interesting, and from the above we know such line exists. Case 2: $\exists T_1\in S_1, T_2\in S_2$ such that $T_1\cap T_2=\emptyset$. In this case one can draw a line $L$ to separate $T_1, T_2$, and let $P_1, P_2$ be the two intersection of $L$ and $C$, one can see that $\max\{\theta\in t(P_1, S_1)\}<\min\{\theta\in t(P_1, S_2)\}$ and $\max\{\theta\in t(P_2, S_2)\}<\min\{\theta\in t(P_2, S_1)\}$, or vice versa. Since when moving $P$ from $P_1$ to $P_2$ on $C$, the change of $t(P, S_1)$, $t(P, S_2)$ are continuous, there exists a moment that $t(P, S_1)\cap t(P, S_2)\neq\emptyset$, and therefore such line exists.
Acclab
11.02.2024 15:25
Basically the proof above in a probably overly rigorous language.
The statement is trivial for point $P$ and a line segment $l$. Then picking the union of the intervals w.r.t. 3 edges of $T$ suffices.
Claim 1. For any point $P$ and an (finite) intersecting set $S$, the interval $\cap_{T \in S} I_{P, T}$ is nonempty.
By induction on $|S|$. $n=1$ is what we just stated above, and suppose for $|S|=k$ it holds. Assume on the contrary for $|S|=k+1$,
$$I_{P, S \setminus \{T\}} \cap I_{P, T} = \emptyset$$for some $T \in S$. Now let $I_{P, S \setminus \{T\}} = [l, r]$, we know some interval $T_l, T_r \in S$ give rise to these endpoints, that is, $l$, $r$ is the left-/right-endpoint of $T_l, T_r$. Write $I_{P, \{T\}} = [l', r']$. Since $I_{P, S \setminus \{T\}} \cap I_{P, T} = \emptyset$, we have that either $r' < l$ or $r < l'$, implying that either $T_r \cap I_{P, T} = \emptyset$ or $T_l \cap I_{P, T} = \emptyset$, both violating the fact they pairwise intersects.
Let the two intersecting sets be $S_1, S_2$. We can see the set of all points on all triangles is bounded, so we can draw a circle enclosing them, and denote $I_P = \cap_{T \in S_1} I_{P, T}$, $J_P = \cap_{T \in S_2} I_{P, T}$. Parameterize the points on circle with $\theta$. As $\theta$ varies from $0$ to $2 \pi$, $P$ moves along the circle at a constant speed as the interval $I_P$, $J_P$ also varies. Claim 2. Both endpoints of $I_P$, $J_P$ varies continuously.
First, as $\theta$ varies, the function of directed angle of line from $P$ to a fixed point in the circle is continuous. This can be derived from the continuity of trigonometric functions. If we replace a triangle with a line segment, the two endpoints of the interval of valid angles (the analogy "$l_{P, l}$") are precisely the angles from $P$ to the two vertices of line segment, up to order. Intersection of all the unions of the three intervals w.r.t the 3 edges of each triangle in $S_1, S_2$ gives $I_P$, $J_P$, but the function that maps $\theta$ to the endpoints are just a series of nested $\max$ and $\min$ of the continuous functions mentioned, which is continuous.
(Careful, though, as I did not fix a canonical choice of angles regarding the $2 \pi$ shifting. This is normally clear in context, especially since any fixed vertices of triangles occurs in the circle in this case, so the angle has a natural local bound. I do not know how to present this part rigorously now.)
Claim 3. As $\theta$ varies from $0$ to $2 \pi$, somewhere $I_P$ and $J_P$ intersects. Suppose $I_P$ and $J_P$ do not intersect for $\theta=0, 2\pi$- otherwise the proof ends. For $\theta=0$, draw a line through $P$ whose angle $\theta_0$ seperates the interval $I_P$, $J_P$. Let this line intersect the circle again at $P'$. Then for $\theta$ corresponding to $P'$, the anglular intervals $I_{P'}$ and $J_{P'}$ must have the greater/lower relation kept, as otherwise at some point they intersect by IVT. Suppose W.L.O.G. angles in $I_P$ are all greater than those in $J_P$. $I_{P'}$ then must have angles all greater than $J_{P'}$'s. It is then clear to see that, the lines through $P$ with angles $I_P$ and the lines through $P'$ with angles $I_{P'}$; and those of $J_P$ and $J_{P'}$ instead, cannot both intersect in circle while keeping angles in $I_P$ all greater than those in $J_P$. But they do intersect in circle, as their intersection contains the set of points on triangles $\in S_1$ and $\in S_2$. Claim 3 clearly finishes the problem.