鳩ノ巣原理

シェアする

 

鳩ノ巣原理とは

難しい原理ではありません。

 

例えば、ハトが10羽います。で、巣が9つしかないとすると全てのハトが巣に戻ると必ずどこかの巣は複数のハトが入ってしまいます。

これが鳩ノ巣原理です。

 

 

一般

\(m>n \) とする。\(m\) 個の対象物(ハト)\(n\) 個の入れ物等(巣)に入れると少なくとも一つの入れ物には\(\biggl[\displaystyle\frac{m}{n}\biggr]\) 個以上いる(ある)。

 

落ち着いて考えれば、言っていることは大したことではありません。

 

例題

数学の問題での適用例

 問題

 

10個の自然数を取ってくる。

この内、二つを\(m\) と\(n\) とする。

\(m-n\) が9の倍数となる組が必ずあることを示せ。

 

\(m-n\) が9の倍数とは\(m\) と \(n\) が9を法として合同である(9で割った余りが等しい)ということ。

 

一般に、自然数を\(9\)で割った余りは\(0\)から\(8\)の\(9\)種類しかありえない。

そして今、自然数は10個あるので鳩ノ巣原理より必ず2つは9で割った余りが同じ、つまり\(m-n\) が9の倍数となる組が必ずある

 

 

シェアする