次: 最小自然数の存在 上: 存在の証明 前: 存在の直接証明

存在の間接証明−鳩の巣論法

しかしいつもこのように実際に条件を満たすものをもってくることができるとはかぎらない．また，存在はするが実際に書き出すことはできない，ということもある．つまり作ることができるかできないかはわからないが，存在することは間違いない，この論証だ． 一つ例を考えよう．

大阪市には頭髪の本数が同じである二人が少なくとも一組存在する．

これを証明せよ．

人間の頭髪がどれくらいあるかはもちろん人によりけりだ． 私なんかは当然少ない方だが，たとえ $1mm$四方に10本とし，頭皮を $30cm\times 30cm$としても90万本， これを越えることはない． 大阪市の人口は90万人より多い． これらの人の頭髪の本数がすべて異なると仮定すれば， 小さい方から並べると最後の人は大阪市の人口より多い頭髪でなければならないが， それはあり得ない． ゆえに必ず少なくとも一組，頭髪の本数が同じ人が存在する！

これが有限個のもののなかでの存在を保証する「鳩の巣原理」である． 注意すべきは「私と同じ本数の人がいる」は一般には成立しないということだ．だから誰と誰が頭髪の本数が等しいのかはわからないし， それはまた別の問題である．

例題 1.17       ［89広島大学］

次の文章は，ある条件を満たすものが存在することを証明する際に，よく使われる 「鳩の巣原理」（または，抽出（ひきだ）し論法ともいう）を説明したものである．

「 $m$ 個のものが， $n$ 個の箱にどのように分配されても， $m>n$ であれば， 2個以上のものが入っている箱が少なくとも一つ存在する」

この原理を用いて，次の二つの命題が成り立つことを証明せよ．

1. 1辺の長さが2の正三角形の内部に， 任意に5個の点をとったとき，その内の2点で， 距離が1より小さいものが少なくとも1組存在する．
2. 座標空間で，その座標がすべて整数であるような点を格子点という． 座標空間に9個の格子点が与えられたとき，その内の2点で， 中点がまた格子点であるものが 少なくとも1組存在する．

考え方     これは問題文のなかの 5 とか 9 とかの数がヒントになる． 1.は正三角形を，その中の二点の距離が必ず1より小さくなる四つの領域にわけられればよい． 2.は中点が格子点であるために両端はどのような性質を持っていなければならないのかを考える．

解答

1. 正三角形を各辺の中点を結んでさらに1辺の長さが1の小正三角形四つに 分割する．小正三角形の各頂点はもとの正三角形の辺上にある．

   $m=5$ ， $n=4$ で「鳩の巣原理」を適用すると，四つの小正三角形のうち少なくとも 一つの小正三角形の内部または周上には二つの点がくる． かつ，点はもとの正三角形の内部に取るのであるから， いずれの点も小正三角形の頂点には来ない．

   三角形の内部および周上にある二点間の距離は最大辺の長さを越えない． 従ってその距離は1より小さい．

2. 二点の中点が格子点であることと， 二点の$x,\ y,\ z$ 座標の和がそれぞれ偶数であることは同値である． 和が偶数になるためには， その二数の偶数か奇数かが一致していればよい． (偶数，奇数，偶数)のような組合せは全部で$2^3=8$より八通である． $m=9$ $n=8$ で鳩の巣原理を適用すれば， 少なくとも一組$x,\ y,\ z$各座標の偶数か奇数かが 一致するものができる． その二点の中点は，格子点である．□

「三角形の内部および周上にある二点間の距離は最大辺の長さを越えない」 が明かでない人はさらに考えておこう． 二点 P, Q が三角形の内部にあれば直線PQと三角形の辺の交点をR, Sとする． RやSが頂点でなければRを固定しSを辺上で動かすと，Sが一方の方向に動くときRSは増加する． ゆえにSが頂点に来たときの方が長い．Rについても同様．

この論法は大変重要なものなのでいくつか演習にあげておいた．歴史上もっとも有名なものは 次の定理の証明である．

定理 2
    $\omega$ を与えられた無理数とする．このとき

$$\vert x-\omega y\vert < \dfrac{1}{y}$$

となる整数 $x,\ y$ が 無数に 存在する．

解説     この証明は『数論初歩』「ペル方程式の解の存在」［実数の近似定理］にある． それは単独で理解できることなのでぜひよく味わっておいてほしい． この定理はディリクレの定理といわれ， 整数問題で鳩の巣原理がもっとも本格的に用いられる． この定理にちなんで鳩の巣原理による論法のことを「ディリクレ論法」ともいう．

証明

1. 任意の自然数 $n$ に対して，
   
   $$0<y\le n, \,\, \vert x-\omega y\vert<\dfrac{1}{n}$$
   
   
   となる整数$(x,\ y)$ が少なくとも一組存在することを示す．

   実数 $a<b$ に対して $a$ を含み $b$ を含まない区間を $[a,b)$ と表す． 区間 $[0,1)$ を次のように $n$ 等分する．
   

   $$\left[0,\dfrac{1}{n}\right),\,\,\left[\dfrac{1}{n},\dfrac{2}{n}\right), \cdots ,\left[\dfrac{n-1}{n},1\right)$$
   
   
   $y$に $0,1, \cdots , n$ の各値を与え，その $y$ に対して， $\omega y$ を超えない最大の整数を $x$ とする．
   
   $$0 \le \omega y-x <1$$
   
   
   である．これらは全部で $n+1$ 個あるので， 鳩の巣原理によって上の$n$個のうち少なくとも一つの区間には， 二つ以上の $\omega y-x$ が属する． $\omega y_1-x_1$， $\omega y_2 -x_2$， $(x_1\ne x_2)$が同じ区間に属するとする．つまり
   
   $$\vert(\omega y_1-x_1)-(\omega y_2-x_2)\vert < \dfrac{1}{n}$$
   
   
   $y_1>y_2$とし， $x=x_1-x_2,\ y=y_1-y_2$ とおく． この$(x,\ y)$に対して
   
   $$\vert\omega y-x\vert < \dfrac{1}{n}$$
   
   
   である．
2. 各自然数 $n$ に対して $0<y\le n$で $\vert\omega y-x\vert < \dfrac{1}{n}$ となる $(x,\ y)$ が 存在した． $n$ を動かすとき， これらの $(x,\ y)$のなかに相異なるものが無数にあることを示す．

   もし有限個しかなかったとする． そのなかで $\vert\omega y-x\vert$ の値が最小のもの を $\vert\omega y_0-x_0\vert$ とする．それに対して，
   

   $$\dfrac{1}{n}<\vert\omega y_0-x_0\vert$$
   
   
   となる $n$ をとる． この $n$ に対して再び， $\vert\omega y-x\vert < \dfrac{1}{n}$ と なるように$(x,\ y)$を選ぶことができる．ところが
   
   $$\vert\omega y-x\vert<\dfrac{1}{n}<\vert\omega y_0-x_0\vert$$
   
   
   なので， $(x_0,y_0)$ の最小性と矛盾した．

   よって相異なるものは無数にある． $\dfrac{1}{n}<\dfrac{1}{y}$なので
   

   $$\vert\omega y-x\vert < \dfrac{1}{y}$$
   
   
   となる$(x,\ y)$が無数にあることが示された． □

鳩の巣原理は次の形で用いることもある．

整数 $a_1,\ a_2,\ \cdots,\ a_n$ はすべて $1 \le a_1,\ a_2,\ \cdots,\ a_n \le n$ を満たし，さらにすべて異なる．このとき， $a_1,\ a_2,\ \cdots,\ a_n$は$1〜n$の値を一回ずつとる．

なぜなら，もし $a_1,\ a_2,\ \cdots,\ a_n$ のなかに， $1〜n$ でとらない値があったとする． その値を除く数を記した箱を用意する．箱の数は $n-1$ 個以下になる． 数 $a_1,\ a_2,\ \cdots,\ a_n$をその値にしたがってこれらの箱に入れる． 鳩の巣原理によって 同じ箱に入るものが少なくとも一組できる． これは $a_1,\ a_2,\ \cdots,\ a_n$の値が すべて異なることに矛盾する． ゆえに $a_1,\ a_2,\ \cdots,\ a_n$は$1〜n$の値を一回ずつとる．

鳩の巣論法はこの形で一次不定方程式の解の存在の証明に用いられる．

例題 1.18       ［00大阪女子大］

1. $4m+6n=7$ を満たす整数 $m,\ n$ は存在しないことを示せ．
2. $3m+5n=2$ を満たすすべての整数の組 $(m,\ n)$ を求めよ．

   以下， $a,\ b$ は互いに素な整数とする．

3. $k$ を整数とするとき， $ak$ を $b$ で割った余りを $r(k)$ で 表す． $k,\ l$ を $b-1$ 以下の正の整数とするとき， $k\ne l$ ならば $r(k)\ne r(l)$ であることを示せ．
4. $am+bn=1$ を満たす整数 $m,\ n$ が存在することを示せ．

考え方     この4. で鳩の巣原理が用いられる．そのことを念頭において，ぜひいちど自分で考えてほしい．

解答    

1. $4m+6n=7$ を満たす整数 $m,\ n$ が存在したとすれば 左辺は偶数であり，右辺は奇数なので矛盾する．ゆえに存在しない．
2. $3m+5n=2$ を満たす1組の $(m,\ n)$ として $(-1,\ 1)$ をとる． つまり
   
   $$3\cdot (-1)+5 \cdot 1=2 \quad \cdots\maru{1}$$
   
   
   ゆえに任意の解 $(m,\ n)$ に対して， $3m+5n=2$ から�@の両辺を引くことにより，
   
   $$3(m+1)+5(n-1)=0$$
   
   
   3と5は互いに素なので， $m+1$ は5の倍数．これを整数 $t$ を用いて $5t$ と書く．このとき
   
   $$(m,\ n)=(-1+5t,\ 1-3t)$$
   
   
   逆に任意の整数 $t$ に対して，この形をしたものが$3m+5n=2$ を満たす ことは明か．
   
   $$∴ \quad (m,\ n)=(-1+5t,\ 1-3t),\ t は任意の整数$$
   
   

3. 対偶を示す．
   $$\begin{eqnarray*} r(k)= r(l)&\iff &ak-al=a(k-l) が b の倍数\\ &&(a と b は互.. ... 、ャ b 、ホヌワソ・\ &&-(b-2)\le k-l\le b-2 なので\\ &\iff &k-l=0 \end{eqnarray*}$$
   
   
   よって $k\ne l$ ならば $r(k)\ne r(l)$ であることが示された．
4. $a$ と $b$ が互いに素なので， $1\le k \le b-1$ に対して $ak$ は $b$ の倍数とはならない．ゆえにこのとき $1\le r(k) \le b-1$ である．

   一方 $k\ne l$ ならば $r(k)\ne r(l)$ なので $r(1),\ r(2),\ \cdots ,\ r(b-1)$ はすべて異なる $b-1$ 個の整数で，すべて $1\le r(k) \le b-1$ をみたす．

   ゆえに鳩の巣原理により $r(1),\ r(2),\ \cdots ,\ r(b-1)$は $1,\ 2,\ \cdots,\ b-1$ の各値を一つずつとる． ゆえに$r(m)=1$ となる $m\ (1 \le m \le b-1)$ が存在する． つまり$am-1$ が $b$ の倍数である．これを $bn$ とおくと
   

   $$am-1=bn \quad$$
   
   
   すなわち，$am+bn=1$ を満たす整数 $m,\ n$ が存在することが示された． □

次: 最小自然数の存在 上: 存在の証明 前: 存在の直接証明