ウィキペディア

鳩の巣原理

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2011/10/21 02:16 UTC 版)

鳩の巣原理（はとのすげんり）またはディリクレの箱入れ原理（—はこいれげんり）とは、n 個の物を m 個の箱に入れるとき、n > m であれば、少なくとも1個の箱には1個より多い物が中にある、という原理である。別の言い方をすれば、1つの箱に1つの物を入れるとき、m 個の箱には最大 m 個の物しか入れることができない（もう1つ物を入れたいなら、箱の1つを再利用しないといけないから）、ということである。