Câu hỏi 167
Cố định hai số nguyên dương $m$ và $n$. Cố định một cách tô màu các đỉnh của một đa giác đều $(2m+2n)$ cạnh sao cho $2m$ đỉnh được tô đen và $2n$ đỉnh còn lại được tô trắng. Định nghĩa khoảng cách màu $d(B, C)$ giữa hai điểm đen $B$ và $C$ là số nhỏ hơn trong hai số lượng điểm trắng nằm ở hai phía của đường thẳng $BC$; tương tự, định nghĩa khoảng cách màu $d(W, X)$ giữa hai điểm trắng $W$ và $X$ là số nhỏ hơn trong hai số lượng điểm đen nằm ở hai phía của đường thẳng $WX$.
Một cách ghép cặp đen $\mathcal{B}$ là một cách đặt tên $2m$ điểm đen là $B_1, \dots, B_m, C_1, \dots, C_m$ sao cho không có hai đoạn thẳng nào trong các đoạn $B_1C_1, \dots, B_mC_m$ cắt nhau. Với mỗi $\mathcal{B}$ như vậy, đặt
$$
P(\mathcal{B}) = \sum_{i=1}^{m} d(B_i, C_i).
$$
Một cách ghép cặp trắng $\mathcal{W}$ là một cách đặt tên $2n$ điểm trắng là $W_1, \dots, W_n, X_1, \dots, X_n$ sao cho không có hai đoạn thẳng nào trong các đoạn $W_1X_1, \dots, W_nX_n$ cắt nhau. Với mỗi $\mathcal{W}$ như vậy, đặt
$$
P(\mathcal{W}) = \sum_{i=1}^{n} d(W_i, X_i).
$$
Chứng minh rằng, với mọi cách tô màu $2m+2n$ đỉnh, ta luôn có
$$
\max_{\mathcal{B}} P(\mathcal{B}) = \max_{\mathcal{W}} P(\mathcal{W}),
$$
trong đó các giá trị lớn nhất được lấy lần lượt trên tất cả các cách ghép cặp đen và tất cả các cách ghép cặp trắng.
Một cách ghép cặp đen $\mathcal{B}$ là một cách đặt tên $2m$ điểm đen là $B_1, \dots, B_m, C_1, \dots, C_m$ sao cho không có hai đoạn thẳng nào trong các đoạn $B_1C_1, \dots, B_mC_m$ cắt nhau. Với mỗi $\mathcal{B}$ như vậy, đặt
$$
P(\mathcal{B}) = \sum_{i=1}^{m} d(B_i, C_i).
$$
Một cách ghép cặp trắng $\mathcal{W}$ là một cách đặt tên $2n$ điểm trắng là $W_1, \dots, W_n, X_1, \dots, X_n$ sao cho không có hai đoạn thẳng nào trong các đoạn $W_1X_1, \dots, W_nX_n$ cắt nhau. Với mỗi $\mathcal{W}$ như vậy, đặt
$$
P(\mathcal{W}) = \sum_{i=1}^{n} d(W_i, X_i).
$$
Chứng minh rằng, với mọi cách tô màu $2m+2n$ đỉnh, ta luôn có
$$
\max_{\mathcal{B}} P(\mathcal{B}) = \max_{\mathcal{W}} P(\mathcal{W}),
$$
trong đó các giá trị lớn nhất được lấy lần lượt trên tất cả các cách ghép cặp đen và tất cả các cách ghép cặp trắng.