\(n\)人のクラスでテストを2回行なったところ、全員、2回目の得点のほうが1回目より高かったとする。このとき、1回目の最高点よりも2回目の最高点のほうが高くなることは直感的に明らかだろう。最高点をとったのが同じ学生Aなら直ちに言えるし、別の学生Bが取ったのであれば、やはり「（Aによる）1回目の最高点＜Aの2回目の得点≦（Bによる）2回目の最高点」となる。では、最高点以外の、同じ順位の（同じ学生によるとは限らない）得点同士についても、一般に「1回目＜2回目」が言えるだろうか？結論は「Yes」であるが、これをきちんと証明しよう。
【問】\(n\)を正の整数とする。\(a_1\leq a_2\leq\ldots\leq a_n\)かつ任意の\(1\leq k\leq n\)なる整数\(k\)について\(a_k < b_k\)が成り立っている。\(b_1,b_2,\ldots,b_n\)を小さい順に並べ替えたものを\(c_1,c_2,\ldots, c_n\)とすると、任意の\(1\leq k\leq n\)なる整数\(k\)について\(a_k < c_k\)となることを示せ。
【証明】\(k\)を任意に固定して考える。\(c_1,c_2,\ldots,c_k\)はすべて\(c_k\)以下であるから、\(b_1,b_2,\ldots,b_n\)は\(c_k\)以下の項を少なくとも\(k\)個持っている。したがって、\(b_k\)以降がすべて\(c_k\)の値を超えるという事態は起こりえない。そこで、\(b_t\leq c_k\)かつ\(k\leq t\leq n\)なる整数\(t\)をひとつとると、\(a_k\leq a_t < b_t\leq c_k\)である。■
