Taiwan IMO Selection Camp

The proof of this problem is based on the following fact.

Lemma. In a graph $G$, let the degree of vertex $v$ be $d_v$. Then $G$ contains an independent set $S$ consisting of some vertices satisfying $|S| \ge f(G)$, where
$$f(G) = \sum_{v \in G} \frac{1}{d_v + 1}.$$
Proof. We proceed by induction on the number of vertices $|G| = n$ of $G$. The base case $n=1$ clearly holds. In the inductive step, take a vertex $v_0$ in $G$ with the minimum degree $d$. Delete $v_0$ together with all its neighbors $v_1, \dots, v_d$, as well as all edges connected to these vertices, from the graph $G$, and call the resulting graph $G'$. By the induction hypothesis, $G'$ contains an independent set of vertices $S'$ satisfying $|S'| \ge f(G')$. Since none of the vertices in $S'$ are neighbors of $v_0$, $S = S' \cup \{v_0\}$ is an independent set of vertices in $G$.

Let the degree of vertex $v$ in $G'$ be $d_v'$. Clearly $d_v' \le d_v$ holds for every vertex $v$, and by the choice of $v_0$, $d_{v_0} \ge d$ holds for all $i=0, 1, \dots, d$. Thus we have
$$\begin{aligned} f(G') &= \sum_{v \in G'} \frac{1}{d_v' + 1} \ge \sum_{v \in G'} \frac{1}{d_v + 1} = f(G) - \sum_{i=0}^{d} \frac{1}{d_{v_i} + 1} \\ &\ge f(G) - \frac{d+1}{d+1} = f(G) - 1. \end{aligned}$$
Hence $|S| = |S'| + 1 \ge f(G') + 1 \ge f(G)$. Therefore the lemma holds by mathematical induction. $\square$

We return to the proof of the problem. For simplicity, let $n = 2^{2012}$, and draw all the chords determined by the $2n$ points on the circle. Color each chord according to the sum of the numbers at its two endpoints, which is one of $3, 4, \dots, 4n-1$ (think of each of $3, 4, \dots, 4n-1$ as a color). Two different chords sharing a common endpoint must have different colors. For each color $c$, consider the following graph $G_c$: its vertices are all the chords of color $c$; two chords are neighbors if and only if they intersect. Let $f(G_c)$ be the quantity defined by the formula in the lemma above.

Each chord $\ell$ divides the circle into two arcs, at least one of which contains $m(\ell) \le n-1$ of the given points. (Special case: if the two endpoints of $\ell$ are adjacent, then $m(\ell) = 0$.) For each $i = 0, 1, \dots, n-2$, there are $2n$ chords $\ell$ satisfying $m(\ell) = i$. Such a chord has degree at most $i$ in the graph of its color, for the reason that if $A_1, A_2, \dots, A_i$ are all the points on the arc determined by the chord $\ell$ with $m(\ell) = i$ and color $c$, then each point $A_j$ is the endpoint of at most one chord of color $c$, for $j = 1, 2, \dots, i$; hence at most $i$ chords of color $c$ intersect $\ell$.

From this it follows that for each $i = 0, 1, \dots, n-2$, the $2n$ chords $\ell$ satisfying $m(\ell) = i$ contribute at least $\frac{2n}{i+1}$ to the sum $\sum_c f(G_c)$. Summing $i$ from $0, 1, \dots$ up to $n-2$ gives
$$\sum_c f(G_c) \ge 2n \sum_{i=1}^{n-1} \frac{1}{i}.$$
Since there are a total of $4n-3$ colors, taking the average shows that there is at least one color $c$ satisfying
$$f(G_c) \ge \frac{2n}{4n-3} \sum_{i=1}^{n-1} \frac{1}{i} > \frac{1}{2} \sum_{i=1}^{n-1} \frac{1}{i}.$$
By the lemma above, there exist at least $\frac{1}{2} \sum_{i=1}^{n-1} \frac{1}{i}$ pairwise disjoint chords of color $c$; the sums of the numbers at the two endpoints of these chords are, of course, all equal to $c$. Finally, it only remains to verify that when $n = 2^{2012}$, $\frac{1}{2} \sum_{i=1}^{n-1} \frac{1}{i} \ge 500$. We have
$$\sum_{i=1}^{n-1} \frac{1}{i} > \sum_{i=1}^{2000} \frac{1}{i} = 1 + \sum_{k=1}^{2000} \sum_{i=2^{k-1}+1}^{2^k} \frac{1}{i} > 1 + \sum_{k=1}^{2000} \frac{2^{k-1}}{2^k} = 1001 > 1000.$$
This proves the problem.