۲۰ امتحان نهایی / گسسته · شمارش
شیء، لانه، تضمین

اصل لانهٔ کبوتری؛
اشیا و دسته‌ها را درست تعریف کن، سپس حد تضمینی را بساز

نام افراد یا عددها مهم نیست؛ باید روشن کنی چه چیزهایی توزیع می‌شوند و بر اساس چه ویژگی در چند دسته قرار می‌گیرند. نتیجه دربارهٔ تضمین است، نه میانگین دقیق هر دسته.

⌈n/m⌉

اشیا و لانه‌ها را صریح نام‌گذاری کن

اشیا مواردی هستند که دسته‌بندی می‌شوند و لانه‌ها دسته‌های ممکن. هر شیء باید طبق قاعده در یک دستهٔ مشخص قرار گیرد.

تعداد دسته‌ها را از ویژگی مسئله بگیر

ماه‌ها، باقیمانده‌ها، روزها یا بازه‌ها می‌توانند دسته بسازند. دسته‌های هم‌پوشان یا ناقص نتیجه را نامعتبر می‌کنند.

کارت لانهٔ کبوتری

اشیا ← معیار دسته‌بندی ← لانه‌های ناپوشا ← تعدادها ← حد هر لانه ← ظرفیت بدون نقض ← شیء اضافه ← تضمین

نسخهٔ ساده را با یک شیء اضافه ببین

اگر تعداد اشیا از تعداد لانه‌ها بیشتر باشد، دست‌کم یک لانه بیش از یک شیء دارد. این نتیجه نمی‌گوید کدام لانه است.

حداقل تضمینی را با سقف نسبت بساز

تقسیم تعداد اشیا بر تعداد لانه‌ها میانگین می‌دهد و گردکردن رو به بالا حدی را می‌سازد که دست‌کم یک لانه باید به آن برسد.

برای تضمین r عضو، ظرفیتِ بدون نقض را پیدا کن

فرض کن هر لانه حداکثر r−1 عضو دارد. مجموع این ظرفیت بیشترین تعداد ممکن بدون رسیدن هیچ لانه به r است؛ شیء بعدی تضمین را می‌سازد.

«دست‌کم» را در نتیجه حفظ کن

اصل مقدار دقیق پرجمعیت‌ترین دسته را تعیین نمی‌کند. نتیجه را با واژهٔ دست‌کم و نوع عضو یا دسته کامل بنویس.

مثال مرزی برای تیزبودن حد بساز

اشیا را تا جای ممکن یکنواخت پخش کن. اگر بتوانی با یک شیء کمتر از نتیجه فرار کنی، آستانهٔ تضمین را بهتر می‌فهمی.

دسته‌بندی با باقیمانده را دقیق تعریف کن

برای تقسیم بر یک عدد ثابت، باقیمانده‌های ممکن لانه‌ها هستند. تعداد باقیمانده‌ها و بازهٔ آن‌ها را کامل بنویس.

وجود را با ساختن نمونه یکی ندان

اصل می‌تواند وجود یک جفت یا دسته را تضمین کند بدون آن‌که مصداق مشخص را پیدا کند. اگر سؤال مصداق می‌خواهد، مرحلهٔ جست‌وجو را جدا انجام بده.

پاسخ را با تناقض کوتاه کامل کن

فرض کن هیچ لانه‌ای به حد مورد نظر نمی‌رسد، ظرفیت کل را حساب و ناسازگاری با تعداد اشیا را نشان بده. برای پایه به شمارش حالت‌ها برو.