بتل کد Battle Codeدارد باز می‌شود…

جلسه‌ی 10: اصل لانه‌ی کبوتری The Pigeonhole Principle

اگر کبوترها از لانه‌ها بیشتر باشند، یک لانه دست‌کم دو کبوتر دارد. نسخه‌ی قوی‌ترش، ساختن لانه‌های زیرکانه (جفت‌ها)، و رنگ‌آمیزیِ یک‌در‌میان برای «حتماً می‌شود».

در این جلسه یاد می‌گیری

درس

این بار ۷ کبوتر و ۳ لانه داریم. سعی کن کبوترها را طوری بنشانی که هیچ لانه‌ای ۳ کبوتر نداشته باشد. نمی‌شود! چرا؟ اگر هر لانه حداکثر ۲ کبوتر داشت، روی هم حداکثر ۶ کبوتر جا می‌شد.

اصل لانه‌ی کبوتری، نسخه‌ی قوی: اگر n کبوتر در k لانه باشند، یک لانه دست‌کم ⌈⁦n ÷ k⁩⌉ کبوتر دارد (⌈ ⌉ یعنی رو به بالا گرد کن). ۷ کبوتر در ۳ لانه: ⌈⁦۷ ÷ ۳⁩⌉ = ۳. ۳۷ نفر و ۱۲ ماه: ⌈⁦۳۷ ÷ ۱۲⁩⌉ = ۴ نفر هم‌ماه.
استدلالش همیشه همین است: «اگر هر لانه کمتر داشت، جمعشان به n نمی‌رسید.»

هنرِ این اصل، ساختن لانه‌هاست. سؤال: از عددهای ۱ تا ۱۰ چند عدد برداریم تا مطمئن باشیم دو تا از آن‌ها جمعشان ۱۱ است؟ لانه‌ها را جفت‌هایی بگیر که جمعشان ۱۱ است: {۱،۱۰}، {۲،۹}، {۳،۸}، {۴،۷}، {۵،۶}. پنج لانه. با ۶ عدد، دو عدد در یک لانه‌اند و جمعشان ۱۱ است. با ۵ عدد مطمئن نیستی (مثلاً ۱ تا ۵). پس جواب ۶.

یک ترفند مهم: «دست‌کم نصف». فرض کن ۸ عدد در یک جدول ⁦۲ × ۴⁩ داری و می‌خواهی خانه‌هایی برداری که هیچ دو تایشان ضلع مشترک نداشته باشند و جمعشان زیاد باشد. جدول را شطرنجی رنگ کن: خانه‌های هم‌رنگ هیچ‌وقت ضلع مشترک ندارند! جمع همه را دو دسته کرده‌ای (تیره‌ها و روشن‌ها)، پس یکی از دو دسته دست‌کم نصفِ جمع را دارد. این همان لانه‌ی کبوتری است با ۲ لانه.

اشتباه رایج: فکر کنی اصل لانه‌ی کبوتری می‌گوید «کدام» لانه شلوغ است. نمی‌گوید! فقط می‌گوید «یکی هست». و همیشه بدترین حالت را امتحان کن تا ببینی عددت دقیقاً کافی است و یکی کمتر کافی نیست (مثل ۵ عدد ۱ تا ۵ در کارت ۳).

چالش‌ها

  1. Thirty-Seven Birthdays (آسان)
  2. Gloves in the Dark (آسان)
  3. Pairs That Make Eleven (متوسط)
  4. A Difference of Six (متوسط)
  5. The Seed Garden (سخت)
  6. Nine Chairs (سخت)

← جلسه‌ی 9: آزمونک شمارش جلسه‌ی 11: ناوردایی: چیزی که عوض نمی‌شود →