قالب اثبات
اشیا، لانهها و تعداد هرکدام را مشخص کن. برای اثبات وجود حداقل r عضو در یک لانه، میتوان فرض کرد همهٔ لانهها حداکثر r−1 عضو دارند و نشان داد ظرفیت کل از تعداد اشیا کمتر میشود.
اشیا ← لانهها ← n و k ← سقف n/k یا ظرفیت خلاف ← نتیجهٔ تضمینی
سؤال ۱: ماه تولد
در میان ۱۳ نفر، چرا دستکم دو نفر در یک ماه به دنیا آمدهاند؟
پاسخ تشریحی
۱۳ نفر اشیا و ۱۲ ماه لانهاند. چون ۱۳>۱۲، دستکم یک ماه حداقل دو نفر دارد.
سؤال ۲: چهار گروه
حداقل چند دانشآموز لازم است تا تضمین شود در یکی از چهار گروه حداقل ۵ نفر باشند؟
پاسخ تشریحی
اگر هر گروه حداکثر ۴ نفر داشته باشد، ۱۶ نفر جا میگیرند. نفر هفدهم وجود گروه ۵نفره را تضمین میکند.
سؤال ۳: باقیمانده تقسیم
از میان ۲۰ عدد صحیح، ثابت کنید دستکم سه عدد باقیمانده یکسانی در تقسیم بر ۷ دارند.
پاسخ تشریحی
هفت باقیماندهٔ ۰ تا ۶ لانهاند. سقف ۲۰/۷=۳؛ پس یک لانه حداقل سه عدد دارد.
سؤال ۴: زوج و فرد
چرا میان هر سه عدد صحیح، دو عدد همزوجیت وجود دارد؟
پاسخ تشریحی
سه عدد میان دو دستهٔ زوج و فرد توزیع میشوند؛ دستکم یک دسته دو عضو دارد.
سؤال ۵: جوراب
در کشویی فقط جورابهای سه رنگ وجود دارد. بدون دیدن رنگ، حداقل چند جوراب برداریم تا دو جوراب همرنگ تضمین شود؟
پاسخ تشریحی
در بدترین حالت سه جوراب نخست سه رنگ متفاوتاند؛ جوراب چهارم با یکی همرنگ است. پاسخ ۴.
سؤال ۶: حداقل بزرگتر
۵۱ پرونده در ۱۰ پوشه گذاشته شدهاند. حداقل چند پرونده در یکی از پوشهها تضمین میشود؟
پاسخ تشریحی
سقف ۵۱/۱۰=۶؛ پس یک پوشه دستکم ۶ پرونده دارد.
سؤال ۷: نشاندادن عدم تضمین
آیا با ۲۰ شیء و ۵ جعبه میتوان وجود جعبهای با حداقل ۵ شیء را تضمین کرد؟
پاسخ تشریحی
خیر. سقف ۲۰/۵=۴ فقط حداقل ۴ را تضمین میکند؛ میتوان در هر جعبه دقیقاً ۴ شیء گذاشت، پس وجود جعبهٔ ۵عضوی الزامی نیست.
سؤال ۸: نقطهها در مربع
مربع را به ۴ ناحیه تقسیم کردهایم و ۹ نقطه در آن قرار میدهیم. چه چیزی تضمین میشود؟
پاسخ تشریحی
سقف ۹/۴=۳؛ دستکم یک ناحیه حداقل ۳ نقطه دارد.
سؤال ۹: تولد و روز سال
با فرض ۳۶۵ روز ممکن، حداقل چند نفر وجود دو نفر با روز تولد یکسان را تضمین میکند؟
پاسخ تشریحی
۳۶۶ نفر؛ در بدترین حالت ۳۶۵ نفر روزهای متفاوت دارند و نفر بعدی تکرار ایجاد میکند.
سؤال ۱۰: ساخت کران عمومی
برای تضمین حداقل r شیء در یکی از k جعبه، حداقل چند شیء لازم است؟
پاسخ تشریحی
k(r−1)+1. با k(r−1) شیء میتوان در هر جعبه r−1 گذاشت؛ یک شیء بیشتر یکی از جعبهها را به r میرساند.
برگهٔ خودتصحیح
نتیجهٔ «حداقل تضمینی» را با امکان یک توزیع مرزی کنترل کن. راهنمای کامل در اصل لانهکبوتری آمده است.