اصل لانه کبوتر

اصل لانه كبوتر بسیار روشن است و بسیار ساده به نظر می‌رسد، گویی دارای اهمیت زیادی نیست، ولی در عمل این اصل دارای اهمیت و قدرت بسیار زیادی است، زیرا تعمیمهای آن حاوی نتایجی عمیق در نظریه تركیباتی و نظریه اعداد است. وقتی می‌گوئیم در هر گروه سه نفری از مردم حداقل دو نفر، هم جنس‌اند در واقع اصل لانه كبوتر را به كار گرفته‌ایم. فرض كنیم به تازگی در دانشكده‌ای، یك گروه علوم كامپیوتر تاسیس یافته كه برای 10 عضو هیئت علمی آن فقط 9 دفتر‌كار موجود باشد. آن‌گاه باز هم ایده نهایی در پشت این ادعای بدیهی كه حداقل از یك دفتر‌كار بیشتر از یك نفر است استفاده می‌كنند، اصل لانه كبوتر است. اگر به جای 10 نفر 19 عضو هیئت علمی وجود داشته باشد، آن‌گاه حداقل از یك دفتر‌كار بیشتر از دو نفر استفاده می‌كنند. همین‌طور، اگر در دانشكده‌ای حداقل 367 دانشجو وجود داشته باشند، باز آشكار است S حداقل دو نفر از آنها روز تولدشان یكی است. می‌گویند كه سرانسان دارای حداكثر 999 و 99 تار مو است. از این رو در شهری S جمعیت آن بیشتر از 4 میلیون باشد، حداقل 41 نفر وجود دارند كه تعداد موهای سرشان یكی است (سر طاس مو ندارد). مثالهای زیادی نظیر این را می‌توانیم نقل كنیم.

ایده اساسی حاكم بر همه‌ی این موارد حقیقت ساده‌ای مشهور به اصل لانه‌كبوتر دیر بلكه است.

كه عبارت است از:

فرض كنید ‌k و n دو عدد طبیعی‌اند. اگر بخواهیم بیشتر از nk+1 شی را در n جعبه قرار دهیم، حداقل یك جعبه وجود دارد كه در آن حداقل k+1 شی قرار گرفته باشد. در حالت خاص، اگر حداقل n+1 شی را در n جعبه قرار دهیم، جعبه‌ای وجود دارد كه در آن حداقل دو شی قرار گرفته باشد.