ریاضیات گسسته، فصل ۳، درس ۲

لانهٔ کبوتری: ساختن لانه از عددها و مجموعه‌ها

نهایی: در ۳ امتحان از ۲۶، روی‌هم ۳/۲۵ نمرهکنکور: ۵ سؤال

ایده

لانه‌ها را اول بساز: دسته‌هایی که هر کدام فقط تعداد معینی انتخاب را بدون ویژگی می‌پذیرد، مثل جفت‌هایی با مجموع داده‌شده، متمم‌ها، زوج و فرد، هم‌باقی‌مانده‌ها یا کوچک‌ترین مقسوم‌علیه اول (ظرفیت )، یا سه‌تایی‌های متوالی (ظرفیت ). اگر انتخاب‌ها از مجموع ظرفیت‌ها بیشتر باشند، ویژگی حتماً پیش می‌آید. پس «حداقل چند انتخاب» برابر است با بیشترین انتخابِ بدون ویژگی به‌علاوهٔ یک، و باید با یک مثال نشان دهی که کمتر کافی نیست.

نمونهٔ نهایی

نهایی شهریور ۱۴۰۳، سؤال ۱۶۱/۲۵ نمره

ثابت کنید در بین هر سه عدد طبیعی حداقل دو عدد طبیعی وجود دارد که مجموعشان عددی زوج است.

  1. عددهای طبیعی را به دو گروه زوج و فرد افراز کن؛ مجموعِ دو عددِ هم‌گروه زوج است.۰/۲۵ نمره

  2. این دو گروه را لانه بگیر.۰/۲۵ نمره

  3. سه عدد داده‌شده را کبوتر بگیر.۰/۲۵ نمره

  4. کبوترها از لانه‌ها بیشترند، پس اصل لانهٔ کبوتری را به کار ببر.۰/۲۵ نمره

  5. لانه‌ای دو عدد دارد: هر دو زوج یا هر دو فرد؛ مجموعشان در هر دو حالت زوج است.۰/۲۵ نمره

همهٔ سؤال‌های این تیپ