اصل لانهکبوتری؛ تضمین وجود در مسائل شمارش
آموزش اصل لانهکبوتری ساده و تعمیمیافته، انتخاب لانه مناسب و حل تستهای تضمین وجود در شمارش.
پاسخ کوتاه
اصل لانهکبوتری به جای شمارش دقیق همه حالتها، وجود یک تکرار یا تراکم را تضمین میکند. بخش خلاقانه حل، تعریف درست «اشیا» و «لانهها» است؛ پس از آن یک تقسیم و گردکردن رو به بالا پاسخ را میدهد.
اصل ساده
اگر n+1 شیء را در n لانه قرار دهیم، دستکم یک لانه حداقل دو شیء دارد. این نتیجه مستقل از شیوه توزیع است. برای اثبات خلاف فرض میکنیم هر لانه حداکثر یک شیء دارد که در آن صورت بیش از n شیء جا نمیگیرد.
فرم تعمیمیافته
اگر N شیء در k لانه باشند، دستکم یک لانه حداقل ceil(N/k) شیء دارد. نماد ceil یعنی گردکردن رو به بالا. حتی اگر تقسیم دقیق نباشد، نمیتوان همه لانهها را کمتر از این مقدار نگه داشت.
انتخاب لانهها
در مسائل تاریخ تولد، ماهها یا روزها لانهاند؛ در باقیماندهها، کلاسهای پیمانهای؛ و در فاصلهها، بازهها. لانهها باید تمام حالتهای ممکن را بدون ابهام پوشش دهند. انتخاب لانه بسیار ریز یا نامرتبط کران مطلوب را نمیسازد.
تضمین حداقل تعداد
برای تضمین حداقل r شیء در یک لانه از k لانه، بیشترین حالتِ بدون تضمین k(r-1) شیء است. پس با k(r-1)+1 شیء حتماً یک لانه دستکم r عضو خواهد داشت. این فرمول شکل وارون اصل تعمیمیافته است.
مثال و تست کوتاه
با 13 نفر و 12 ماه، دستکم دو نفر ماه تولد یکسان دارند. برای تضمین سه نفر در یک ماه، 12×2+1=25 نفر لازم است؛ با 24 نفر هنوز ممکن است در هر ماه دقیقاً دو نفر باشند و تضمین سهتایی نداریم.
چکلیست حل تست
- ابتدا اشیا و لانهها را صریح نامگذاری کن.
- در فرم عمومی N/k را رو به بالا گرد کن.
- برای تضمین r عضو از k(r-1)+1 استفاده کن.