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:
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.
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}$.
$\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}$
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.
$\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$
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.