鳩の巣原理の応用 | 雑多な話題

1 部分列の長さによる分類

定理 1.1 (Erdős–Szekeres の定理). $n$ を正の整数とし、相異なる実数 $a_1,a_2,\ldots,a_{n^2+1}$ をこの順に並べる。この列は、長さ $n+1$ の狭義単調増加部分列または長さ $n+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$ に属することになる。これは鳩の巣原理に反する。ゆえに、求める部分列の少なくとも一方が存在する。▨

2 整数を別の量で分類する例

例 2.1. $n$ を正の整数とする。 $n+1$ 個の整数 $x_1,x_2,\ldots,x_{n+1}$ から、差が $n$ の倍数となる二つを選ぶことができる。

証明. 各 $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$ の倍数である。▨

例 2.2. $n$ を正の整数とする。 $1,2,\ldots,2n$ から相異なる $n+1$ 個の整数を選ぶと、そのうちの一方が他方を割り切る二数が存在する。

証明. 選んだ各整数 $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$ を割り切る。▨

3 設計チェック

注意 3.1. 鳩の巣原理を適用する前に、次の四点を確かめる。

鳩に当たる対象をすべて特定する。
各対象がちょうど一つに入る分類を定め、その分類の個数を数える。
対象の個数が分類の個数を上回ることを示す。
同じ分類に入った相異なる二対象から、求める結論が実際に従うことを示す。

分類の個数を必要以上に大きく評価すると、同じ分類に二対象が入ることを保証するために、問題が与えるより多くの対象が必要になる。

4 演習

問題 4.1. $2n+1$ 個の整数から、同じ偶奇をもつ $n+1$ 個を選ぶことができることを示せ。

解答.

$n$ を $0$ 以上の整数とする。与えられた $2n+1$ 個の整数を、偶数の組と奇数の組の二つに分類する。どちらの組の個数も $n$ 以下であると仮定すると、整数の個数は $n+n=2n$ 以下となり、 $2n+1$ 個であることに反する。したがって、一方の組は $n+1$ 個以上の整数を含む。その組から $n+1$ 個を選べば、それらは同じ偶奇をもつ。▨

問題 4.2. 整数列 $x_1,x_2,\ldots,x_{n+1}$ には、和が $n+1$ の倍数となる空でない連続部分 $x_i+x_{i+1}+\cdots+x_j$ が存在することを示せ。 $0$ から始まる部分和を分類に用いよ。

解答.

$n$ を正の整数とする。 $S_0=0$ とし、 $k=1,\ldots,n+1$ について $S_k=x_1+x_2+\cdots+x_k$ と置く。 $S_0,S_1,\ldots,S_{n+1}$ は $n+2$ 個の整数である。例 2.1を正の整数 $n+1$ と、この $n+2$ 個の整数に適用すると、差が $n+1$ の倍数となる二つ $S_i,S_j$ を選ぶことができる。添字を入れ替えて $0\le i<j\le n+1$ としてよい。このとき

S_j-S_i=x_{i+1}+x_{i+2}+\cdots+x_j

は $n+1$ の倍数である。 $i<j$ であるから、この和は少なくとも一つの項 $x_j$ を含む空でない連続部分の和である。▨

問題 4.3. 一辺の長さが $1$ の正方形の内部または周上に相異なる $n^2+1$ 個の点を置くと、距離が $\sqrt{2}/n$ 以下となる二点が存在することを示せ。

解答.

$n$ を正の整数とし、正方形を座標平面の $0\le x\le1$ 、 $0\le y\le1$ の部分とする。 $i,j=0,1,\ldots,n-1$ について、一辺の長さが $\dfrac1n$ の閉じた小正方形

Q_{ij}=\left\{(x,y)\ \middle|\ \frac in\le x\le\frac{i+1}n,\ \frac jn\le y\le\frac{j+1}n\right\}

を考える。小正方形は $n^2$ 個ある。

正方形の各点 $(x,y)$ を一つの小正方形に割り当てる。 $nx$ を超えない最大の整数と $n-1$ のうち小さい方を $i$ 、 $ny$ を超えない最大の整数と $n-1$ のうち小さい方を $j$ とする。 $x<1$ なら $i$ は $nx$ を超えない最大の整数であるから $\dfrac in\le x<\dfrac{i+1}n$ であり、 $x=1$ なら $i=n-1$ で $\dfrac{n-1}n\le x=\dfrac nn$ である。 $y$ と $j$ についても同じであるから、 $(x,y)$ は $Q_{ij}$ に属する。この割り当てで、各点はちょうど一つの小正方形に割り当てられる。

$n^2+1$ 個の点を $n^2$ 個の小正方形に割り当てるので、鳩の巣原理により、同じ小正方形 $Q_{ij}$ に割り当てられた相異なる二点 $(x,y),(x',y')$ が存在する。二点はともに $Q_{ij}$ に属するので $|x-x'|\le\dfrac1n$ 、 $|y-y'|\le\dfrac1n$ であり、二点の距離は

\sqrt{(x-x')^2+(y-y')^2}\le\sqrt{\frac1{n^2}+\frac1{n^2}}=\frac{\sqrt2}n

を満たす。▨

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

1 部分列の長さによる分類

2 整数を別の量で分類する例

3 設計チェック

4 演習

前提記事