منو
 کاربر Online
568 کاربر online
تاریخچه ی: اصل لانه کبوتر

در حال مقایسه نگارشها

نگارش واقعی نگارش:1
اصل لانه کبوتر که به نام های «اصل جعبه کفش» یا «اصل کشویی دیر کله» مشهور است، اغلب برای پاسخ دادن به سوالات زیر مفید است:
«آیا اشیایی وجود دارند که درخاصیت مشخصی صدق کنند؟»
اگر اصل لانه کبوتر به طور موفقیت آمیزی به کار رود، تنها وجود چنین اشیایی را ثابت می کند و چیزی درباره روش یافتن اشیا و یا مشخص کردن تعداد آنها بیان نمی کند.

شکل ساده اصل لانه کبوتری

n کبوتر در k لانه قرار می گیرند. اگر n>k ،آنگاه تعدادی از لانه ها بیش از یک کبوتر خواهند داشت.

برهان

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


img/daneshnameh_up/2/29/kab.gif


مثال

ده نفر به اتاقی وارد شده اند که نام کوچک آنها احمد، رضا و مهدی است و نام خانوادگی آنها محمدیان، رسولی و رضایی است. نشان دهید حداقل دو نفر از این ده نفر، نام و نام خانوادگی یکسانی دارند.
حل: تنها 9 امکان برای تولید اسامی متمایز وجود دارد. اگر افراد را به عنوان کبوتر اسامی را به منزله لانه کبوتر فرض کنیم، آنگاه بنا بر اصل لانه کبوتر، بعضی از اسامی (لانه ها) به حداقل دو نقر (کبوتر ها) نسبت داده می شوند.
حال مثال دیگری ذکر میکنیم:
15 نفر دریک میهمانی شرکت کرده اند. طبق این اصل حداقل دو نفر پیدا می شوند که در یک ماه به دنیا آمده اند.

همچنین ببینید:

ریاضیات گسسته



اصل لانه کبوتری
مطابق این اصل اگر n کبوتر و m لانه داشته باشم و تعداد کبوتر ها بیشتر از لانه ها باشد، آنگاه لااقل یک لانه یافت می شود که در آن حداقل دو یا بیشتر کبوتر وجود داشته باشد.
این اصل را بیشتر در احتمالات و مجموعه اعداد گسسته استفاده می کنند.

مثالهای مربوط به اصل لانه کبوتری:

مثال1) 15 نفر دریک میهمانی شرکت کرده اند. طبق این اصل حداقل دو نفر پیدا می شوند که در یک ماه به دنیا آمده اند.
مثال2) اگر S یک مجموعه 20 عضوی از اعداد طبیعی باشد، و این اعداد را بر 19 تقسیم کنیم آنگاه طبق این اصل حداقل دو عدد در این مجموعه یافت می شوند که باقیمانده آن ها در تقسیم بر عدد 19 یکسان باشد.

مجموعه Sاز 20 عضو تشکیل شده و طبق الگوریتم تعداد باقیمانده های تقسیم یک عدد صحیح بر 19، 19 تا می باشند. پس با داشتن 20 عدد مقسوم علیه، و 19 عدد باقیمانده، طبق اصل لانه کبوتری، حداقل دو عدد یافت می شوند که باقیماندشان در تقسیم بر عدد 19 یکسان باشد.

پیوست مربوطه:


تاریخ شماره نسخه کاربر توضیح اقدام
 سه شنبه 20 اردیبهشت 1384 [10:44 ]   5   علی هادی      جاری 
 سه شنبه 20 اردیبهشت 1384 [10:33 ]   4   علی هادی      v  c  d  s 
 سه شنبه 20 اردیبهشت 1384 [10:21 ]   3   علی هادی      v  c  d  s 
 دوشنبه 08 فروردین 1384 [20:27 ]   2   احمد شکیب      v  c  d  s 
 دوشنبه 08 فروردین 1384 [20:14 ]   1   احمد شکیب      v  c  d  s 


ارسال توضیح جدید
الزامی
big grin confused جالب cry eek evil فریاد اخم خبر lol عصبانی mr green خنثی سوال razz redface rolleyes غمگین smile surprised twisted چشمک arrow



از پیوند [http://www.foo.com] یا [http://www.foo.com|شرح] برای پیوندها.
برچسب های HTML در داخل توضیحات مجاز نیستند و تمام نوشته ها ی بین علامت های > و < حذف خواهند شد..