Find the largest positive constant C such that the following is satisfied: Given n arcs (containing their endpoints) A1,A2,…,An on the circumference of a circle, where among all sets of three arcs (Ai,Aj,Ak) (1≤i<j<k≤n), at least half of them has Ai∩Aj∩Ak nonempty, then there exists l>Cn, such that we can choose l arcs among A1,A2,…,An, 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 C=1√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.