اصل لانه كبوتر

[nafise sadeghi]

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


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

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


برهان

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





مثال

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