جلسهی 10: اصل لانهی کبوتری The Pigeonhole Principle
اگر کبوترها از لانهها بیشتر باشند، یک لانه دستکم دو کبوتر دارد. نسخهی قویترش، ساختن لانههای زیرکانه (جفتها)، و رنگآمیزیِ یکدرمیان برای «حتماً میشود».
در این جلسه یاد میگیری
- اصل لانهی کبوتری و نسخهی قویترش (دستکم ⌈n ÷ k⌉ در یک لانه) را به کار میبری.
- برای یک سؤال، لانههای مناسب میسازی (مثلاً جفتهایی که جمعشان ۱۱ است).
- با تقسیم به دو دسته نشان میدهی «دستکم نصف» همیشه به دست میآید.
درس
این بار ۷ کبوتر و ۳ لانه داریم. سعی کن کبوترها را طوری بنشانی که هیچ لانهای ۳ کبوتر نداشته باشد. نمیشود! چرا؟ اگر هر لانه حداکثر ۲ کبوتر داشت، روی هم حداکثر ۶ کبوتر جا میشد.
اصل لانهی کبوتری، نسخهی قوی: اگر n کبوتر در k لانه باشند، یک لانه دستکم ⌈n ÷ k⌉ کبوتر دارد (⌈ ⌉ یعنی رو به بالا گرد کن). ۷ کبوتر در ۳ لانه: ⌈۷ ÷ ۳⌉ = ۳. ۳۷ نفر و ۱۲ ماه: ⌈۳۷ ÷ ۱۲⌉ = ۴ نفر همماه.
استدلالش همیشه همین است: «اگر هر لانه کمتر داشت، جمعشان به n نمیرسید.»
هنرِ این اصل، ساختن لانههاست. سؤال: از عددهای ۱ تا ۱۰ چند عدد برداریم تا مطمئن باشیم دو تا از آنها جمعشان ۱۱ است؟ لانهها را جفتهایی بگیر که جمعشان ۱۱ است: {۱،۱۰}، {۲،۹}، {۳،۸}، {۴،۷}، {۵،۶}. پنج لانه. با ۶ عدد، دو عدد در یک لانهاند و جمعشان ۱۱ است. با ۵ عدد مطمئن نیستی (مثلاً ۱ تا ۵). پس جواب ۶.
یک ترفند مهم: «دستکم نصف». فرض کن ۸ عدد در یک جدول ۲ × ۴ داری و میخواهی خانههایی برداری که هیچ دو تایشان ضلع مشترک نداشته باشند و جمعشان زیاد باشد. جدول را شطرنجی رنگ کن: خانههای همرنگ هیچوقت ضلع مشترک ندارند! جمع همه را دو دسته کردهای (تیرهها و روشنها)، پس یکی از دو دسته دستکم نصفِ جمع را دارد. این همان لانهی کبوتری است با ۲ لانه.
اشتباه رایج: فکر کنی اصل لانهی کبوتری میگوید «کدام» لانه شلوغ است. نمیگوید! فقط میگوید «یکی هست». و همیشه بدترین حالت را امتحان کن تا ببینی عددت دقیقاً کافی است و یکی کمتر کافی نیست (مثل ۵ عدد ۱ تا ۵ در کارت ۳).
چالشها
- Thirty-Seven Birthdays (آسان)
- Gloves in the Dark (آسان)
- Pairs That Make Eleven (متوسط)
- A Difference of Six (متوسط)
- The Seed Garden (سخت)
- Nine Chairs (سخت)
← جلسهی 9: آزمونک شمارش جلسهی 11: ناوردایی: چیزی که عوض نمیشود →