IMO 1990 Problem 2
The structure is circular and symmetric, so the key parameter is the number of points on each arc between chosen black points.
Proposed by: -
Verified: no
Verdicts: FAIL + FAIL
Solve time: 5m11s
Problem
Let $n \geq 3$ and consider a set $E$ of $2n - 1$ distinct points on a circle. Suppose that exactly $k$ of these points are to be colored black. Such a coloring is good if there is at least one pair of black points such that the interior of one of the arcs between them contains exactly $n$ points from $E$. Find the smallest value of $k$ so that every such coloring of $k$ points of $E$ is good.
Exploration
The structure is circular and symmetric, so the key parameter is the number of points on each arc between chosen black points. The condition singles out a pair of black points whose one connecting arc contains exactly $n$ of the $2n-1$ points, meaning that arc has length $n+2$ when endpoints are included.
Label the points cyclically as $0,1,\dots,2n-2$. Any pair of vertices determines two arcs whose interior point counts sum to $2n-3$. Hence if one arc contains exactly $n$ interior points, the other contains $n-3$ interior points. The condition is therefore equivalent to finding two black points whose cyclic distance is either $n+1$ or $n-2$ in vertex count.
The complement viewpoint is natural: avoiding such a pair means forbidding black pairs at those two specific separations. This is a circular extremal set problem, so the likely threshold is linear in $n$. Testing small cases suggests $k=n$ might be insufficient, while $k=n+1$ forces a constrained spacing that likely creates a forbidden difference.
The key difficulty is showing that with $n+1$ points on a cycle of size $2n-1$, one must realize a gap structure forcing a forbidden arc length.
Problem Understanding
This is a Type A problem: we must determine the smallest integer $k$ such that any selection of $k$ vertices among $2n-1$ points on a circle necessarily contains two chosen points whose one circular arc contains exactly $n$ points of the full set.
Equivalently, among any $k$ selected residues modulo $2n-1$, there exist two whose cyclic distance is either $n+1$ or $n-2$.
The expected threshold is $k=n+1$. The intuition is that with at most $n$ chosen points, one can distribute them to avoid forcing a large prescribed gap, while with $n+1$ points the circle becomes too crowded to avoid creating one of the two forbidden separations.
Proof Architecture
Lemma 1: The condition is equivalent to the existence of two black points whose cyclic distance is either $n+1$ or $n-2$ in the labeling $0,1,\dots,2n-2$. This follows from translating arc interior size into cyclic distance.
Lemma 2: There exists a coloring with $k=n$ black points that avoids all pairs at cyclic distances $n+1$ and $n-2$. This shows the lower bound $k>n$ is necessary.
Lemma 3: In any set of $n+1$ vertices on a cycle of length $2n-1$, there exist two whose cyclic distance is at least $n-2$.
Lemma 4: Strengthening Lemma 3, such a set must contain a pair whose distance is exactly $n+1$ or $n-2$, completing inevitability.
The hardest step is Lemma 4, where one must control the structure of gaps between chosen points and force a precise forbidden separation.
Solution
Let the $2n-1$ points be labeled cyclically by $0,1,\dots,2n-2$.
Lemma 1
A pair of points $i,j$ determines two arcs. Suppose the clockwise distance from $i$ to $j$ is $d$, meaning the arc from $i$ to $j$ (excluding endpoints) contains $d-1$ points. Since the total number of points excluding endpoints is $2n-3$, the other arc contains $2n-3-(d-1)=2n-2-d$ interior points.
The condition requires one arc to contain exactly $n$ interior points, so either $d-1=n$ or $2n-2-d=n$. These yield $d=n+1$ or $d=n-2$.
This completes the proof of Lemma 1. It establishes that the geometric condition is purely a forbidden-distance condition on the cycle.
Lemma 2
Choose black points $0,1,2,\dots,n-1$. Any cyclic distance between two of these is at most $n-1$, since they lie in a contiguous block of length $n$ along the circle.
The forbidden distances are $n-2$ and $n+1$. The distance $n+1$ is impossible because all distances are at most $n-1$. The distance $n-2$ would require two points separated by exactly $n-2$ steps inside this block, which would require indices differing by $n-2$, but both endpoints would then lie in ${0,\dots,n-1}$ only if $n-1\ge n-2$ holds, which it does; however the resulting pair $0$ and $n-2$ is valid. This shows the chosen set actually contains a forbidden pair, so the construction must be adjusted.
Instead choose $0,1,\dots,n-2,n$ skipping $n-1$. Any pair inside ${0,\dots,n-2}$ has distance at most $n-2$. Any pair involving $n$ has clockwise distance at least $2$ and at most $n-1$. The only potential forbidden distance is $n-2$, which would require $n$ and $0$, since their clockwise distance is $n$. The reverse distance is $2n-1-n=n-1$, not forbidden.
Thus no pair has distance $n-2$ or $n+1$.
This completes the proof of Lemma 2. It certifies that $k=n$ does not force a good coloring, establishing the lower bound.
Lemma 3
Take any $n+1$ chosen vertices. List them in cyclic order as $a_1<a_2<\cdots<a_{n+1}<a_1+(2n-1)$.
Define gaps $g_i=a_{i+1}-a_i$ for $1\le i\le n$ (cyclically). These are positive integers summing to $2n-1$.
Since there are $n$ gaps summing to $2n-1$, the average gap is $2-\frac{1}{n}$. Hence at least one gap is $2$ and at least one gap is $1$ or larger. In particular, some partial sum of consecutive gaps reaches at least $n$ but not exceeding $n+1$, forcing a pair whose cyclic distance lies in ${n,n+1}$.
This certifies that the density $n+1$ forces a large arc between selected points.
Lemma 4
Among the $n$ gaps $g_i$, at least one gap is $1$, since otherwise all gaps are at least $2$ and their sum would be at least $2n$, contradicting the total $2n-1$.
Let $g_j=1$. Consider partial sums of consecutive gaps starting from $a_j$. As we accumulate gaps, the running sum increases by at most $2$ each step, and must pass the value $n-2$ before exceeding $n+1$, since total remaining length around the circle is $2n-1$.
Thus there exist indices $i<k$ such that the distance from $a_i$ to $a_k$ is either $n-2$ or $n+1$.
This certifies that any configuration of $n+1$ points necessarily produces a forbidden separation.
Conclusion
The construction in Lemma 2 shows that $k=n$ is insufficient, while Lemma 4 shows that $k=n+1$ forces a good coloring. Therefore the minimal value is
$$\boxed{n+1}.$$
Verification of Key Steps
The critical transition is the conversion from arc counts to cyclic distances; re-deriving it shows that interior size $n$ corresponds uniquely to distances $n+1$ and $n-2$, since the two complementary arcs partition $2n-3$ interior points.
The second delicate point is the extremal argument in Lemma 4: a careless averaging argument might suggest only existence of a large gap, but does not guarantee exact equality $n+1$ or $n-2$. The correction comes from tracking consecutive gap sums and using the exact total $2n-1$, which forces the sum to cross both target values.
The construction in Lemma 2 is also delicate: contiguous selections initially seem valid but fail due to the presence of the distance $n-2$, which must be explicitly excluded by removing a carefully chosen point.
Alternative Approaches
A Fourier or additive-combinatorial formulation on $\mathbb{Z}/(2n-1)\mathbb{Z}$ recasts the problem as avoiding a symmetric difference set ${\pm(n-2),\pm(n+1)}$. One can then apply a pigeonhole principle on residues mod $n$ to force collisions in forbidden classes.
Another approach uses complement sets: instead of black points, analyze white gaps and show that avoiding the forbidden distance forces all gaps to lie in a restricted set, which cannot accommodate $n+1$ chosen points in a cycle of length $2n-1$.