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

جلسه‌ی 8: توپ‌ها و جعبه‌ها Balls and Boxes

تقسیم چیزهای یکسان بین جعبه‌های متفاوت با «توپ و دیوار»، شرط «دست‌کم یکی در هر جعبه»، معادله‌ی ⁦x + y + z = n⁩، و فرقش با چیزهای متفاوت.

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

درس

۵ توپ یکسان را بین ۳ جعبه تقسیم کن (جعبه‌ی خالی هم مجاز است). توپ‌ها را در یک ردیف بگذار و ۲ دیوار بینشان: توپ‌های قبل از دیوار اول مال جعبه‌ی ۱، بین دو دیوار مال جعبه‌ی ۲، بعد از دیوار دوم مال جعبه‌ی ۳. دیوارها را جابه‌جا کن و ببین چند تقسیمِ متفاوت پیدا می‌کنی.

روش «توپ و دیوار»: هر تقسیم یعنی یک ردیف از ۵ توپ و ۲ دیوار، مثل ●●|●●●| (یعنی ۲، ۳، ۰). ۷ جا داریم و باید معلوم کنیم کدام ۲ جا دیوار است: ⁦C(۷, ۲) = ۲۱⁩.
قانون: n چیز یکسان بین k جعبه‌ی متفاوت = ⁦C(n + k − ۱, k − ۱)⁩.
همین یعنی تعداد جواب‌های ⁦x + y + z = ۵⁩ با عددهای حسابی (۰، ۱، ۲، …).

اگر هر جعبه دست‌کم یکی بخواهد: اول به هر جعبه یکی بده! از ۱۰ سیب و ۳ بچه که هر کدام دست‌کم یک سیب می‌خواهند: اول ۳ سیب پخش کن، ۷ سیب می‌ماند که آزادانه تقسیم می‌شود: ⁦C(۷ + ۲, ۲) = C(۹, ۲) = ۳۶⁩.
به همین روش برای «هر کدام دست‌کم ۲»: اول ۲ تا به هر کدام بده.

چیزهای متفاوت فرق دارند: اگر توپ‌ها شماره داشته باشند (متفاوت باشند)، هر توپ جداگانه جعبه‌اش را انتخاب می‌کند: ۳ توپِ متفاوت در ۲ جعبه = ⁦۲ × ۲ × ۲ = ۸⁩. ولی ۳ توپِ یکسان در ۲ جعبه فقط ۴ حالت دارد: ⁦(۳,۰)⁩، ⁦(۲,۱)⁩، ⁦(۱,۲)⁩، ⁦(۰,۳)⁩.
پس همیشه اول بپرس: چیزها یکسان‌اند یا متفاوت؟ جعبه‌ها چه؟

چالش‌ها

  1. Four Candies, Two Kids (آسان)
  2. Three Different Balls (آسان)
  3. x + y + z = 6 (متوسط)
  4. Apples for Everyone (متوسط)
  5. At Least Two Each (سخت)
  6. Multiples of Five (سخت)

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