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

از ویکی‌پدیا، دانشنامهٔ آزاد
پرش به: ناوبری، جستجو
تجسمی برای نام اصل: کبوترها در لانه‌ها. در این‌جا 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). حداقل تعداد جوراب‌هایی که لازم است تا مطمئن شویم که یک جفت همرنگ داریم برابر m+1 است. (زیرا ممکن است از بین m جوراب همگی هم‌رنگ باشند)

دست دادن[ویرایش]

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

شمارش مو[ویرایش]

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

روز تولد[ویرایش]

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

استفاده‌ها و کاربردها[ویرایش]

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

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

صورت تعمیم یافته از این اصل بیان می‌کند که اگر n شی گسسته در m جعبه قرار داده شوند در این صورت حداقل یک جعبه داریم که در آن حداقل شی وجود دارد. سقف x کوچکترین عدد صحیح بزرگتر یا مساوی x را نشان می‌دهد به طور مشابه در حداقل یک ظرف نباید بیش از شی داشته باشیم. صورت تعمیم یافتهٔ این اصل در احتمال بیان می‌کند که اگر n کبوتر با احتمال یکسان m^-1 به طورت تصادفی در m لانه قرار بگیرند در این صورت حداقل یک لانه بیشتر از یک کبوتر را با احتمال نگه داری می‌کند که در آن

(m)n =m(m − 1)(m − 2)...(mn + 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 وجود ندارد. آنچه وضعیت مجموعه‌های متناهی را جالب می‌کند این است که اضافه کردن حداقل یک عضو به یک مجموعه کافیست تا مطمئن شویم کاردینالیتی افزایش میابد.

*Wikipedia contributors, «Pigeonhole principle,» Wikipedia, The Free Encyclopedia, http://en.wikipedia.org/w/index.php?title=Pigeonhole_principle&oldid=168917852 (accessed November 30, 2007).