Given an integer $d \ge 2$ and a circle $\omega$. Hansel drew a finite number of chords of circle $\omega$. The following condition is fulfilled: each end of each chord drawn is at least an end of $d$ different drawn chords. Prove that there is a drawn chord which intersects at least $\tfrac{d^2}{4}$ other drawn chords. Here we assume that the chords with a common end intersect. Note: Proof that a certain drawn chord crosses at least $\tfrac{d^2}{8}$ other drawn chords will be awarded two points.
Problem
Source: Polish Mathematical Olympiad finals 2021 P6
Tags:
fagot
09.05.2021 19:13
This problem is part of https://artofproblemsolving.com/community/c6h20662p135074 In the official solution this fact is formulated as a lemma.
alexiaslexia
16.05.2021 09:27
We Claim that $\dfrac{d^2}{4}$ can be strengthened into \[ C = \left\lfloor \dfrac{d-1}{2} \right\rfloor \cdot \left\lceil \dfrac{d-1}{2} \right\rceil + 2 (d-1) \]In other words, the constant is $k^2+3k-2$ when $d = 2k$ and $k^2+4k$ when $d = 2k+1$. $\color{green} \rule{25cm}{0.2pt}$ Here's a deceivingly simple way of finding the $\color{green} \text{chord}$.
(The ineq that comes with this argument might seem difficult, but it's $\textbf{definitely}$ not the main point, nor does it make the problem/solution more complicated than it already is.)
$\color{magenta} \rule{11cm}{2pt}$ $\color{yellow} \clubsuit$ $\color{red} \boxed{\textbf{A Very Nice Argument with a Very Ugly Computation.}}$ $\color{yellow} \clubsuit$ $\color{blue} \rule{11cm}{2pt}$
(The formulation of the Claim is the hardest part of the Solution, while the parts after this are just Finishing.)
We can, without loss of generality, assume that the endpoints form a regular polygon. Namely, the shortest distances between neighboring endpoints are all equal. After this $\textit{homogenization}$, select the $\left\lceil \dfrac{d}{2} \right\rceil^{\text{th}}$ shortest chord. We Claim that this chord intersects $C$ other chords.
(This formulation does not assume the regularity of the endpoints.)
Define the distance between two endpoints to be the minimal number of points in the two arcs connecting them. Then, we Claim that the chord with the $\left\lceil \frac{d}{2} \right\rceil^{\text{th}}$ smallest distance intersects with $C$ other chords.
$\color{green} \rule{25cm}{0.2pt}$ $\color{green} \spadesuit$ $ \boxed{\textbf{Proof.}}$ $\color{green} \spadesuit$ Let there be $a$ vertices between the minor ard of the $\left\lceil \frac{d}{2} \right\rceil^{\text{th}}$ smallest chord. For simplification, name the chord $XY$. Consider all the chords that $\textit{goes out}$ of those $a$ vertices. In total, we can count the intersections between those chords and $XY$ by substracting $a \cdot d$ with $\textbf{\textit{twice}}$ the total number of edges that stay between them. This is because for every edge that is $\textit{stuck}$, two points can be deducted from the total intersections with $XY$ (or, two less potential is achieved, in total.) However, we can bound the total deductions: between them, since the $i^{\text{th}}$ smallest chord must have at least $i$ distance (or it must have at least $i-1$ vertices in its minor chord), so there must be at most $a-i$ of them stuck inside the minor arc $XY$. Summing them, we must have at most \[ (a-1) + (a-2) + \ldots + \left(a - \left(\left\lceil \dfrac{d}{2} \right\rceil -1 \right)\right) \]So, the total number of intersections between the $a$ vertices and $XY$ is at least \begin{align*} \#\text{Intersections} &\geq ad-2 \left[ (a-1) + (a-2) + \ldots + \left(a - \left(\left\lceil \dfrac{d}{2} \right\rceil -1\right) \right) \right] \\ & = ad - 2 \left( \left\lceil \dfrac{d}{2} \right\rceil -1 \right)a + 2 \cdot \left(1+2+\ldots+\left( \left\lceil \dfrac{d}{2} \right\rceil - 1 \right) \right) \\ &\geq \left\lfloor \dfrac{d-1}{2} \right\rfloor \cdot \left( d - 2 \left\lceil \dfrac{d}{2} \right\rceil + 2 \right) + \left( \left\lceil \dfrac{d}{2} \right\rceil - 1\right) \cdot \left\lceil \dfrac{d}{2} \right\rceil \\ \end{align*}as $a \geq \left\lfloor \dfrac{d-1}{2} \right\rfloor$. When $d = 2k, 2k+1$, this value is evidently $k^2+k-2$ and $k^2+2k$, respectively. $\blacksquare$ $\blacksquare$ $\blacksquare$
In the above inequality, we have already counted $XY$'s intersections with its minor arc vertices. However, we $\textbf{do}$ have (uncounted) intersections which encompass the major arc vertices with $XY$. Note that we do not count (again) the chords which have one endpoint in both the major and minor arc.
(If we look closely, the intersections consist of (minor arc - $XY$); (minor arc - major arc); and (major arc - $XY$).)
So, $X$ and $Y$ considered, we have accounted their intersections with the $a$ vertices --- they must intersect at most
\[ \left( \left\lceil \dfrac{d}{2} \right\rceil - 1 \right) + \left( \left\lceil \dfrac{d}{2} \right\rceil - 1 \right) \ \text{times} \]and so they each have $d - \left\lceil \dfrac{d}{2} \right\rceil$ intersections left, not counting the one chord which form $XY$. In total, if $d = 2k,2k+1$, we have $2k$ uncounted intersections.
Summing those with what we already have earlier yields $(k^2+k-2) + 2k$ and $(k^2+2k) + 2k$ intersections for $d = 2k,2k+1$. We are done. $\color{blue} \blacksquare$ $\color{blue} \blacksquare$ $\color{blue} \blacksquare$
After writing this up, I think the main obstacle of this problem is to find a particular chord (local choice) without relying too much on other chords' positions (so that the local choice works however the remaining endpoints expend their $d$ chords.)
I also realized that in configurations where the equality isn't rather tight, a lot of possible chords can be chosen to intersect $C$ other chords: one can pick the smallest chord which contains $\geq \left\lceil \dfrac{d}{2} \right\rceil - 1$ points, and in some cases, the $\left\lceil \dfrac{d}{2} \right\rceil -1$ or $\left\lceil \dfrac{d}{2} \right\rceil +1$ smallest chord might work too.
$\color{green} \rule{25cm}{2pt}$
$\color{red} \text{Sec 1: Possible} \ \textit{shapes} \ \text{the chords can form (with each other).}$ Looking at smaller groups of endpoints (or vertices) and chords (or edges), I noticed that there is hardly any lead on forcing many other (read: $\frac{d^2}{4}$) other chords to intersect with it. For example, either a cycle, a star graph, or just plain bipartite graphs do not need to exist, and if they do, the other chords may be tailored to avoid intersecting too much with them.
The only lead, for me, was to consider one particular vertex (or a pair of them) and hopefully pray that the middle chord (the one that is likely to intersect more chords) intersects sufficiently enough by PHP or double counting. However, the sheer quantity of vertices made it almost impossible to individually look at the vertices, without somehow looking at the whole configuration.
Speaking of whole configurations, I thought it'd be nice to say that $\textbf{every two vertices}$'s chord must lie in a particular component; so I tried to divide the whole config into components; and assume that the components do not intersect each other.
This makes for a good starting point (side note: this technique is more used to establish the final contradiction: see Serbia MO 2020 - 2 and IMO 2020 P3) but this doesn't warrant anything more than the existence of a spanning tree here. From experimentation, the ones with potential for many intersections are the zigzag ones in the form of
\[ A_1 - A_2 - \dots - A_k \]where $A_4$ lies in the opposite half-plane with $A_1$ in regards to $\overline{A_2A_3}$; $A_5$ in opposite with $A_1,A_2$, and so on. This is very nice because the whole circle is $\textit{divided into regions}$, with a guarantee of intersections in regions with a lot of $\textit{distance}$.
However, looking at distance only (in the context of spanning trees) presented a problem: what if it is $\textsf{exactly}$ isomorphic: but for every edge $A_i - A_{i+1}$, all other vertices lie in the same half-plane? This renders $\textit{two}$ degree from each vertex useless, and I thought it might be better off reducing an at-least-$d$-regular graph into a $d-1$ sized one.
The conclusion I got from here was that the graph $\textbf{must}$ be simple, distance and middle chords are good, and considering whole configs (spanning trees, cycles, star graphs) does more harm than good.
$\color{green} \rule{25cm}{2pt}$
$\color{red} \text{Sec 2: Small edges, and the next smallest edge.}$ From here, I tried the next idea of complementing the intersections: if we are tasked to bound the existing intersections between chords; what would happen if we tried to maximize the non-existing intersections between chords? Here I tried to draw the intersections of any two chords, including the ones that meet $\textit{outside}$ the circle (and the chord itself).
Again, here I observed that the smaller chords are better off un-picked; and this is all the more reason to just add them in case they are $\textbf{not picked}$. This makes a pretty interesting circular argument on why all edges of $\textbf{distance 1}$ should be drawn nonetheless --- and here came the idea to homogenize all vertices and define distance as the regular arc-distance (instead of the contrived $\textsf{number of edges one needs to traverse}$ to reach the other vertex.)
The final blow to the problem was struck once I was comfortable enough to look at the equality when $n > d+1$; it's pretty easy to construct a config with $d = 4$ and $12$ endpoints, for example. Granted, this doesn't have exactly $\frac{d^2}{4}$ vertices, but it at least shares the same $C$ intersections (in the middle chords) with the case of $d+1$ vertices.
And as one might expect, since considering the smallest-distance chords does no good, I thought it might be a great idea to consider chords of length $2$ --- and the one vertex (here $a = 1$) in the middle will lead to success iff $d = 3$ or $d = 4$. So, for larger $d$ I could just pick the $\left\lceil \dfrac{d}{2} \right\rceil$ smallest vertex, and the rest is just finishing the ineq (which isn't easy either, but I hope the explanation in $\color{green} \spadesuit$ $\boxed{\textbf{Proof}}$ $\color{green} \spadesuit$ does it justice.)
\[\begin{tabular}{p{12cm}}
$\rule{4cm}{0.5pt} \hspace{1cm} \blacksquare \hspace{1cm} \rule{4cm}{0.5pt}$ \\
\end{tabular} \\ \]
Piortek
30.03.2024 19:31
A proof for two points: Call the size of a chord the number of points that are in between its ends. Choose the smallest choose whose size is more than $\frac{d}{4}$. In case, there are more than one of those, choose arbitrarily. Label one of its ends $A_0$ and from then on label the points clockwise $A_1,...,A_t$. This chord is now $\overline{A_0A_n}$ where $n>d/4$. It should be obvious that if $0<k<n$ then chords $\overline{A_kA_l}$ and $\overline{A_0A_n}$ intersect if and only if $l=0$ or $l \geq n$. Let $I(s)$ be the numbers of chords whose end is $A_s$ and intersect $\overline{A_0A_n}$. Similarly, let $N(s)$ be the number of non-intersecting chords. We know that $I(s)+N(s) \geq d$. Now, for $0<s<n$ we have $N(s) \leq \frac{d}{2}$, since the second end of every non-intersecting chord must be $A_{s+t}$, where $-\frac{d}{4}\leq t \leq \frac{d}{4}$, $t \neq 0$, since there can't be any chord of size greater than $\frac{d}{2}$, whose ends are in the range $\left \lbrace A_1,...,A_{n-1} \right \rbrace$ and the second end must be one of the points in this range. It means that for every such point $I(s) \geq d-N(s) \geq d-\frac{d}{2}=\frac{d}{2}$. Moreover, we know that in the sum $I(1)+\cdots+I(n-1)$ no chord is counted twice because its second end is not in the range $\left \lbrace A_1,...,A_{n-1} \right \rbrace$. We know as well that $I(0) \geq d$, $I(n) \geq d$ and that in the sum $I(0)+\cdots+I(n)$ no more than $2n$ chords are counted twice (because there are at most $n$ chords whose ends are $A_0$ and one of the points $A_1,...,A_n$ and there are at most $n$ chords whose ends are $A_n$ and one of the points $A_0,...,A_{n-1}$). We have that the numbers of intersections is at least: $$I(0)+I(1)+I(2)+\cdots + I(n) - 2n \geq (n-1)\cdot \frac{d}{2} +2(d-n) =n(\frac{d}{2}-2)+\frac{3}{2} d> \frac{d^2}{8}+d>\frac{d^2}{8}$$and the proof is complete.