Given positive integer $m,n$, color the points of the regular $(2m+2n)$-gon in black and white, $2m$ in black and $2n$ in white. The coloring distance $d(B,C) $ of two black points $B,C$ is defined as the smaller number of white points in the two paths linking the two black points. The coloring distance $d(W,X) $ of two white points $W,X$ is defined as the smaller number of black points in the two paths linking the two white points. We define the matching of black points $\mathcal{B}$ : label the $2m$ black points with $A_1,\cdots,A_m,B_1,\cdots,B_m$ satisfying no $A_iB_i$ intersects inside the gon. We define the matching of white points $\mathcal{W}$ : label the $2n$ white points with $C_1,\cdots,C_n,D_1,\cdots,D_n$ satisfying no $C_iD_i$ intersects inside the gon. We define $P(\mathcal{B})=\sum^m_{i=1}d(A_i,B_i), P(\mathcal{W} )=\sum^n_{j=1}d(C_j,D_j) $. Prove that: $\max_{\mathcal{B}}P(\mathcal{B})=\max_{\mathcal{W}}P(\mathcal{W})$
Problem
Source: China MO 2023 P3
Tags: combinatorics
29.12.2022 10:56
is my sol anyway.
29.12.2022 12:09
Let $M$ be the maximum number of intersections by drawing $m+n$ chords,each connecting to points with the same color,and the chords connecting the same color do not intersect. Clearly for any black chord,it has at most the minimum number of white points on either side of this chord;summing up we get $M \le \max P(B)$. On the other side,for any valid matching of black points,we consider the interval with smaller number of white points in it. Clearly these intervals contain each other or do not intersect. Taking the intervals not contained by any other,it is easy to show by induction(by pairing one point in the "longest" chord with one outside) that there exist a valid matching such that each white chord is not contained in any interval. Easy computation shows that it yields $\max P(B)\le M$. So $\max P(w)=M=\max P(B)$ as desired.
30.12.2022 04:03
This is China MO 2022.
31.12.2022 01:46
This problem is difficult to writeup. Please draw a diagram if you are serious about understanding this solution. Notations: WLOG, the $(2m+2n)$-agon is inscribed in a circle. With respect to a white point $P$, the next white point $P'$ is the point such that if I move clockwise from $P$, the first white point I encounter is $P'$. When I say between $A$ and $B$, I mean the arc that we get starting from $A$, moving clockwise, and ending at $B$.Label the black points in clockwise order $W_1, \cdots, W_{2n}, W_{2n+1}=W_1$. Call the chord between two points their line segment. Say two points $X,Y$ are paired if $X=C_j, Y=D_j$ for some $j$ Claim: there exists an integer $s$ and pair two points if the sum of their indices is $s(\bmod\; 2n)$. Proof: I will just show that if $X,Y$ are adjacent white points, if $X$ is paired with $W$ and $Y$ is paired with $Z$, then $WZ$ are also adjacent. This clearly suffices. We only need to deal with the case where $X,Y$ are not paired together. Say if $X$ is the next white point of $Y$. Then if I start moving clockwise from $X$, I traverse $X,W,Z,Y$ in this order. This means if $W' \ne Z$ is the next white point of $W$, it must be paired with something on the clockwise arc from $W$ to $Z$, call $W''$. If $Z' \ne W$ is the previous white point of $Z$, it must be paired with something on the clockwise arc from $W$ to $Z$, call $Z''$ (it is advised to draw a diagram to see this) So the points in clockwise order, starting from $X$ are $X,W,W', W'', Z'', Z', Z, Y$ This means there are either at most $m$ black points between $X$ and $W''$, or at most $m$ black points between $Z''$ and $Y$. WLOG there are $m$ black points between $X$ and $W''$. Then I pair $X$ with $W''$ and $W$ with $W'$. Since $W,W'$ are adjacent, there should be no intersections, as anything that intersects with $XW''$ must either intersect with $XW$ or $W'W''$. WLOG $s=0$, and we label the white points $W_1, \cdots, W_n, V_n, \cdots, V_1$ in this clockwise order, where $W_iV_i$ is horizontal and $V_i$ is to the left of $W_i$. Main claim: $\max_{\mathcal{W}}P(\mathcal{W})$ is equal to the maximum number of intersections between white chords and black chords, where chords of the same color don't intersect (within the $(2m+2n)$-agon). This solves the problem by symmetry. Proof: It is obvious if we connect black chords, the number of intersections is at most $\max_{\mathcal{W}}P(\mathcal{W})$ because if a white chord and a black chord intersect, exactly one of the black points of this black chord contributes to the sum. The important part is to show that equality is achievable. This is equivalent to the following: if a white chord and a black chord DON'T intersect, the black points are not counted for sure. We say an arc $\hat{XY}$ is major if it contains more than half of the black points, and call it minor otherwise. Rotate the circle and move the points (order don't change) so that the white chords are all horizontal. Label them from top to bottom $1,2,\cdots,n$. For each black point $A$, let $S_A$ be the set of minor white chords $\hat{XY}$ that contain $A$ (if there are exactly $m$ black points between $XY$, which side is counted is arbitrary as long as it is consistent.) Let $k$ be the unique integer such that the arc between $V_k$ and $W_k$ (this is the upper arc) is minor (or there are $m$ points but we count the top part). Then for any black point $A$, we have either $S_A$ is the set of all integers from $t$ to $k$ (for some $t\le k+1$) if it is not below the $(k+1)$th line. Otherwise, it will be the set of integers from $k+1$ to $t$ for some $t\ge k+1$. There are at most $m$ black points in the arc between $V_k$ and $W_k$ and at most $m$ black points between $W_{k+1}$ and $V_{k+1}$. Define two sides top and bottom as follows: all black points in the arc between $V_k$ and $W_k$ For the black points between $V_{k+1}$ and $V_k$ or between $W_k$ and $W_{k+1}$, we "add" it to a side so that in the end, the top and bottom side both have $m$ points each, and the top side has $m$ consecutive black points. Note if $A$ is from the top and $B$ is from the bottom, then $S_A\cap S_B=\emptyset$. Therefore, we can pair top and bottom points. If a white chord doesn't intersect the two black points, since the sets of chords that have the black points "contribute" are distinct, the white chord simply don't have these two black points counted.
Attachments:

01.01.2023 08:21
Let $W,B$ be the set of white and black points respectively. It suffices to show the following: given any matching of the white points, $\mathcal{W}$, we can produce a matching of the black points, $\mathcal{B}$ such that $P(\mathcal{B}) \geq P(\mathcal{W})$. From here the result follows from symmetry. Let $\mathcal{W}$ be a given matching of the white points. For any edge $(w_1, w_2) \in \mathcal{W}$ define $S(w_1, w_2)$ to be the set of black points on the arc from $w_1$ to $w_2$ which has fewer black points, so $$ P(\mathcal{W}) = \displaystyle \sum_{(w_1, w_2) \in \mathcal{W}} |S(w_1, w_2)|$$
). We shall use the following lemma (easy to prove, and commonly encountered in competitive programming). Lemma: Suppose there are $n$ boxes, and the $i$-th box contains $a_i$ balls. Suppose $a_1 + a_2 + \cdots + a_n$ is even, and $a_i \leq \displaystyle \sum_{j \in [n], j \neq i} a_j$ for all $i \in [n]$. Then, there exists a matching of the balls where every ball is matched to a ball in a different box. It is easy to see that for $(w_1, w_2), (w_3, w_4) \in \mathcal{W}$, either $S(w_1, w_2) \subseteq S(w_3,w_4)$ or $S(w_3, w_4) \subseteq S(w_1, w_2)$ or $S(w_1, w_2) \cap S(w_3, w_4)= \phi$. We say $(w_1, w_2)$ dominates $(w_3, w_4)$ if $S(w_3, w_4) \subseteq S(w_1, w_2)$. Let $U \subseteq \mathcal{W}$ be the set of non-dominated edges. Suppose $U = \{(w_1, v_1), (w_2, v_2), \cdots , (w_t, v_t)\}$. Let $S_i = S(w_i, v_i)$. The sets $S_i$ are mutually disjoint. It suffices to produce a matching $\mathcal{B}$ such that every element in $S_i$ is matched to an element not in $S_i$. We do this as follows. Case 1: $|B \setminus (S_1 \cup \cdots \cup S_t)| \geq |S_1| + \cdots + |S_t|$ In this case construct the matching as follows: as long as there is an unmatched element in $S_1 \cup S_2 \cdots \cup S_t$, match it to an arbitrary element of $B \setminus (S_1 \cup \cdots \cup S_t)$. Case 2: $|B \setminus (S_1 \cup \cdots \cup S_t)| \leq |S_1| + \cdots + |S_t|$ Since $|S_i| \leq |B \setminus S_i| $ for all $i \in [t]$, in this case we can invoke the lemma on $S_1, S_2, \cdots , S_t, B \setminus (S_1 \cup \cdots \cup S_t)$ to get the desired matching.
11.12.2024 03:19
It suffices to prove that for any matching of black points, we can find a matching of white points such that $P(\mathcal{W})\geq P(\mathcal{B})$. This also implies that for any matching of white points we can find a matching of black points such that $P(\mathcal{B})\geq P(\mathcal{W})$. This clearly implies the result. To see that this is true it suffices to prove that for any set of white points between two connected black points we can find a matching such that each white point inside two connected black points connects to a white point outside. To prove that such a matching exists I will first prove that if we have a number of sets $a_1$, $a_2$, \dots $a_n$, such that for any $i$, $\vert a_i\vert \leq \sum_{k=1, k\neq i}^{n}\vert a_k\vert$. I will prove that we can find a matching on those sets such that none of the elements of the sets map to themselves. Suppose if we have $m<\sum_{k=1}^{n}\vert a_k \vert$ elements than we can find such a matching on any subsets. Now we can choose an element in the maximal size and second maximal size subset and match and remove those elements. Clearly we still have that the set size condition holds, because after removing $2$ elements the third largest size subset cannot be bigger than the sum of the rest. Thus we have a matching between those subsets such that no element in the same subset matches to one of the same. Now apply this matching to the subsets we have. If two lines in the matching intersect, we can see that one of the two possible uncrossings will not match two things in the same subset thus as this process of unmatching decreases the sum of the euclidean distances between the vertices it must end so we get our matching. Thus the result must hold.
16.01.2025 17:47
Peak. Define a proper matching of the $(2m+2n)$ points as a set of $(m+n)$ chords such that chords are drawn between 2 points of the same color, and no two chords between points of the same color intersect. The number of crossings of a proper matching is the number of pairs of black and white chords that intersect. Let $\mathcal{S}$ be the proper matching that attains the maximum number of crossings, say $C$. Let $\mathcal{D}$ denote the pairings of the white points. For each white chord that intersects a black chord, note no matter which side of the white chord contains less black points, it will contain exactly one point from this black chord. Thus summing over all white chords, we obtain $$C \leq P(\mathcal{D}) \leq \max_{\mathcal{W}}P(\mathcal{W})$$ On the other hand, let $\mathcal{W'}$ be the matching of white points that attains $\max_{\mathcal{W}}P(\mathcal{W})$. We claim that we can construct a proper matching containing $\mathcal{W'}$ such that no black chord is contained in the interval of any white chord (that contains the smaller number of black points). Consider all such intervals across all white chords. It is known that every 2 intervals are either disjoint or one contains the other. Thus there exists some chord not contained in the interval of any other. Consider the set of all such chords whose interval contains a black point. We induct on the number of such chords to prove our claim. By definition there are at least as many black points not in the interval than in the interval; suppose we have the consecutive black points in clockwise order $A_n, A_{n-1}, \cdots , A_1, B_1, B_2, \cdots , B_n$, where $ B_1, B_2, \cdots , B_n$ are the black points in this interval; then we simply construct $A_i B_i$ for $i=1,\cdots n$ and note that none of these black chords can possibly intersect with any new black chord we construct. Additionally, if these black chords were contained in the interval of some white chord, the interval would intersect with and hence contain the original white chord, a contradiction. As we have matched all the black points inside this chord's interval, the inductive step is complete. In particular, consider now the proper matching produced by the above claim applied to $\mathcal{W'}$, with $C'$ crossings. If the interval of a white chord contains some black point, the corresponding black chord must intersect with this chord; summing over all white chords gives $$\max_{\mathcal{W}}P(\mathcal{W}) = P(\mathcal{W'}) \leq C' \leq C$$ Therefore, $\max_{\mathcal{W}}P(\mathcal{W}) = C$ and by symmetry $\max_{\mathcal{B}}P(\mathcal{B}) = C$, as desired.