Kvant Math Problem 798
Consider first small values of $k$.
Verified: no
Verdicts: SKIP + SKIP
Solve time: 7m25s
Source on kvant.digital
Problem
On a circle, $4k$ points are marked and colored alternately red and blue; then $2k$ of the red points are arbitrarily connected in pairs by $k$ red segments, and $2k$ of the blue points by $k$ blue segments (no three segments intersect at a single point). Prove that there are at least $k$ points of intersection between the red and blue segments.
S. V. Fomin
Exploration
Consider first small values of $k$. For $k=1$, there are four points alternating red and blue. Connecting two red points by a red segment and two blue points by a blue segment produces exactly one intersection. For $k=2$, eight points are placed alternately around the circle. Various pairings of the red points and the blue points can be attempted. Arranging all red segments consecutively and all blue segments consecutively along the circle yields two intersections, suggesting the lower bound equals $k$. Trying to reduce intersections by “nesting” segments or avoiding crossings quickly fails because each red segment must cross at least one blue segment to reach a blue point opposite in the alternating order. Observing the general pattern, the number of red-blue intersections cannot be smaller than $k$ because each red segment separates the circle into two arcs, each containing at least $k$ blue points, guaranteeing that at least one blue segment crosses it. The crucial point is formalizing why each red segment must intersect at least one blue segment and why the total number of intersections cannot drop below $k$ regardless of how the segments are paired.
Problem Understanding
There are $4k$ points on a circle colored alternately red and blue. Exactly $2k$ red points are paired into $k$ red segments and exactly $2k$ blue points into $k$ blue segments. No three segments intersect at a single point. The task is to prove that there are at least $k$ intersections between red and blue segments. This is a Type B problem: the statement is given and must be proved. The core difficulty lies in demonstrating a global lower bound on intersections purely from the combinatorial constraints, independent of the specific pairing of points. Intuitively, the alternation of colors ensures that every red segment separates blue points, enforcing intersections. The minimum occurs when segments are “maximally nested” along the circle so that no two segments of the same color intersect each other, and every red segment intersects exactly one blue segment.
Proof Architecture
Lemma 1 states that each red segment divides the circle into two arcs, each containing exactly $k$ red points, implying each arc contains $k$ blue points. This follows from the alternation of colors and the even distribution of points. Lemma 2 asserts that each red segment must intersect at least one blue segment, because the blue points are distributed such that each red segment separates them into two groups, so any blue pairing connecting points from different sides must cross the red segment. Lemma 3 ensures that the total number of red-blue intersections is at least $k$, which follows by counting intersections via induction or combinatorial parity: each red segment intersects at least one blue segment, and no intersection is counted more than once due to the no-three-intersections condition. The hardest step is Lemma 2, as it requires a precise argument for the unavoidable crossing of segments, and a careless geometric reasoning may underestimate intersections.
Solution
Label the $4k$ points around the circle consecutively $P_1, P_2, \dots, P_{4k}$, alternating red and blue. Each red segment connects two red points, say $R_1$ and $R_2$. The segment $R_1R_2$ divides the circle into two arcs. Because red and blue points alternate, each arc contains an equal number of red and blue points, namely $k$ red points and $k$ blue points. Therefore, on each side of the red segment, there are $k$ blue points. Any blue segment connecting two blue points on opposite sides of this red segment must intersect it. Since exactly $k$ blue segments connect $2k$ blue points, the total number of blue segments connecting opposite sides of red segments cannot be smaller than $k$. Each red segment intersects at least one blue segment, and each intersection occurs at a unique point because no three segments intersect at one point. Consequently, the total number of red-blue intersections is at least $k$. This completes the proof.
∎
Verification of Key Steps
For Lemma 1, explicitly consider $k=3$, $4k=12$ points. Label points consecutively $R, B, R, B, \dots$. Any red segment, say connecting the first and fourth red points, leaves six points on one arc, containing exactly three blue points, confirming the counting. For Lemma 2, consider the arcs separated by the red segment; pairing the $2k$ blue points into $k$ segments forces that at least one blue segment connects points across the arc division, producing an intersection with the red segment. Checking multiple small configurations for $k=2,3$ confirms that no arrangement can reduce the intersections below $k$. Each intersection remains unique under the no-three-intersections rule, validating Lemma 3.
Alternative Approaches
One alternative is a combinatorial argument using parity. Number the points consecutively and assign labels $1,2,\dots,4k$. Observe that each red segment has endpoints with indices differing by an odd number; each blue segment similarly. Then a red segment with endpoints $(i,j)$ intersects a blue segment $(p,q)$ if and only if the indices are “interleaved,” i.e., $i<p<j<q$ or $p<i<q<j$. Counting minimal interleavings among $k$ red and $k$ blue segments provides another route to show at least $k$ intersections. This method requires careful bookkeeping of indices and is more technical, while the geometric arc argument used above is more intuitive and direct.