To finish a proof I have to prove the following:
Consider the set of integers $ S= \{ 1,\dots,n \} $ and let $k\le n$.
Pick $k$ elements of S two times $a_1,\dots,a_k$, $b_1,\dots b_k\in S$
in such way that: there is a unique way to order the two choices
$a_1<\dots<a_k$ and $b_1<\dots<b_k$, we ask that $a_i\le b_i$ for each
$i=1,\dots,k$. Consider then $a_{k+1}<\dots<a_n$ the remaining
elements in order of $S\setminus\{a_1,\dots,a_k\}$ and
$b_{k+1}<\dots<b_n\in S\setminus\{b_1,\dots,b_k\}$. The claim is that
$a_i\ge b_i$ for each $i=k+1,\dots,n$.
For example: $S=\{ 1,2,3,4,5,6 \},$ so $n=6$, and let $k=3$. Pick $(a_1,a_2,a_3)=(1,3,5)$ and $(b_1,b_2,b_3)=(2,5,6)$. Of course we have $a_i\le b_i$. Taking the complements we have $(a_4,a_5,a_6)=(2,4,6)$ and $(b_4,b_5,b_6)=(1,3,4)$ and here $a_i\ge b_i$ as wanted.
The question is really elementary, but I struggled to write a general proof. My progress is: we can assume in the first choise that each $a_i < b_i$, otherwise if $a_i = b_i$ we can drop this pair. This implies in the complement that $a_{k+1}>b_{k+1}$ and $a_{n}>b_n$. I tried to use induction on the index between $k+1$ and $n$ but I can't figure it out how to conclude. Also I tried for contraddiction assuming there is an index such that $a_j\le b_j$, and taking the smaller of those, but I cannot finish the proof.
Thank you in advance to those who can answer me.
Best Answer
This seems like the sort of problem where a better choice of notation can help a lot.
Let $\alpha(x) = \#\{i \le k : a_i \le x\}$ and $\beta(x) = \#\{i \le k : b_i \le x\}$ for $x \in \{1,\dots,n\}$. Then your hypothesis that $a_i \le b_i$ for $i=1,\dots,k$ is equivalent to $\alpha(x) \ge \beta(x)$ for all $x$. Now the number of remaining elements $\le x$ after removing the $a_i$'s is $x - \alpha(x)$, and analogously for the $b_i$'s, and obviously $\alpha(x) \ge \beta(x)$ for all $x$ implies $x - \alpha(x) \le x - \beta(x)$ for all $x$.