جلسهی 8: توپها و جعبهها Balls and Boxes
تقسیم چیزهای یکسان بین جعبههای متفاوت با «توپ و دیوار»، شرط «دستکم یکی در هر جعبه»، معادلهی x + y + z = n، و فرقش با چیزهای متفاوت.
در این جلسه یاد میگیری
- تقسیم n چیز یکسان بین k جعبه را با توپ و دیوار میشماری.
- شرط «هر جعبه دستکم یکی» یا «دستکم چند تا» را با «اول بده، بعد تقسیم کن» حل میکنی.
- فرق چیزهای یکسان و متفاوت را در شمردن میدانی.
درس
۵ توپ یکسان را بین ۳ جعبه تقسیم کن (جعبهی خالی هم مجاز است). توپها را در یک ردیف بگذار و ۲ دیوار بینشان: توپهای قبل از دیوار اول مال جعبهی ۱، بین دو دیوار مال جعبهی ۲، بعد از دیوار دوم مال جعبهی ۳. دیوارها را جابهجا کن و ببین چند تقسیمِ متفاوت پیدا میکنی.
روش «توپ و دیوار»: هر تقسیم یعنی یک ردیف از ۵ توپ و ۲ دیوار، مثل ●●|●●●| (یعنی ۲، ۳، ۰). ۷ جا داریم و باید معلوم کنیم کدام ۲ جا دیوار است: C(۷, ۲) = ۲۱.
قانون: n چیز یکسان بین k جعبهی متفاوت = C(n + k − ۱, k − ۱).
همین یعنی تعداد جوابهای x + y + z = ۵ با عددهای حسابی (۰، ۱، ۲، …).
اگر هر جعبه دستکم یکی بخواهد: اول به هر جعبه یکی بده! از ۱۰ سیب و ۳ بچه که هر کدام دستکم یک سیب میخواهند: اول ۳ سیب پخش کن، ۷ سیب میماند که آزادانه تقسیم میشود: C(۷ + ۲, ۲) = C(۹, ۲) = ۳۶.
به همین روش برای «هر کدام دستکم ۲»: اول ۲ تا به هر کدام بده.
چیزهای متفاوت فرق دارند: اگر توپها شماره داشته باشند (متفاوت باشند)، هر توپ جداگانه جعبهاش را انتخاب میکند: ۳ توپِ متفاوت در ۲ جعبه = ۲ × ۲ × ۲ = ۸. ولی ۳ توپِ یکسان در ۲ جعبه فقط ۴ حالت دارد: (۳,۰)، (۲,۱)، (۱,۲)، (۰,۳).
پس همیشه اول بپرس: چیزها یکساناند یا متفاوت؟ جعبهها چه؟
چالشها
- Four Candies, Two Kids (آسان)
- Three Different Balls (آسان)
- x + y + z = 6 (متوسط)
- Apples for Everyone (متوسط)
- At Least Two Each (سخت)
- Multiples of Five (سخت)