Competitive Programming Advent Calendar 2016 23日目の記事です。
鳩の巣原理と、競技プログラミングでの使われ方を紹介します。
鳩の巣原理とは
昔々あるところに、5羽の鳩がおりました。彼らをすべて巣箱に入れたいのですが、あいにく巣は4つしかありませんでした。 すると以下の図のように、どこか1つの巣には2羽以上の鳩が入ってしまいます。
適当な入れ方をすると、2羽より多い巣があったり、空の巣があるかもしれません。でも、どんな入れ方をしても「どこかの巣には2羽以上」入ることが保証されます 。
一般に n 羽の鳩を m < n 個の巣にいれるとき、どこか 1 つの巣には鳩が2羽以上入ります。
更に一般化。巣に入っている鳩の最大数を最小化しようとすると、各巣になるべく均等に鳩を配る形になります。 このとき、鳩の数の最大値は *1 となり、これが最大値の下限になります。 以下の図は n = 10, m = 4 とした例で、最低でも3羽以上の鳩が入っている巣があることを示しています。
*1:小数点以下を切り上げる