鳩の巣原理

▼ クリックで展開

整数を4で割った余りで分類すると、kを整数として、［4k］［4k+1］［4k+2］［4k+3］の4種類のグループに分類できる。

グループは4つしかない一方、相異なる整数は5つなので、2つ以上の整数が属するグループが最低1つは存在する。

その2つの整数をそれぞれ4p+j、4q+j（p,qは整数、jは0～3のいずれかの整数）とすると、2つの整数の差は

 

(4p+j)-(4q+j)=4(p-q)

 

p-qが整数のため、これは4の倍数

 

有名な「鳩の巣原理」で考える問題です。

「鳩の巣原理」とは、10羽の鳩を9個の巣に入れるとき2羽以上の鳩が入る巣が少なくとも1個あるという現象を一般化したもので、

 

n個以上のものをm個の箱に入れるとき、n>mならば、2個以上のものが入る箱が少なくとも1個ある

 

というものです。

 

 

 

 

日常生活でも、「10階建て（地下なし）の建物の1Fからエレベーターに10人乗った時、必ず2人以上降りるフロアがある」といったように応用できますね。

 

単純な話なのですが、図形や整数問題にも用いられることがあり、面白いものがたくさんあります。

難関大学を目指す受験生は必ず頭の隅には置いておく必要があります。