Fix an integer $n\geq4$. Let $C_n$ be the collection of all $n$–point configurations in the plane, every three points of which span a triangle of area strictly greater than $1.$ For each configuration $C\in C_n$ let $f(n,C)$ be the maximal size of a subconfiguration of $C$ subject to the condition that every pair of distinct points has distance strictly greater than $2.$ Determine the minimum value $f(n)$ which $f(n,C)$ achieves as $C$ runs through $C_n.$ Radu Bumbăcea and Călin Popescu
Problem
Source: Spring Stars of Mathematics 2021 P4 (senior level)
Tags: combinatorics, romania
29.03.2021 22:25
Here is the official solution: The required minimum is $f(n)=\lceil n/3\rceil$ and is achieved, for instance, by the configuration described in the next block of four paragraphs. Let $m=\lceil n/3\rceil$ and consider the vertex set of $m+1$ equilateral triangles, $\Delta_1,\ldots,\Delta_{m+1},$ of side length $2$ each, which are translated copies of one another, widely and suitably spread in the plane. Here by widely it is understood that $\text{dist}(\Delta_i,\Delta_j)>2$ for all $i\neq j;$ and by suitably, that each $\Delta_i$ lies outside every forbidden area strip determined by a segment with one end point at a vertex of a $\Delta_j, \ j\neq i,$ and the other at a vertex of a $\Delta_k, \ k\neq i$ $($possibly, $j=k).$ This is possible, since admissible regions opening wider and wider to infinity always form in the complement of a finite number of strips. The removal of $3m-n+3$ vertices of $\Delta_{m+1}$ leaves a vertex configuration $C$ in $C_n.$ Choose one vertex from each $\Delta_i$ ($\Delta_{m+1}$ inclusive if $m<n/3$) to obtain a subconfiguration of $C$ of size $\lceil n/3\rceil,$ every two points of which are strictly more than $2$ distance apart. Clearly, every subconfiguration of $C$ of larger size contains points $2$ distance apart. Consequently, $f(n,C)\leq\lceil n/3\rceil$ so $f(n)\leq \lceil n/3\rceil.$ To show that $f(n)\geq \lceil n/3\rceil$ it is sufficient to prove that $f(n,C)\geq \lceil n/3\rceil$ for any configuration $C\in C_n$. Fix such a configuration $C$. For convenience, a segment of length at most $2$ will be referred to as a short segment; and a segment with both endpoints in $C$ will be referred to as a segment in $C$. Consider the short segment graph $G$ associated with $C$: the points of $C$ form the vertex set, and the short segments in $C$ form the edge set. We will show that $G$ is (vertex) $3$–colorable, i. e. the points of $C$ can be assigned one of three colors so that the endpoints of each short segment in $C$ are assigned distinct colors. The most frequently colored points then form a subconfiguration of at least $n/3$ points every two of which are strictly more than $2$ distance apart; that is, $f(n,C)\geq n/3.$ To prove $3$-colourability, induct on the number of vertices. For convenience, start with the trivial base case $n=3$. For the induction step, let $a$ be a vertex of $G$. If $\text{deg }a\leq 2$, then a colour is always available for $a$ to extend a valid $3$-colouring of $G-a$ to one of $G$. If $\text{deg }a\geq 3$, then $a$ has a neighbour $b$ such that the line $l$ through $a$ and $b$ leaves neighbours of $a$, and hence points of $C$, on either side. Let $H$ be the short segment graph associated with the subconfiguration consisting of $a, b$ and all points of $C$ on one side of $l$, and let $K$ be the short segment graph associated with the subconfiguration consisting of $a, b$ and all points of $C$ on the other side of $l$. Clearly, $H$ and $K$ are both subgraphs of $G$. Since the segment $ab$ is short, the area condition forces all points in $C - \{a, b\}$ to be strictly more than $1$ distance away from $l$. Consequently, every edge of $G$ is either one of $H$ or one of $K$, and the two share one single edge, namely, $ab$. (No edge crosses $l$.) By the induction hypothesis, $H$ and $K$ are both $3$–colourable. The previous paragraph shows that the restriction of any $3$-colouring of $H$ to $H - a - b$ and the restriction of any $3$-colouring of $K$ to $K - a - b$ always combine to provide a $3$-colouring of $G - a - b$. To obtain an overall $3$-colouring of $G$ from one of $H$ and one of $K$, it is therefore sufficient to make the two agree at both $a$ and $b$. To this end, perform at most two color swaps in one of them. This completes the argument and concludes the proof. Remark 1: The area condition implies that, if $ab$ and $ac$ are edges of $G$, then their lines of support form an angle (strictly) greater than $30^{\circ}$ and (strictly) less than $150^{\circ}$. Consequently, the degree of every vertex of $G$ is at most $5$. Without further work, however, this fact alone does not even imply $5$-colourability. In fact, the area condition implies that the line of support of an edge of $G$ hits no other edge unless the two edges hinge at a common vertex. In particular, no two edges cross, so $G$ is geometrically plane. At this stage, reference alone to the highly non-trivial four color theorem merely proves $4$-colourability. Using ideas in the last three paragraphs of the solution, it can be shown that $G$ has at most $2n - 3$ edges. It then follows that the average vertex degree does not exceed $4-6/n,$ so $G$ has a vertex of degree at most $3$. Again, without further work, this merely proves $4$-colourability without reference to the four color theorem. The authors suspect and are about to prove that $G$ has in fact at most $7n/5$ edges. If this is indeed the case, then the average vertex degree does not exceed $14/5 < 3,$ so $G$ has a vertex of degree at most $2,$ and $3$-colourability now follows at once. The short segment graph is not necessarily $2$-colourable, as the configuration described in the solution clearly shows. Remark 2: We exhibit two configurations, one in $C_4,$ and the other in $C_5,$ every three points of which span a triangle with at least one short side. Consequently, they both achieve the corresponding $f(n)$. Moreover, the short segment graph associated with each of these configurations is connected and has the largest possible number of edges. For any $n\geq 5$, using widely and suitably spread (translated) copies of the configuration in $C_5$ produces a configuration in $C_n$ whose short segment graph has at most $7n/5$ edges. For convenience, in what follows, a segment of length (strictly) greater than $2$ will be referred to as a long segment. The configuration in $C_4$ consists of the vertices of a lozenge of side length $2$ with an internal angular span of $60^{\circ}$ at some vertex. There are five short segments and one long segment. This configuration achieves $f(4)=2$. The short segment graph is connected and has the largest possible number of edges; it contains (two) triangles, so it is not $2$-colourable. The configuration in $C_5$ consists of the vertices of a convex pentagon $ABCDE$ such that $AB = AC = AD = AE = CD = 2$, $BE$ and $CD$ are parallel, and \[1 < \text{dist} (BE, CD) < \sqrt3 - 12(\sqrt6 - \sqrt2). \quad(\dagger)\]Before checking the area condition, we show that $BC<2$; by symmetry, $DE=BC<2$, accounting thus for another two short segments. The inequality $BC<2$ is equivalent to $\angle BAC < 60^{\circ}$. Letting $M$ be the midpoint of $B$E, the desired angular inequality follows from the fact that $\angle BAM$ is acute and $\angle CAM = 30^{\circ}$. We now check that every three vertices of the pentagon span a triangle whose area is strictly greater than $1$. By symmetry, the area condition is to be checked out only for the triangles $ABC, ABD, ABE, ACD, BCD$, and $BCE$. The first four triangles above span an area strictly greater than $1$, since their internal angular spans at $A$ all lie strictly between $30^{\circ}$ and $150^{\circ}$. Indeed, the smallest of these is $\angle BAC = \angle BAM - 30^{\circ}$, and the largest is $\angle BAE = 2\angle BAM$, so it is sufficient to show that $60^{\circ} < \angle BAM < 75^{\circ}$. Alternatively, but equivalently, $\sqrt3/2 > \text{cos} \angle BAM >(\sqrt6 -\sqrt2)/4$. To establish the latter, write $\text{cos } \angle BAM = AM/AB = AM/2$, and $AM = \text{dist}(A, CD)$ by $(\dagger)$ and $A_{BCE} > 1,$ since the $C$–altitude is strictly greater than $1,$ by $(\dagger),$ and \[BE = 2 BM = 2 AB \sin \angle BAM = 4 \sin \angle BAM > 4\sin 60^{\circ} = 2\sqrt3 > 2.\]Consequently, the vertices of the pentagon form a configuration in $C_5$. There are seven short segments, three long segments, and the triangle spanned by every three vertices has at least one short side. This configuration achieves $f(5) = 2$. The short segment graph is connected and has the largest possible number of edges; it is not $2$–colourable, since it contains triangles, such as $ABC, ACD$ and $ADE$.
31.03.2021 13:19
Nice and hard! I am going to present my solution, which is different from the official one. Although it shares some ideas with the authors' solution (mainly in exploiting the planarity of distance graph), it departs from it in two ways: 1) it actually proves that there is a vertex of degree at most $2$ (which is only hinted at in the notes of the official solution) and 2) it has something to say about the structure of the graph. Unfortunately, in this form, the solution can only prove an upper bound of $2n-3$ for the number of edges. Anyways, here is the solution: The answer is $\bigg\lceil\frac{n}{3}\bigg\rceil$. An example that proves that one can't do better than that is achieved by taking $\bigg\lceil\frac{n}{3}\bigg\rceil$ equilateral triangles of sidelength $2$ that are sufficiently far away from each other. We are now going to prove that one can always find $\bigg\lceil\frac{n}{3}\bigg\rceil$ points that are at distance more than $2$ apart from each other. Consider the graph $G$ induced by the segments of length at most $2.$ Then we must prove that $G$ contains an independent set of size at least $\frac{|V(G)|}{3}$. We prove this by induction on $n$. For $n=1,2,3$ this is obviously true, so assume $n\ge 4$ from now on. Suppose that the problem has been proved for any $m<n$ and we are trying to prove it for $n.$ If $G$ has a vertex $v$ of degree at most $2$, then by the induction hypothesis we know that $G-(\{v\}\cup N(v))$ contains an independent $I$ of size at least $$\frac{|V(G-(\{v\}\cup N(v))|}{3}=\frac{|V(G)|-1-\text{deg}(v)}{3}\ge\frac{|V(G)|-3}{3}.$$However, $I\cap N(v)=\emptyset$, so $\{v\}\cup I$ is an independent set of $G$ of size at least $1+\frac{|V(G)|-3}{3}=\frac{|V(G)|}{3}$, proving the problem. Thus, as long as $G$ has vertices of degree at most $2$, the claim follows from induction. Suppose now for the sake of contradiction that $G$ has minimal degree at least $3.$ The main idea will be the following: $G$ is not only planar, but also has the property that any two edges must meet at their extensions, while the condition that every vertex has degree at least three will force $G$ to have many edges that can't possibly maintain the interior intersection restriction. We first prove the interior intersection restriction: assume that $G$ contains two edges $\overline{AB}$ and $\overline{CD}$ such that the line $AB$ intersects the segment $\overline{CD}$ strictly in it's interior. Then $$[ACD]+[BCD]=\frac{|AB|\cdot |CD|\cdot\text{sin}(\angle(AB,CD))}{2}\le\frac{2\cdot 2\cdot 1}{2}=2$$implying that $\text{min}([ACD],[BCD])\le 1$, which contradicts the hypothesis! In particular, the segments $\overline{AB}$ and $\overline{CD}$ can't intersect at an interior point, proving the planarity of $G.$ As $G$ is planar, our graph naturally divides the plane into finite regions (possibly none) and one infinite region. A finite region that borders no other finite region will be called a "face". We will also call "faces" all the vertices of $G$ that are not contained in any finite region. Take note of this notion that should not be confused with the typical planar graph definitions: the standard is for the region bounded by a (minimal) cycle to be called a face, but here we rather focus on only the maximal cycles of $G$ and the regions that they enclose. We now turn to making observations about the structure of $G$. More concretely, we will prove that 1) every cycle (maximal or not) is convex; 2) no two faces can share a vertex; 3) and no face contains an interior point. The arguments that go into the proofs of those claims are entirely geometric. For the first one, assume that we find a nonconvex cycle. Nonconvexity implies the existence of two interior points (not necessarily vertices of the graph) $S$ and $T$ that determine a segment not completely inside the interior of the cycle. The segment $\overline{ST}$ then intersects and edge $\ell$ of the cycle. If the support line of $\ell$ wouldn't cross the interior of the cycle, then it would leave the whole cycle one one side of it, i.e. leaving $S$ and $T$ on one side of it. But then $\overline{ST}$ couldn't possibly intersect $\ell.$ Hence, the support line of $\ell$ crosses the interior of the cycle, meaning that it intersects another edge $\ell'$ of the cycle, either contradicting the interior intersection restriction or forcing the collinearity of three vertices of $G$, which would violate the area condition. The third claim follows directly from the interior intersection restriction: if a face with border given by a cycle $C$ contains any interior point $P$, then the support line of any edge of $P$ intersects $C$ in at least two points $Q$ and $R.$ By the interior intersection restriction we know that $Q$ and $R$ must be vertices of $G$, but then $[PQR]=0<1$, contradicting the problem's hypothesis! As for the second observation, suppose that two faces $F_1$ and $F_2$ have a common border vertex $X$. They can't have any common edge in $X$, as then $F_1$ and $F_2$ can be merged into a bigger face of $G.$ Let $\overline{XY},\overline{XZ}$ be the edges in $X$ along $F_1$, and $\overline{XU},\overline{XV}$ be the edges of $X$ along $F_2.$ Then either one of the lines $XY$ and $XZ$ crosses the interior of $\angle{UXV}$ or one of the lines $XU$ and $XV$ crosses the interior of $\angle{YXZ}.$ Without loss of generality, suppose that $XY$ crosses the interior of $\angle{UXV}.$ Then $XY$ crosses the interior of $F_2$; in particular, $XY$ crosses the border of $F_2$ (here we use the convexity of cycles: as the border cycle of $F_2$ is convex, the interior of angle $\angle{UXV}$ contains the whole cycle) at a point $W\neq X$. $W\neq Y$ as well, as if $F_1$ and $F_2$ have two common border vertices, we could merge those two faces into a bigger face of $G.$ Moreover, by the interior intersection restriction, $W$ must be a vertex of $G.$ Unfortunately, $[XYW]=0<1$ contradicts the problem's hypothesis! We now return to combinatorial arguments to prove that all of the above observations can't comply with the minimal degree condition. Suppose that $G$ has $k$ faces. Each edge of $G$ is either contained in a face or connects two distinct faces. Consider the graph $G'$ with the set of vertices given by the $k$ faces of $G$ and the edge set given by the edges of $G$ that connect two distinct faces (not that $G'$ might have multiple edges). If $G'$ contains a cycle consisting of vertices $F_1,F_2,...,F_m$, then those faces of $G$ may be merged into a bigger face, contradiction! In other words, $G'$ is acyclic, implying that it has at most $k-1$ edges, and, consequently, there is a vertex $F$ of degree at most one. If $F$ represents just a vertex of $G$, then it has degree at least three in $G$, and so degree at least three in $G'$ as well, contradiction! Thus, $F$ represents a nontrivial face of $G.$ By observation 3) from above, all interior edges of $F$ must be diagonals or edges of the border cycle. We may even add dummy edges until we obtain a triangulation by diagonals of the border cycle. But a classical result in combinatorial geometry states that any triangulation of a convex polygon (convexity is assured by observation 1) contains either at least two triangles of the partition that each has two common edges with the polygon or the initial polygon is a triangle, in which case we have no interior diagonals. Either way, there will be two distinct vertices of the border cycle that have no diagonals stemming from then. Deleting the dummy edges preserves this property. Then, since each such vertex has degree at least three in $G$, but only two of its edges are used to border $F$, each such vertex induces at least an edge in $G'$ that stems from $F$. Overall, $F$ must have degree at least two in $G'$, contradicting the choice of this vertex! In conclusion, we have reached a contradiction, proving that $G$ can't have minimal degree at least three. This ends our proof.
31.03.2021 16:26
huricane wrote: Nice and hard! I am going to present my solution, which is different from the official one. Although it shares some ideas with the authors' solution (mainly in exploiting the planarity of distance graph), it departs from it in two ways: 1) it actually proves that there is a vertex of degree at most $2$ (which is only hinted at in the notes of the official solution) and 2) it has something to say about the structure of the graph. Unfortunately, in this form, the solution can only prove an upper bound of $2n-3$ for the number of edges. Anyways, here is the solution: ... Impressive proof! ... as always.