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

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

اصل لانه کبوتری (به انگلیسی: Pigeonhole principle)، که با نام اصل جعبه (یا کشوی) دیریکله نیز شناخته می‌شود، بیان می‌کند که اگر دو عدد طبیعی n و m را با خاصیت n>m داشته باشیم، اگر n شیء در m لانه کبوتر قرار گیرد، آن‌گاه حداقل یک لانه کبوتر (یا قفسه) دارای بیش از یک شیء خواهد بود. بیانی دیگر از این اصل به این صورت است که اگر در m لانه حداکثر m شیء آن هم با شرط در هر لانه یک شیء، قرار گرفته است؛ اضافه کردن یک شیء دیگر ما را مجبور می‌کند که از یکی از لانه‌ها بار دیگر استفاده کنیم (با این شرط که m متناهی باشد).به طور رسمی این قضیه بیان میکند :"در مجموعه های متناهی تابعی یک به یک وجود ندارد که برد آن کوچکتر از دامنه ی آن باشد ." تجسم این تئوری در زندگی واقعی اینگونه میتواند باشد که در " یک گروه 3 تایی از دستکشها حد اقل 2 دستکش متعلق به یک دست ( راست یا چپ) میباشند ." اصل لانه کبوتری مثالی از اصل شمارش است با وجود این که بدیهی به نظر میرسد با استفاده از آن میتوان حکم های غیر منتظره را ثابت کرد ، برای مثال: " دو نفر در لندن وجود دارند که دارای تعداد موهای یکسان اند ".

اعتقاد هست که نخستین بیان این قضیه به وسیلهٔ دیریکله در سال ۱۸۳۴ تحت نام Schubfachprinzip («اصل کشو» یا «اصل قفسه») مطرح شده‌است. نام اصلی اصل جعبه هنوز در فرانسه ("principe des tiroirs") و در لهستان "(zasada szufladkowa)" و مجارستان ("skatulyaelv") و در ایتالیا ("principio dei cassetti") و آلمان ("Schubfachprinzip") و در دانمارک ("Skuffeprincippet") و در چینی ("抽屉原理") نامیده میشود . قضایای پیشرفته ریاضی مانند لم سیگل با این مفهوم اثبات شده اند .

مثال ها[ویرایش]

تیم بیسبال[ویرایش]

فرض کنیم 5 نفر میخواهند در 4 تیم بیسبال بازی کنند .( n=5 ,m=4 ) اصل لانه کبوتری میگوید که همه ی آنها نمیتوانند در تیم های مختلف بازی کنند . حد اقل 2 نفر باید در یک تیم مشابه بازی کنند.

انتخاب جوراب[ویرایش]

فرض کنید شما ترکیبی از جوراب های آبی و مشکی دارید حداقل تعداد جوراب هایی که لازم است تا مطمئن شویم که یک جفت جوراب با رنگ یکسان داریم چقدر است ؟ با استفاده از اصل لانه کبوتری برای داشتن یک جفت همرنگ ( m=2 ) ما به 3 جوراب ( کبوتر ) نیاز داریم .

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

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

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

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

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

مساله ی روز تولد بیان میکند برای یک مجموعه ی n نفری از افراد انتخاب شده به طور تصادفی احتمال وجود افراد با روز تولد یکسان چقدر است ؟ با استفاده از اصل لانه کبوتری میتوان نشان داد اگر 366 نفر را در یک اتاق جمع کنیم حداقل 2 نفر وجود دارند که روز تولد یکسان دارند .

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

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

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

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

(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 اغلب حداکثر 2 است.

مجموعه های نامتناهی[ویرایش]

اصل لانه کبوتری نسبت به مجموعه های نامتناهی با استفاده از اعداد کاردینال(اصلی) تعمیم داده شود . اگر کاردینالیتی مجموعه ی 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 ۳۰, ۲۰۰۷).