Find the largest positive constant $C$ such that the following is satisfied: Given $n$ arcs (containing their endpoints) $A_1,A_2,\ldots ,A_n$ on the circumference of a circle, where among all sets of three arcs $(A_i,A_j,A_k)$ $(1\le i< j< k\le n)$, at least half of them has $A_i\cap A_j\cap A_k$ nonempty, then there exists $l>Cn$, such that we can choose $l$ arcs among $A_1,A_2,\ldots ,A_n$, whose intersection is nonempty.
Problem
Source: 2020 CMO P4
Tags: combinatorics
27.11.2019 20:31
Are you sure this is correct? Seems far too easy for a China P4. We claim the answer is $\boxed{C = \frac{1}{\sqrt 6}}$. In particular, let $M$ be the maximum number of arcs with nonempty intersection. We will show that \[ n\binom {M-1}{2} \geq \frac 12\binom n3. \tag{$\clubsuit$} \]Indeed, it suffices to show that there are at most $n\binom{M-1}{2}$ triples with $A_i\cap A_j\cap A_k$ nonempty. Also, note that if the arcs have common endpoints, we can shift them so that the endpoints are no longer common: [asy][asy] D((-2,0) -- (0,0), orange); D((-2,0.25)--(0,0.25), red); D((0,-0.25)--(2,-0.25),green); D((0,-0.5)--(2,-0.5),blue); D((0,0), orange); D((0,.25), red); D((0,-.25),green); D((0,-.5), blue); [/asy][/asy] becomes [asy][asy] D((-2,0) -- (.15,0), orange); D((-2,0.25)--(.3,0.25), red); D((-.15,-0.25)--(2,-0.25),green); D((-.3,-0.5)--(2,-0.5),blue); D((.15,0), orange); D((.3,.25), red); D((-.15,-.25),green); D((-0.3,-.5), blue); [/asy][/asy] Note that for $S\subset [n]$, \[ \bigcup_{i\in S} A_i \neq \varnothing \]holds after the change if and only if it holds before. Thus this is valid. Now, suppose we walk around the circle, keeping track at every point of how many arcs contain the circle. This number $\chi$ never exceeds $M$. Now, we will count the number of intervals $I$ that shows up as a connected component of $A_i \cap A_j \cap A_k$ (which might be multiple intervals). WLOG let $A_k$ be the ``clockwise end" of the interval (we count unordered triples instead of triples with $i < j < k$). Then, whenever we cross an endpoint to end up on a new arc $A_k$, we note that if we are currently on $\chi$ arcs, then there are $\chi-1$ arcs that could be $A_i, A_j$, which gives us \[ \binom {\chi-1}{2}\leq \binom {M-1}{2} \]possible intervals with the current arc as $A_k$. This gives us at most $n\binom {M-1}{2}$ intervals and thus at most that many unordered triples $(i,j,k)$. Thus, $(\clubsuit)$ is true. It follows that $(M-1)(M-2) \geq (n-1)(n-2)/6$. Since $\left(\frac{n}{\sqrt 6} -1\right)\left(\frac n{\sqrt 6} - 2\right) < \frac{(n-1)(n-2)}{6}$, this forces $M > \frac n{\sqrt 6}$ indeed. To show that $C > \frac{1}{\sqrt 6}$ is impossible, simply note that if we let $P_1\cdots P_{2n}$ be regular, then if we let $M$ be such that $(\clubsuit)$ is true, then let $A_i$ be $P_{2i} \to P_{2i+2M-1}$ where indices are taken modulo $2n$. Then, we indeed have $n\binom{M-1}{2}$ triples $(i,j,k)$. In this case, we get that as long as $M \geq {n-1}{\sqrt 6} + 2$, the construction works, so $M = \left \lceil \frac{n-1}{\sqrt 6} + 2\right\rceil$ works and so $C > \sqrt{1}{\sqrt 6}$ fails. $\Box$
27.11.2019 22:47
We claim that the answer is $c = \frac{1}{\sqrt 6}$. First let's show that $c \ge \frac{1}{\sqrt 6}$. To do this, consider any $n$ arcs which satisfy the condition of the problem. As in above, we may assume that the $2n$ endpoints of the arcs are $2n$ distinct points. Now, let's label the points $P_1, P_2, \cdots, P_{2n}$ in clockwise order. Let $P_i$ be on $d_i$ arcs, for each $1 \le i \le 2n.$ We wish to show that $d_i \ge \frac{n}{\sqrt{6}}$ for some $i.$ If not, then we have that $\sum \binom{d_i}{2} \le 2n \cdot \frac{\frac{n^2}{6} - \frac{n}{\sqrt6}}{2}$. However, this is also equal to $\sum |A_i \cap A_j|$, where $A_i \cap A_j$ denotes the intersection of two intervals. Notice that any arc $A_k$ which has an endpoint in $A_i \cap A_j$ has the property that $A_i, A_j, A_k$ have a nonempty intersection (that endpoint is in all three arcs). In this case, we will say that $(i, j)$ counts the triple $A_i, A_j, A_k.$ So we know that $(i, j)$ counts at most $|A_i \cap A_j|-2$ triples (the $-2$ because we $A_k$ can't share an endpoint with $A_i$ or $A_j$). We claim that each triple $(A_i, A_j, A_k)$ of arcs with nonempty intersection is counted at least twice. This is obvious. From here, it's clear that the triples are counted a total of at least $\binom{n}{3}$ times. Hence $\binom{n}{3} \le (\sum |A_i \cap A_j| ) - n(n-1) = \sum \binom{d_i}{2} - n(n-1).$ However, $\binom{n}{3} > 2n \cdot \frac{\frac{n^2}{6} - \frac{n}{\sqrt6}}{2} - n(n-1),$ so the above stuff gives a contradiction. To see that $\frac{1}{\sqrt6}$ cannot be improved, use the same construction as above. $\square$
28.11.2019 02:10
First we can adjust the endpoints such that they don't coincide (move the endpoint "over" by a small distance). Then every connected intersection arc contains two distinct endpoints. (Note that the intersection of several arcs can be multiple disjoint arcs.) Consider an endpoint $a_i$ of an arc $A_i$. Suppose $a_i$ is covered by $c$ arcs, then $c\le Cn$. Counting the number of ordered triples $(A_i,A_j,A_k)$ such that their intersection is non-empty, we have the following inequality: $$\frac{n(n-1)(n-2)}{12}\le \#(triples)\le n\binom{Cn-1}{2} =\frac{n(Cn-1)(Cn-2)}{2},$$which implies $C\ge\frac{1}{\sqrt{6}}$. To see that $C$ can't be larger than $\frac{1}{\sqrt{6}}$, consider the case where each arc covers $\left\lceil\frac{1}{\sqrt{6}}\right\rceil+2$ endpoints (including its own) and each endpoint is covered by $\left\lceil\frac{1}{\sqrt{6}}\right\rceil + 1$ arcs.