اصل لانه کبوتری: اگر تعداد اشیا از تعداد دستهها بیشتر باشد، دستکم یک دسته بیش از یک عضو دارد
بیان ساده و شهودی اصل لانه کبوتری
تصور کنید تعداد کبوترها بیشتر از تعداد لانهها باشد. اگر هر کبوتر وارد یک لانه شود، ناگزیر حداقل یک لانه وجود دارد که بیش از یک کبوتر در آن قرار گرفته است. این گزاره که به «اصل لانه کبوتری»1 معروف است، در نگاه اول بسیار بدیهی به نظر میرسد، اما همین اصل ساده پایهٔ بسیاری از استدلالهای عمیق در ریاضیات، علوم کامپیوتر و حتی مسائل روزمره است.
برای نمونه، در یک کلاس با ۳۳ دانشآموز، طبق این اصل حداقل دو نفر در یک ماه متولد شدهاند (چون تعداد ماهها ۱۲ است و ۳۳ از ۱۲ بیشتر است). این استدلال به ما اجازه میدهد بدون نیاز به بررسی تکتک افراد، یک نتیجهٔ قطعی بگیریم.
تقسیمبندی موضوع: حالتهای مختلف اصل لانه کبوتری
این اصل در دو شکل اصلی مطرح میشود: حالت ساده (که بیان شد) و حالت تعمیمیافته. در حالت تعمیمیافته، اگر $n$ شیء را در $k$ دسته بریزیم، آنگاه حداقل یک دسته شامل $\lceil n/k \rceil$ شیء خواهد بود. همچنین میتوان از مکمل آن استفاده کرد: اگر بخواهیم هیچ دستهای بیش از $m$ شیء نداشته باشد، حداکثر تعداد کل اشیاء برابر $k \times m$ خواهد بود.
| نوع اصل | شرط | نتیجه |
|---|---|---|
| ساده | $n = k+1$ | حداقل یک دسته شامل دستکم ۲ شیء |
| تعمیمیافته | $n \gt k$ (هر مقدار) | حداقل یک دسته شامل $\lceil n/k \rceil$ شیء |
کاربرد عملی و مثالهای عینی از زندگی روزمره
یکی از جذابیتهای اصل لانه کبوتری، کاربردهای فراوان آن در موقعیتهای به ظاهر غیرمرتبط است. فرض کنید یک کشوی جوراب شامل ۱۰ جفت جوراب آبی و ۱۰ جفت جوراب سفید دارید. در تاریکی مطلق، چند جوراب باید بردارید تا مطمئن شوید یک جفت همرنگ دارید؟ طبق اصل لانه کبوتری، ۳ جوراب کافی است (زیرا ۲ رنگ به عنوان لانه در نظر گرفته میشود و ۳ جوراب بیشتر از ۲ لانه است).
مثال دیگر: در یک مهمانی با ۱۳ نفر، حداقل دو نفر در یک ماه متولد شدهاند. همچنین اگر ۳۶۷ نفر جمع شوند، حداقل دو نفر روز تولد یکسانی دارند (چون تعداد روزهای سال ۳۶۶ روز است و ۳۶۷ نفر از آن بیشتر است). در علوم کامپیوتر، این اصل برای اثبات وجود برخورد در توابع درهمساز2 استفاده میشود: اگر تعداد ورودیهای ممکن بیشتر از تعداد خروجیهای تابع باشد، حداقل دو ورودی خروجی یکسان خواهند داشت.
چالشهای مفهومی و پاسخ به پرسشهای رایج
پرسش ۱: آیا اصل لانه کبوتری همیشه درست است؟ اگر همه اشیاء را عمداً طوری بچینیم که هر دسته دقیقاً یک شیء داشته باشد، چه؟
پاسخ: اصل لانه کبوتری یک قضیهٔ ریاضی است و همواره درست است. اگر تعداد اشیاء از تعداد دستهها بیشتر باشد، چیدن اشیاء به گونهای که هر دسته حداکثر یک شیء داشته باشد امکانپذیر نیست. زیرا حداکثر تعداد اشیایی که میتوان بدون داشتن دستهٔ تکراری توزیع کرد، برابر تعداد دستهها است. به محض اینکه یک شیء اضافه شود، ناچاراً به یکی از دستههای موجود اضافه میشود.
پرسش ۲: در حالت تعمیمیافته، چرا از تابع سقف $\lceil \cdot \rceil$ استفاده میشود و نه گرد کردن معمولی؟
پاسخ: تابع سقف $\lceil x \rceil$ کوچکترین عدد صحیح بزرگتر یا مساوی $x$ را میدهد. در اصل لانه کبوتری، تعداد اشیاء در دستهٔ پربارتر باید عددی صحیح باشد و نمیتواند کسری باشد. مثلاً اگر $n=5$ و $k=2$، آنگاه $n/k = 2.5$ و سقف آن $3$ است، یعنی حداقل یک دسته شامل $3$ شیء خواهد بود (و اگر گرد کنیم $2$ میشود که نادرست است).
پرسش ۳: آیا اصل لانه کبوتری فقط در ریاضیات گسسته کاربرد دارد یا در آمار و احتمال هم استفاده میشود؟
پاسخ: بله، این اصل در آمار و احتمال نیز کاربرد دارد. برای نمونه، در مسئلهٔ «تولدهای تکراری» (Birthday Problem) از این اصل برای اثبات وجود دستکم دو نفر با تولد یکسان استفاده میشود. هرچند در مسائل احتمالی معمولاً احتمال وقوع پدیده محاسبه میشود، اما اصل لانه کبوتری یک تضمین صددرصدی (یقینی) ارائه میدهد، نه یک احتمال.
چند مثال ریاضی برای تمرین بیشتر
در یک کیسه ۵۰ عدد داریم که هر عدد یا فرد است یا زوج. اگر ۵۱ عدد انتخاب کنیم، طبق اصل لانه کبوتری حداقل ۲ عدد دارای یک نوع زوجیت هستند. همچنین در یک صفحهٔ شطرنج ۸×۸ اگر خانهها را به ۶۴ لانه و مهرهها را اشیاء در نظر بگیریم، قرار دادن ۶۵ مهره روی صفحه تضمین میکند که حداقل دو مهره در یک خانه قرار گرفتهاند (غیرممکن است، چون هر خانه فقط یک مهره میگیرد). این مثال نشان میدهد که اصل لانه کبوتری گاهی به نادرستی یک وضعیت پی میبرد (امکانناپذیری توزیع بدون اشتراک).
پاورقی
1 اصل لانه کبوتری (Pigeonhole Principle): قضیهای در ترکیبیات که میگوید اگر تعداد اشیاء بیشتر از تعداد ظرفها باشد، حداقل یک ظرف بیش از یک شیء دارد.
2 تابع درهمساز (Hash Function): تابعی که ورودی با اندازه دلخواه را به خروجی با اندازه ثابت نگاشت میکند. برخورد زمانی رخ میدهد که دو ورودی متفاوت خروجی یکسان داشته باشند.