Hey there! Let's tackle this neat combinatorial problem together—your intuition about using contradiction was on the right track; we just needed to frame the counting argument correctly to seal the deal. First, let's restate the problem clearly to align our understanding:

给定整数集合 ( S = {1, 2, \dots, n} )，取 ( k \leq n )。选择两个k元子集，排序后得到 ( a_1 < a_2 < \dots < a_k ) 和 ( b_1 < b_2 < \dots < b_k )，满足对所有 ( 1 \leq i \leq k )，( a_i \leq b_i )。将 ( S \setminus {a_1, \dots, a_k} ) 和 ( S \setminus {b_1, \dots, b_k} ) 分别排序得到 ( a_{k+1} < \dots < a_n ) 和 ( b_{k+1} < \dots < b_n )，需要证明：对所有 ( k+1 \leq i \leq n )，( a_i \geq b_i )。

示例验证 #

Take your example to ground this: ( S = {1,2,3,4,5,6} ), ( k=3 ), ( (a_1,a_2,a_3)=(1,3,5) ), ( (b_1,b_2,b_3)=(2,5,6) ). We can see ( a_i \leq b_i ) holds for all i=1,2,3. The complements sorted are ( (a_4,a_5,a_6)=(2,4,6) ) and ( (b_4,b_5,b_6)=(1,3,4) ), and indeed ( a_i \geq b_i ) for each complementary position.

正式证明：反证法 #

Let's assume for contradiction that there exists some smallest index ( j \in {k+1, k+2, \dots, n} ) where ( a_j < b_j ). Let ( x = b_j ) (the value at this "bad" complementary position). We'll use a counting argument to show this leads to a contradiction.

Step 1: A key counting property from the original condition

First, let's define for any integer ( x ):

• ( c_A(x) ): number of elements in ( {a_1, \dots, a_k} ) that are ≤ x
• ( c_B(x) ): number of elements in ( {b_1, \dots, b_k} ) that are ≤ x

Because ( a_1 \leq b_1, a_2 \leq b_2, \dots, a_k \leq b_k ), we can prove that for every x, ( c_A(x) \geq c_B(x) ). Here's why:

• If ( c_B(x) = m ), then ( b_m \leq x < b_{m+1} ) (or ( b_k \leq x ) if m=k). Since ( a_m \leq b_m \leq x ), all ( a_1 \dots a_m ) are ≤x, so ( c_A(x) \geq m = c_B(x) ). This property is crucial for our contradiction.

Step 2: Count elements ≤ x

Since ( j ) is the smallest index where ( a_j < b_j = x ):

• All complementary elements before j (i.e., ( a_{k+1}, \dots, a_{j-1} )) satisfy ( a_i \geq b_i ), and since ( a_{j-1} < a_j < x ), these ( b_i ) must also be <x.
• The sorted complement ( a_{k+1} < \dots < a_j < x ), so exactly ( j - k ) elements of the complement of A are ≤x. Thus, total elements in S ≤x are ( c_A(x) + (j - k) = x ) (since S contains all integers from 1 to x). Rearranged: ( c_A(x) = x - (j - k) ).
• For B's complement: ( b_{k+1} < \dots < b_{j-1} < x = b_j ), so exactly ( j - k ) elements of B's complement are ≤x. Thus, ( c_B(x) + (j - k) = x ), so ( c_B(x) = x - (j - k) ).

Step 3: Contradiction with x-1

Now consider ( x-1 ):

• Elements in A's complement ≤x-1: still ( j - k ) (since ( a_j < x ) implies ( a_j ≤x-1 ), and ( a_{j+1} > a_j ), plus ( j ) is the smallest bad index so ( a_{j+1} ≥ b_{j+1} > x )). Thus, ( c_A(x-1) = (x-1) - (j - k) ).
• Elements in B's complement ≤x-1: only ( j - k -1 ) (since ( b_j =x >x-1 )). Thus, ( c_B(x-1) = (x-1) - (j - k -1) = x - (j - k) ).

Now compare ( c_A(x-1) ) and ( c_B(x-1) ):
( c_A(x-1) = (x-1) - (j - k) = [x - (j - k)] - 1 = c_B(x-1) -1 )

This means ( c_A(x-1) < c_B(x-1) ), which directly violates our earlier key property that ( c_A(x) ≥ c_B(x) ) for all x.

Conclusion #

Our assumption that there exists a "bad" index j leads to a contradiction, so no such index can exist. Therefore, for all ( k+1 ≤i ≤n ), ( a_i ≥b_i ).

As you noted earlier, we can simplify the problem first by removing any pairs where ( a_i =b_i ) (since they don't affect the complementary sequences), but the above proof works directly even with equal pairs included.

备注：内容来源于stack exchange，提问作者FreeFunctor