§C5.1鳩の巣原理の応用

証明. 各$i$に対し、$a_i$で終わる狭義単調増加部分列の長さの最大値を$p_i$、$a_i$で終わる狭義単調減少部分列の長さの最大値を$q_i$とする。

長さ$n+1$の狭義単調増加部分列も狭義単調減少部分列も存在しないと仮定する。このとき、すべての$i$に対して$1\leq p_i\leq n$かつ$1\leq q_i\leq n$であるから、組$(p_i,q_i)$は$n^2$通りしかない。

$i<j$とする。$a_i<a_j$ならば、$a_i$で終わる長さ$p_i$の狭義単調増加部分列の末尾に$a_j$を加えることができるので、$p_j\geq p_i+1$である。$a_i>a_j$ならば、同様に$q_j\geq q_i+1$である。各項は相異なるから二場合のいずれかが成り立ち、$(p_i,q_i)\neq(p_j,q_j)$を得る。

したがって、$n^2+1$個の相異なる組$(p_i,q_i)$が$n^2$個の組からなる集合$\{1,\ldots,n\}^2$に属することになる。これは鳩の巣原理に反する。ゆえに、求める部分列の少なくとも一方が存在する。▨

証明. 各$x_i$を$n$で割った余りによって、$0,1,\ldots,n-1$の$n$個の箱に分類する。$n+1$個の整数を$n$個の箱に入れるので、同じ余りをもつ$x_i,x_j$があり、添字を入れ替えれば$i<j$としてよい。ある整数$q_i,q_j$と同じ余り$r$を用いて$x_i=nq_i+r$、$x_j=nq_j+r$と書くと、$x_j-x_i=n(q_j-q_i)$である。したがって、$x_j-x_i$は$n$の倍数である。▨

証明. 選んだ各整数$x$は、非負整数$k$と奇数$m$を用いて$x=2^k m$と一意に表すことができる。この奇数$m$を$x$の奇数部分とする。$1$以上$2n$以下の奇数は$1,3,\ldots,2n-1$の$n$個であるから、選んだ$n+1$個の整数のうち二つ$x,y$は同じ奇数部分$m$をもつ。

$x=2^r m$、$y=2^s m$と書く。$x$と$y$は相異なるから$r\neq s$であり、必要なら$x$と$y$を入れ替えて$r<s$としてよい。このとき$y=2^{s-r}x$であるから、$x$は$y$を割り切る。▨