Chinese Mathematical Olympiad

Proof: Consider $2m+2n$ vertices placed on the unit circle. The Euclidean distances between vertices are irrelevant to the discussion. We define the line segments in the white pairing scheme as white segments and those in the black pairing scheme as black segments.

Lemma 1: For any black pairing scheme $\mathcal{B}$ and any white point pairing scheme $\mathcal{W}$, the number of intersection points $I(\mathcal{B},\mathcal{W})$ between the $m+n$ line segments connected in the schemes is bounded above by $P(\mathcal{B})$ and by $P(\mathcal{W})$, respectively.



(For the black and white pairing schemes $\mathcal{B}$ and $\mathcal{W}$ shown in the figure, we replace white segments with red ones and denote intersection points with blue, so that $I(\mathcal{B},\mathcal{W})=5$, $P(\mathcal{B})=2+3+2=7$, and $P(\mathcal{W})=1+3+1=5$.)

Proof of Lemma 1: For any line segment $B_i{C}_i$ in $\mathcal{B}$, the number of white line segments intersecting it is at most $d(B_i,C_i)$, because each white line segment corresponds to a white point on each side of $B_i{C}_i$. Summing over all black segments in $\mathcal{B}$ yields the inequality $I(\mathcal{B},\mathcal{W})\le P(\mathcal{B})$. Similarly, we have $I(\mathcal{B},\mathcal{W})\le P(\mathcal{W})$. Therefore, Lemma 1 is proved.

Lemma 2: For any black pairing scheme $\mathcal{B}$, there exists a white pairing scheme $\mathcal{W}$ such that $I(\mathcal{B},\mathcal{W})=P(\mathcal{B})$. Thus, $P(\mathcal{B})=I(\mathcal{B},\mathcal{W})\le P(\mathcal{W})$.

We now show that Lemma 2 proves the original problem. Apply Lemma 2 to all $\mathcal{B}$ to obtain ${\max }_{\mathcal{B}}P(\mathcal{B})\le {\max }_{\mathcal{W}}P(\mathcal{W})$. A symmetric argument shows that ${\max }_{\mathcal{W}}P(\mathcal{W})\le {\max }_{\mathcal{B}}P(\mathcal{B})$. Therefore, the problem is proved.

Proof of Lemma 2 (Method 1): We prove by induction on the number $2n$ of white points that there exists a white pairing scheme $\mathcal{W}$. When $n=0$, the claim is trivial. Suppose the claim is true for $2n-2$ white points. Consider the case of $2n$ white points. Among all black pairings $B_i{C}_i$, let $B_1{C}_1$ be the one with the largest $d(B_i,C_i)$. If $d(B_1,C_1)=0$, we can arbitrarily choose a white pairing scheme. Assume that $d(B_1,C_1)>0$. Let $W_n$ be the first white point encountered when rotating clockwise from $B_1$ and let $X_n$ be the first white point encountered when rotating counterclockwise from $B_1$. As shown in the following figure,



Now consider the case where we remove two white points $W_n$ and $X_n$. Let $d^{\prime }(B,C)$ be the chromatic distance in this case, and let $P^{\prime }(\mathcal{B})={\sum }_{i=1}^m{d}^{\prime }(B_i,C_i)$. By the induction hypothesis, there exists a white pairing scheme ${\mathcal{W}}^{\prime }$ for $\mathcal{B}$ without $W_n$ and $X_n$ such that $I(\mathcal{B},{\mathcal{W}}^{\prime })=P^{\prime }(\mathcal{B})$. We will prove that we can obtain the desired white pairing scheme $\mathcal{W}$ by adding the line segment $W_n{X}_n$ to ${\mathcal{W}}^{\prime }$.

We consider each segment $BC$ in $\mathcal{B}$. If it intersects with $W_n{X}_n$, then removing $W_n$ and $X_n$ is equivalent to removing one white point on each side of $BC$, so $d^{\prime }(B,C)=d(B,C)-1$. If $BC$ does not intersect with $W_n{X}_n$, we want to show that $d(B,C)=d^{\prime }(B,C)$. Note that if there are more than $n+1$ white points on one side of $BC$ with respect to $W_n{X}_n$, while the other side has no more than $n-1$ white points, then we must have $d(B,C)=d^{\prime }(B,C)$. On the other hand, if there are no more than $n$ white points on one side of $BC$, and $BC$ does not intersect with either $B_1{C}_1$ or $W_n{X}_n$, then the entire segment $B_1{C}_1$ must be on the side of $BC$ with no more than $n$ white points. This contradicts our assumption that $d(B,C)>d(B_1,C_1)$, since $BC$ is closer to $B_1{C}_1$ than any other black segment. Therefore, we have $d(B,C)=d^{\prime }(B,C)$.

Thus, we see that $P(\mathcal{B})-P^{\prime }(\mathcal{B})$ is exactly equal to the number of black segments in $\mathcal{B}$ that intersect $W_n{X}_n$, which is equal to $I(\mathcal{B},\mathcal{W})-I(\mathcal{B},{\mathcal{W}}^{\prime })$. Therefore, we have $I(\mathcal{B},\mathcal{W})=P(\mathcal{B})$. This completes the induction proof.

Proof of Lemma 2 (Method 2): This proof is essentially the same as Method 1, but the statement is worded differently. For each black segment $BC$ in $\mathcal{B}$, we call the set of white points on the side with fewer white points an internal white point set (if $d(B,C)=n$, choose one side arbitrarily to define the internal white point set). Note that any two internal white point sets (for two different black segments) either do not intersect or one is contained in the other.

We choose all the largest internal white point sets, and consider the points outside these sets as their own internal white point sets. We only need to prove there exists a white pairing scheme such that no two white segments correspond to white points in the same internal white point set. To do this, we first choose the largest internal white point set, connect the last point in clockwise order to the next point in counterclockwise order, and remove these two white points. We then consider the remaining white points and internal white point sets. Clearly, the resulting white point scheme is valid, and it satisfies the condition because by induction, we know that at any point in the algorithm, the number of white points in the largest internal white point set is less than or equal to the total number of white points in the rest of the internal white point sets.

Proof of Lemma 2 (Method 3): First, we construct a weak white pairing scheme ${\mathcal{W}}^{\prime }$, where white points are matched without requiring the corresponding white segments to have mutually disjoint pairs, such that $I(\mathcal{B},{\mathcal{W}}^{\prime })=P(\mathcal{B})$. In fact, if $W_1,W_2,\dots ,W_{2n}$ are $2n$ white points arranged in sequence on the circle, we just need to match $W_i$ with $W_{n+i}$ ($1\le i\le n$) to achieve this, because such a pairing will connect the white points with fewer white points on one side of any black segment to the other side.

We select from all weak white pairing schemes ${\mathcal{W}}^{\prime }$ that satisfy $I(\mathcal{B},{\mathcal{W}}^{\prime })=P(\mathcal{B})$ the one with the minimum Euclidean distance sum of white segments, denoted by ${\mathcal{W}}_0$. We then prove that any two of the $n$ white segments in ${\mathcal{W}}_0$ do not intersect.

Suppose, to the contrary, that two segments $WX$ and $YZ$ intersect, and without loss of generality, we assume they are arranged clockwise on the circle as $W,Y,X,Z$. As black segments in $\mathcal{B}$ do not intersect, there cannot be a black segment connecting $\overline{YX}$ and $\overline{WZ}$, as well as a black segment connecting $\overline{XZ}$ and $\overline{WY}$ simultaneously. Without loss of generality, we assume there is no black segment connecting $\overline{YX}$ and $\overline{WZ}$. We then modify segments $YZ$ and $WX$ to be $WY$ and $ZX$, respectively, obtaining a new weak white pairing scheme ${\mathcal{W}}_0^{\prime }$, which clearly reduces the Euclidean distance sum of all white segments.



We now compare $I(\mathcal{B},{\mathcal{W}}_0)$ and $I(\mathcal{B},{\mathcal{W}}_0^{\prime })$ using the following observations: For any black segment that connects $\overline{WY}$ and $\overline{XY}$, or $\overline{ZX}$ and $\overline{XY}$, or $\overline{WY}$ and $\overline{WZ}$, or $\overline{ZX}$ and $\overline{WZ}$, the number of intersections with $WX$ and $YZ$ is precisely one, and the number of intersections with $WY$ and $ZX$ is also one. For any black segment that connects $\overline{WY}$ and $\overline{ZX}$, the number of intersections with each of $WY,WX,YZ$, and $ZX$ is also one.

Thus, we have $I(\mathcal{B},{\mathcal{W}}_0)=I(\mathcal{B},{\mathcal{W}}_0^{\prime })$. However, this contradicts the fact that the sum of Euclidean distances of all white segments in ${\mathcal{W}}_0$ is minimal. Therefore, ${\mathcal{W}}_0$ is a valid white pairing scheme, and the proof of Lemma 2 is complete.