Common intersection of arcs

Art of Problem Solving

AoPS Online

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

No tags match your search

M

Common intersection of arcs

G H J

Reveal topic tags

L

G H BBookmark kLocked kLocked NReply

Source: 2020 CMO P4

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

179 posts

#1 h Nov 27, 2019, 6:42 AM • 1 Y

Y by Adventure10

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.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

89 posts

#2 h Nov 27, 2019, 5:31 PM • 4 Y

Y by Math5000, rashah76, PIartist, Adventure10

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] 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]$

becomes

$[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]$

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$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

578 posts

#4 h Nov 27, 2019, 7:47 PM • 3 Y

Y by Pure_IQ, qubatae, Adventure10

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$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

206 posts

#5 h Nov 27, 2019, 11:10 PM • 2 Y

Y by Adventure10, Mango247

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.

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a