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

تجسمی برای نام اصل: کبوترها در لانه‌ها. در این‌جا n = 7 و m = 9 بنابراین می‌توانیم نتیجه بگیریم که حداقل دو لانه کبوتر خالی وجود دارد. (که اگر دقیقاً دو کبوتر در یک لانه قرار گرفته باشند، سه خانهٔ خالی وجود دارد)

اصل لانهٔ کبوتری (به انگلیسی: 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 است) وجود دارند که با تعداد یکسان دیگری دست داده‌اند .

شمارش مو

می‌توانیم نشان بدهیم در لندن حداقل ۲ نفر وجود دارند که تعداد موی یکسانی بر سر خود دارند. از آنجا که یک فرد معمولی به‌طور متوسط ۱۵۰۰۰۰ مو بر روی سر خود دارد منطقی است که فردی با بیش از ۱۰۰۰۰۰۰ تار مو بر سر خود وجود نداشته باشد. در لندن بیش از یک میلیون نفر زندگی می‌کند اکنون تعداد لانه‌ها را برابر یک میلیون در نظر گرفته و کبوترها را تعداد افرادی که در لندن زندگی می‌کنند در نظر می‌گیریم(n>1000000) پس طبق اصل لانه کبوتری حداقل ۲ نفر وجود دارن که تعداد موی یکسانی بر روی سر خود دارند.

روز تولد

مسئلهٔ روز تولد بیان می‌کند برای یک مجموعهٔ n نفری از افراد انتخاب شده به‌طور تصادفی احتمال وجود افراد با روز تولد یکسان چقدر است؟ با استفاده از اصل لانه کبوتری می‌توان نشان داد اگر ۳۶۷ نفر را در یک اتاق جمع کنیم حداقل ۲ نفر وجود دارند که روز تولد یکسان دارند.

استفاده‌ها و کاربردها

اصل لانه کبوتری در علوم کامپیوتر به کار می‌رود برای مثال تداخل در جدول هش اجتناب ناپذیر است زیرا تعداد کلیدهای امکان‌پذیر از تعداد اندیسهای آرایه بیشتر است. الگوریتم هش از این تداخل‌ها نمی‌تواند جلوگیری کند. این اصل می‌تواند برای اثبات الگوریتم فشرده‌سازی بی‌اتلاف داده‌ها استفاده شود، به صورتی که داده‌های ورودی را کوچکتر می‌کند همچنین برخی از داده‌ها را بزرگتر می‌کند. به‌طور دیگر مجموعهٔ همهٔ رشته‌های ورودی به میزان طول داده شدهٔ L می‌توانند به مجموعه‌ای از همهٔ رشته‌ها به طول کمتر از L و بدون تداخل نگاشته شوند.

اصل لانه کبوتری (صورت تعمیم یافته)

صورت تعمیم یافته از این اصل بیان می‌کند که اگر n شی گسسته در m جعبه قرار داده شوند در این صورت حداقل یک جعبه داریم که در آن حداقل $\lceil n/m\rceil$ شی وجود دارد. $\lceil x\rceil$ سقف x کوچکترین عدد صحیح بزرگتر یا مساوی x را نشان می‌دهد به‌طور مشابه در حداقل یک ظرف نباید بیش از $\lfloor n/m\rfloor$ شی داشته باشیم. صورت تعمیم یافتهٔ این اصل در احتمال بیان می‌کند که اگر n کبوتر با احتمال یکسان 1/m به صورت تصادفی در m لانه قرار بگیرند در این صورت حداقل یک لانه بیشتر از یک کبوتر را با احتمال $1-{\frac {(m)_{n}}{m^{n}}}\!$ نگهداری می‌کند که در آن

(m)_n=m(m − 1)(m − 2)...(m − n + 1)

تعمیم بیشتر آن در احتمال این است که وقتی یک متغیر تصادفی حقیقی X میانگین متناهی(E(X را دارد، احتمال آن غیر صفر است که X بزرگتر یا مساوی (E(X باشد و به‌طور مشابه احتمال آن غیر صفر است که X کوچکتر یا مساوی (E(X باشد. برای این که ببینیم این نتیجهٔ اصل لانه کبوتری است هر ترکیب ثابت از n کبوتر در m لانه را در نظر می‌گیریم و X را تعداد کبوترهایی در نظر می‌گیریم که به‌طور تصادفی و یک نواخت در یک لانه قرار گرفته‌اند. میانگینX برابر n/m است؛ بنابراین اگر کبوترهای بیشتری از تعداد لانه‌ها داشته باشیم میانگین بیشتر از یک است بنابراین X اغلب حداکثر ۲ است.

مجموعه‌های نامتناهی

اصل لانه کبوتری نسبت به مجموعه‌های نامتناهی با استفاده از اعداد کاردینال (اصلی) تعمیم داده شود. اگر کاردینالیتی مجموعهٔ A بزرگتر از کاردینالیتی مجموعهٔ B باشد تناظر یک به یکی از A به B وجود ندارد اگر چه در این فرم این اصل همواره صادق (راستگو) است، از آنجا که معنای این عبارت که کاردینالیتی A بزرگتر از کاردینالیتی B است دقیقاً همان چیزی است که تناظر یک به یکی بین A و B وجود ندارد. آنچه وضعیت مجموعه‌های متناهی را جالب می‌کند این است که اضافه کردن حداقل یک عضو به یک مجموعه کافیست تا مطمئن شویم کاردینالیتی افزایش میابد.

منابع

مشارکت‌کنندگان ویکی‌پدیا. «Pigeonhole principle». در دانشنامهٔ ویکی‌پدیای انگلیسی، بازبینی‌شده در ۱۷ اکتبر ۲۰۱۷.