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

اصل لانهٔ کبوتری ( به انگلیسی: Pigeonhole principle ) ، که با نام اصل جعبه ( یا کشوی ) دیریکله نیز شناخته می شود، بیان می کند که اگر دو عدد طبیعی n و m را با خاصیت n> m داشته باشیم، اگر n شیء در m لانهٔ کبوتر قرار گیرد، آن گاه حداقل یک لانهٔ کبوتر ( یا قفسه ) دارای بیش از یک شیء خواهد بود. بیانی دیگر از این اصل به این صورت است که اگر در m لانه حداکثر m شیء آن هم با شرط در هر لانه یک شیء، قرار گرفته است؛ اضافه کردن یک شیء دیگر ما را مجبور می کند که از یکی از لانه ها بار دیگر استفاده کنیم ( با این شرط که m متناهی باشد ) . به طور رسمی این قضیه بیان می کند  :«در مجموعه های متناهی تابعی یک به یک وجود ندارد که برد آن کوچکتر از دامنهٔ آن باشد. » تجسم این تئوری در زندگی واقعی اینگونه می تواند باشد که «در هر گروه سه تایی از انسان ها حداقل دو نفر هم جنس هستند. » اصل لانهٔ کبوتری مثالی از اصل شمارش است با وجود این که بدیهی به نظر می رسد با استفاده از آن می توان حکم های غیرمنتظره را ثابت کرد، برای مثال: «دو نفر در لندن وجود دارند که دارای تعداد موهای یکسان اند. »
اعتقاد هست که نخستین بیان این قضیه به وسیلهٔ دیریکله در سال ۱۸۳۴ تحت نام Schubfachprinzip ( «اصل کشو» یا «اصل قفسه» ) مطرح شده است. برای نام اصلی اصل جعبه هنوز در فرانسه از ( "principe des tiroirs" ) ، در لهستان از ( "zasada szufladkowa" ) ، در مجارستان از ( "skatulyaelv" ) ، در ایتالیا از ( "principio dei cassetti" ) ، در آلمان از ( "Schubfachprinzip" ) ، در دانمارک از ( "Skuffeprincippet" ) و در چینی از ( "抽屉原理" ) استفاده می شود. قضایای پیشرفتهٔ ریاضی مانند لم سیگل با این مفهوم اثبات شده اند.
فرض کنیم ۵ نفر می خواهند در ۴ تیم بیسبال بازی کنند ( n=5 , m=۴ ) . اصل لانه کبوتری می گوید که همهٔ آن ها نمی توانند در تیم های مختلف بازی کنند. حد اقل ۲ نفر باید در یک تیم مشابه بازی کنند.
فرض کنید n جوراب آبی و m جوراب مشکی دارید ( m< n ) . حداقل تعداد جوراب هایی که لازم است تا مطمئن شویم که یک جفت غیر همرنگ داریم برابر n+1 است. ( زیرا ممکن است از بین n جوراب همگی هم رنگ باشند )
فرض کنیم n نفر وجود دارند ( n> 1 ) که هر کدام می توانند با دیگری دست بدهند. طبق اصل لانهٔ کبوتری همیشه ۲ نفر وجود دارند که با تعداد یکسانی از افراد دست داده اند. هرکس می تواند با ۰ تا n - 1 شخص دیگر دست بدهد اما تعداد لانه ها را n - 1 در نظر می گیریم زیرا اگر شخصی با ۰ نفر دست دهد شخص دیگری نمی تواند با n - 1 نفر دست بدهد و بلعکس. اکنون n - 1 لانه داریم و طبق اصل لانه کبوتری حد اقل ۲ شخص ( کبوتر که تعداد آنها n است ) وجود دارند که با تعداد یکسان دیگری دست داده اند .