useful?: In a graph with $n$ vertices, with degrees $d_1$,...,$d_n$, there exists an independent set of vertices of size at least $\sum \frac{1}{d_i+1}$

We define the fatness of a chord to be the shortest distance from one end of the chord to the other along the circumference of the circle. 

oneplusone wrote:

Good! And this lemma is an immediate consequence of Turan's lemma mentioned in 'theflowerking's post above! The lemma also has a probabilistic proof.

What does the ' independent set of vertices ' mean ?

A set of vertices with no edges between any two of them

Define the value of a chord to be the sum of the endpoints. The key claim is as follows: Claim: Given a circle with $3^k$ consecutive numbers there exists a set of $k \cdot 3^k$ chords such that any $2$ chords intersect only if their values are distinct. Proof: We induct on $k$. The base case $k = 0$ is trivial. Now consider a circle with $3^{k+1}$ consecutive numbers. Define $C_i$ as the sub-circle comprised of the $3^k$ numbers that are congruent to $i \pmod 3$. By the induction hypothesis there exists a set of $k \cdot 3^k$ chords for each sub-circle $C_i$ (after scaling and translating the numbers on each circle so they are consecutive). Label the chords between numbers in circle $C_i$ with the label $2i \pmod 3$. Observe that the value of each chord $\pmod 3$ is equal to its label and hence any $2$ chords that intersect must have different label. For every number $a$ on the circle draw a chord between it and the first number $b$ clockwise from $a$ such that $a \not \equiv b \pmod 3$ and label these chords with label $a + b \pmod 3$. Observe that any $2$ chords sharing an endpoint have distinct values and no $2$ of these new chords intersect anywhere but at endpoints. Also observe that if $a + b \equiv 2c \pmod 3$ and $a \not \equiv b \pmod 3$ then $a, b, c$ are all distinct modulo $3$. The clockwise arc from $a$ to $b$ contains only numbers congruent to $a \pmod 3$ and hence the chord from $a$ to $b$ cannot intersect any other chord with label $a + b \pmod 3$. Finally observe we have added exactly $3^{k+1}$ chords. Thus in total we have a set of $k \cdot 3^k + k \cdot 3^k + k \cdot 3^k + 3^{k+1} = (k + 1) \cdot 3^{k+1}$ chords so the induction is complete. We return to the problem. We have $3^{200} < 2^{500}$ and any circle with $3^{200}$ consecutive numbers must contain a set of disjoint chords of equal value with size at least $\frac{200 \cdot 3^{200}}{2 \cdot 3^{200}} = 100$. This completes the proof. $\blacksquare$

Probably one of the only cases (aside from USAMO 2011 P6) where straight-up averaging works. While this problem isn't exactly my type, the method of assigning weights has been a classic of math contests that this deserves a writeup (and a Motivation which shows the thought process behind the crucial Lemma).

We begin with some crucial observations (which need not be stated), but I think it's important to highlight and isolate what makes setting up the bound to be viable (in the first place.) $\color{green} \rule{5cm}{2pt}$ $\color{green} \clubsuit$ $\boxed{\textbf{Limited Intersections.}}$ $\color{green} \clubsuit$ $\color{green} \rule{5cm}{2pt}$ First, to avoid ambiguity, call a chord to have $\color{green} \textbf{\textit{color}}$ $k$ (abbreviated as $c_k$) if the sum of its endpoints is $k$ (we won't use the terms $\textit{value}$ or $\textit{length}$, and we will use their synonyms later.) Then, all chords from a particular vertex have different colors. Next, define the $\color{green} \textbf{\textit{reach}}$ $r$ of a chord to be the number of smaller arcs (of reach 1) which forms its minor arc. We Claim that each chord intersects at most $r-1$ other chords with the same color. $\color{green} \rule{25cm}{0.2pt}$ $\color{green} \spadesuit$ $\boxed{\textbf{Proof.}}$ $\color{green} \spadesuit$ The first one is obvious: the endpoint labelled with number $i$ will have chords of color \[ c_{i+1}, c_{i+2}, \ldots, c_{2i-1}, c_{2i+1}, \ldots, c_{i+N}, \]exactly one each. The second is easy but tricky to notice: observe that there are $r-1$ points in the minor arc of $\text{that}$ chord. Since any chord with $\text{the same color}$ that intersects that chord must consist of one of those vertices; and those vertices can only form one chord of $\text{that color}$, we obtain the desired conclusion. $\blacksquare$ Let $N = 2n = 2^{500}$. Moving on from the chord's properties, we assign a $\color{red} \textbf{\textit{value}}$ of $\frac{1}{r}$ to $\textbf{every}$ chord (this is the weight-assigning step). From here, we can define a color's value: add all the values of the chords having that color. $\color{red} \rule{4.6cm}{2pt}$ $\color{red} \clubsuit$ $\color{red} \boxed{\textbf{Value Pinpoint-ing.}}$ $\color{red} \clubsuit$ $\color{red} \rule{4.6cm}{2pt}$ There is a color $c$ with value at least $100$. $\color{red} \rule{25cm}{0.2pt}$ $\color{red} \spadesuit$ $\color{red} \boxed{\textbf{Proof.}}$ $\color{red} \spadesuit$ The total value of all chords is \[ N \cdot \left( \sum_{i=1}^{n-1} \dfrac{1}{i} \right) + \dfrac{N}{2} \cdot n \]which is more than \[ N \cdot [\ln{((n-1)+1)}] \]since $\frac{1}{1}+\frac{1}{2}+\ldots+\frac{1}{k} \geq \ln{(k+1)}$ by Riemann Integration.

Since there are only $2N-3$ colors (from $3$ to $2N-1$), a simple application of Pigeonhole Principle yields the conclusion; as \[ \dfrac{N \cdot \ln{2^{499}}}{2N-3} \geq 0.5 \cdot 499 \ln{2} \sim 172.94 \]$\blacksquare$ $\blacksquare$ To finish it off, we Claim that we can pick $100$ nonintersecting chords with the color $c$. After going this far, we already have our work cut out for us: consider a graph $G_c$ with its vertices consisting of chords of color $c$, and draw an edges between two vertices iff they intersect. Speaking generally, $\color{blue} \rule{5.7cm}{2pt}$ $\color{blue} \clubsuit$ $\color{blue} \boxed{\textbf{Single-Color Greedy Algo.}}$ $\color{blue} \clubsuit$ $\color{blue} \rule{5.7cm}{2pt}$ Given a graph $G$ with vertices of degree \[ (d_1,d_2,\ldots,d_{|V|}). \]Then, we can pick an independent set (set of vertices with no edge between them) with \[ v(G) = \sum_{i=1}^{|V|} \dfrac{1}{d_i+1} \]vertices. $\color{blue} \rule{25cm}{0.2pt}$ $\color{blue} \spadesuit$ $\color{blue} \boxed{\textbf{Proof.}}$ $\color{blue} \spadesuit$ Proceed as the official (or $\#3$'s) Solution. Pick the vertex $v_1$ with the smallest degree; and consider a new graph with $v_1$ and its neighboring vertices removed. We will analyze $v(G')$ (the value of the new graph, as computed in the Claim) in relation to $v(G)$. For $v_1$ and its neighbors $v_{i_1},v_{i_2},\ldots,v_{i_d}$ (with $d = d_1$ to simplify notations), we have that they have value $0$ (i.e. they are not included) in $G'$, and they have value \[ \dfrac{1}{d+1} + \sum_{j=1}^{d} \dfrac{1}{d_{j_i}+1} \leq (d+1) \cdot \dfrac{1}{d+1} \]in $G$. Moreover, the remaining vertices' degree will decrease, resulting in an increasing value from $G$ to $G'$. In total, $G'$ has a deficit of at most $1$ compared to $G$, and we have guaranteed the inclusion of $v_1$ in the independent set we intend to construct. We are done after exhausting all vertices in $G$. $\color{blue} \rule{25cm}{0.2pt}$ To solve the problem, we note that $v(G_c)$ is at least \[ \sum_{v \in G_c} \dfrac{1}{(r-1)+1} = \sum_{v \in G_c} \dfrac{1}{r} \geq 100 \]since each chord intersects at most $r-1$ other chords (abusing notation a bit here: the correct form should be $r_v$ for $v \in G_c$), implying that the chord's value is at least $\dfrac{1}{(r-1)+1}$. We are done. $\blacksquare$ $\blacksquare$ $\blacksquare$

Replace $n$ with $2^{499}$. Define the graph $G_k$ over vertices corresponding to chords with value $k$ and two vertices are adjacent if their corresponding chords intersect. Note that $k$ is always in $\{3, 4, \ldots, 4n-1\}$. We require the following two lemmas. Lemma 1 (Caro-Wei): In a graph $G$ on vertices $1, \ldots, n$ in which each vertex $i$ has degree $d_i$, there exists an independent set of vertices of size at least $\sum_{i=1}^n \frac{1}{d_i+1}$. Proof: Choose a permutation $\sigma$ of $[n]$ at random with uniform probability. Let $X$ be the number of vertices $k$ such that $k$ comes before any of the labels of vertices adjacent to $k$ in $\sigma$. The probability of $k$ satisfying this is $\frac{1}{d_i+1}$, so by Linearity of Expectation, $\mathbb{E}[X]=\sum_{i=1}^n \frac{1}{d_i+1}$, so there exists an independent set of vertices of size at least $\sum_{i=1}^n \frac{1}{d_i+1}$. $\square$ Lemma 2: For all $k \ge 1$, $\sum_{i=1}^k \frac{1}{i} \ge \ln(k+1)$. Proof: Use a Riemann sum to estimate $\int_1^{k+1} \frac{1}{x} dx$. $\square$ Lemma 1 implies that if the size of the largest independent set of $G_k$ is $I(G_k)$, then the average value of $I(G_k)$ is \[ \frac{1}{4n-3} \sum_{k=3}^{4n-1} I(G_k) \ge \frac{1}{4n-3} \sum_{i=3}^{4n-1} \sum_{j=1}^n \frac{1}{d_j+1}. \]Let $S$ be the set of points on the circle. Note that $\sum_{i=3}^{4n-1} \sum_{j=1}^n \frac{1}{d_j+1} = \sum_{v \in S} \frac{1}{\deg(v)+1}$. Now, for each chord $\ell$, let $f(\ell)$ be the number of points contained in its minor arc (not including $\ell$'s endpoints). In particular, $\ell$ can intersect at most $f(\ell)$ other chords. Note that there are exactly $2n$ chords $\ell$ with $f(\ell)=i$ for every $0 \le i \le n-1$, so there are at least $2n$ vertices with degree at most $i$. Thus \[ \frac{1}{4n-3} \sum_{v \in S} \frac{1}{\deg(v)+1} \ge \frac{1}{4n-3} \sum_{i=1}^n \frac{2n}{i} > \frac{1}{2} \ln(n+1). \]It can be computed that $\frac{1}{2} \ln(n+1) > 100$. Therefore, the average value of $I(G_k)$ is at least $100$, so there exists $G_m$ with $3 \le m \le 4n-1$ such that $G_m$ has an independent set of size at least $100$; the conclusion follows.

Basically, the entire problem boils down to one observation: Hey, big chords intersect one another, but small ones usually don't! :exploding_head: We proceed by performing a greedy algorithm on this heuristic (because when has greedy ever failed?): For each number, we build a set starting with the pair which sums to that number with minimal chord length. Then pick the next smallest pair that doesn't intersect all previous chords, and repeat this process. Repeat this set-building process for every number which can be written as the sum of some pair. Notice that during this process, a small distance chord is only skipped if one of its endpoints was contained between a chord that has already been chosen. A chord of distance $d$ can disqualify at most $d-1$ other chords this way. Now, define $a_i$ to be the number of distance $i$ chords which are counted in this process, then if we look exclusively at the set of chords with distance at most $k$, we obtain the double-counting inequality for every valid $1 \leq k \leq \frac{n-1}{2}$: $$\sum \limits_{i = 1}^k i \cdot a_i \geq kn$$ Now consider the minimum value of $\frac{a_1+a_2+\ldots+a_k}{2n - 3}$. Since we can smooth by minimizing $a_{i}$ and adding back the same value to $a_{i+1}$, it follows that at the minimum, by subtracting consecutive equations, $ka_k \geq n$ for all $1 \leq k \leq \frac{n-1}{2}$. Hence $\frac{a_1+a_2+\ldots+a_{\lfloor \frac{n-1}{2} \rfloor}}{2n-3} \geq \frac{1}{2} H_{\lfloor \frac{n-1}{2} \rfloor}$ Furthermore, notice again by double counting that some number must achieve at least this many disjoint chords in our greedy algorithm, so it suffices for us to have $\frac{1}{2} H_{\lfloor \frac{n-1}{2} \rfloor} \geq 100$ Since $H_n \geq 1 + \ln(n)$, it suffices for $n \geq 2^{2 + 200 \cdot \log_2(e)}$. Since $\log_2(e) \leq 2$, we have that $2^{500} \geq 2^{402} \geq 2^{1 + 200 \cdot \log_2(e)}$, finishing.

Inconsistent wrote: Basically, the entire problem boils down to one observation: Hey, big chords intersect one another, but small ones usually don't! :exploding_head: We proceed by performing a greedy algorithm on this heuristic (because when has greedy ever failed?): For each number, we build a set starting with the pair which sums to that number with minimal chord length. Then pick the next smallest pair that doesn't intersect all previous chords, and repeat this process. Repeat this set-building process for every number which can be written as the sum of some pair. Notice that during this process, a small distance chord is only skipped if one of its endpoints was contained between a chord that has already been chosen. A chord of distance $d$ can disqualify at most $d-1$ other chords this way. Now, define $a_i$ to be the number of distance $i$ chords which are counted in this process, then if we look exclusively at the set of chords with distance at most $k$, we obtain the double-counting inequality for every valid $1 \leq k \leq \frac{n-1}{2}$: $$\sum \limits_{i = 1}^k i \cdot a_i \geq kn$$ Now consider the minimum value of $\frac{a_1+a_2+\ldots+a_k}{2n - 3}$. Since we can smooth by minimizing $a_{i}$ and adding back the same value to $a_{i+1}$, it follows that at the minimum, by subtracting consecutive equations, $ka_k \geq n$ for all $1 \leq k \leq \frac{n-1}{2}$. Hence $\frac{a_1+a_2+\ldots+a_{\lfloor \frac{n-1}{2} \rfloor}}{2n-3} \geq \frac{1}{2} H_{\lfloor \frac{n-1}{2} \rfloor}$ Furthermore, notice again by double counting that some number must achieve at least this many disjoint chords in our greedy algorithm, so it suffices for us to have $\frac{1}{2} H_{\lfloor \frac{n-1}{2} \rfloor} \geq 100$ Since $H_n \geq 1 + \ln(n)$, it suffices for $n \geq 2^{2 + 200 \cdot \log_2(e)}$. Since $\log_2(e) \leq 2$, we have that $2^{500} \geq 2^{402} \geq 2^{1 + 200 \cdot \log_2(e)}$, finishing. Wait a minute... this is so clean :star_struck:

Assume points are equally spaced. Let the sum of a chord be the sum of the numbers on the endpoints. Let the length of a chord be the shortest angular distance between the endpoints, measured in $\tfrac{\pi}{2^{499}}$ radians. Thus, chords connecting adjacent points have distance $1$ and diametrically opposite points have distance $2^{499}$. $~$ Consider a set of chords $C$ for which the sum of the reciprocals of the lengths is greater than $k-1$ and none of them share an endpoint. We'll show that we can choose $k$ chords that are all pairwise disjoint. Draw a graph $G$ with chords as vertices and edge between vertices if two chords intersect. Let the degrees be $d_1,d_2,\dots,d_i$ and note that the degree of a vertex, or the number of other chords that intersect the chord the vertex corresponds to, is at most the length minus one because that's how many points there are in the minor arc. Therefore, \[\frac{1}{d_1+1}+\frac{1}{d_2+1}+\dots+\frac{1}{d_i+1}>k-1\]We remove the vertex with the smallest degree. WLOG it has degree $d_1$ then for our new graph, we decreased our weird sum by \[\frac{1}{d_1+1}+d_1\cdot \frac{1}{d_x+1}\]where $x$ is variable and doesn't matter and this is clearly at most $1$. Note that for all other terms in the sequence, the degree decreases so the fraction increases. Thus, for our new graph the sum of the reciprocals of the lengths is greater than $k-2$, so we're obviously done by induction. Now we globally compute the average value of this sum of reciprocals for each set of chords with the same sum. It is obvious that such a set does not have two chords that share endpoint. The total sum over all the chords is \[2^{500}\left(\frac11+\frac12+\frac13+\frac14+\dots+\frac{1}{2^{499}-1}\right)+2^{499}\cdot \frac{1}{2^{499}}>2^{500}ln(2^500)+1\]There are total of $2^{501}-3$ such sets, from $3$ to $2^{501}-1$. This means that the average value is at least \[250ln(2)+1>99\]so we done.