تقسیمبندی حالتها: شکستن مسئله به چند حالت جداگانه
۱. مبانی تقسیمبندی حالتها: اصل جمع و شرط عدم تداخل
در ریاضیات، وقتی با یک مسئلهٔ شمارش روبهرو میشویم که شرایط مختلفی دارد، بهترین کار این است که آن را به چند حالت کوچکتر بشکنیم. این کار بر پایهٔ «اصل جمع» انجام میشود. اصل جمع میگوید اگر یک کار را بتوان به دو روش متفاوت و غیرهمپوشان انجام داد، تعداد کل راههای انجام آن کار برابر است با مجموع راههای هر روش. شرط مهم این است که این حالتها نباید با هم اشتراک داشته باشند (متقابل باشند) و همچنین همهٔ راههای ممکن را پوشش دهند.
برای مثال، فرض کنید میخواهید یک تاس قرمز و یک تاس آبی را پرتاب کنید و تعداد حالتهایی که مجموع نقاط بالا آمده فرد میشود را بشمارید. میتوانید مسئله را به دو حالت تقسیم کنید: ۱) تاس قرمز فرد باشد، تاس آبی زوج باشد. ۲) تاس قرمز زوج باشد، تاس آبی فرد باشد. در هر حالت تعداد 3 عدد فرد (۱، ۳، ۵) و 3 عدد زوج (۲، ۴، ۶) داریم. پس تعداد حالتها برابر است با (۳×۳) + (۳×۳) = ۹ + ۹ = ۱۸. میبینید که با تقسیم به دو حالت ساده، مسئله به راحتی حل شد.
۲. حالتهای متقابل و پوشش کامل: دو قانون طلایی
برای اینکه تقسیمبندی حالتها درست و دقیق باشد، باید دو ویژگی مهم را رعایت کنیم:
- قانون ۱: حالتها متقابل باشند یعنی هیچ دو حالتی نباید با هم اشتراک داشته باشند. یک راه حل خاص نباید در دو حالت مختلف شمرده شود. این کار از شمارش دوباره جلوگیری میکند.
- قانون ۲: پوشش کامل یعنی همهٔ راهحلهای ممکن باید حداقل در یکی از حالتها قرار بگیرند. هیچ راه حلی نباید از قلم بیفتد.
به عنوان مثال، میخواهیم تعداد اعداد دو رقمی را که حداقل یک بار رقم 7 در آنها دیده میشود، بشماریم. میتوانیم مسئله را به سه حالت تقسیم کنیم:
- حالت اول: رقم دهگان 7 باشد (اعداد 70 تا 79).
- حالت دوم: رقم یکان 7 باشد و دهگان 7 نباشد (اعدادی مثل 17, 27, ..., 97 به جز 77).
- حالت سوم: هر دو رقم 7 باشند (فقط 77).
اگر دقت کنید، این سه حالت هیچ اشتراکی ندارند (شرط اول) و هر عدد دو رقمی که شامل 7 باشد، در یکی از این سه گروه قرار میگیرد (شرط دوم). تعداد کل: 10 + 8 + 1 = 19 عدد.
۳. کاربرد عملی: چیدمان و جایگشت با محدودیت
یکی از رایجترین کاربردهای تقسیمبندی حالتها در مسائل جایگشت[4] با شرایط خاص است. فرض کنید میخواهیم 5 کتاب ریاضی، 3 کتاب فیزیک و 2 کتاب شیمی را در یک قفسه بچینیم به طوری که کتابهای یک درس کنار هم باشند. برای حل، ابتدا هر درس را یک «بلوک» در نظر میگیریم. 3 بلوک داریم که به 3! حالت قابل چیدن هستند. در داخل بلوک ریاضی، کتابها به 5! حالت، داخل بلوک فیزیک به 3! حالت و داخل بلوک شیمی به 2! حالت جابجا میشوند. طبق اصل ضرب، جواب $3! \times 5! \times 3! \times 2!$ است.
اما اگر شرط بگوید که کتابهای فیزیک حتماً باید کنار هم باشند ولی کتابهای ریاضی و شیمی هیچ محدودیتی ندارند، چه میکنیم؟ اینجا باید حالتها را تقسیمبندی کنیم. ابتدا بلوک فیزیک را یک شیء در نظر میگیریم. حالا 1 بلوک فیزیک، 5 کتاب ریاضی و 2 کتاب شیمی داریم، یعنی مجموعاً 1 + 5 + 2 = 8 شیء که به 8! حالت چیده میشوند. سپس داخل بلوک فیزیک، کتابها به 3! حالت جابجا میشوند. جواب نهایی: $8! \times 3!$. در این مسئله، فقط یک حالت (همان بلوک فیزیک) را جدا کردیم.
۴. مثال عینی: شمارش اعداد طبیعی با شرایط خاص
مسئله: تعداد اعداد طبیعی سه رقمی که بر 3 بخشپذیرند و حداقل یک رقم تکراری دارند را بیابید.
حل این مسئله به طور مستقیم سخت است، اما با تقسیمبندی حالتها آسان میشود. ابتدا کل اعداد سه رقمی بخشپذیر بر 3 را حساب میکنیم. کوچکترین عدد 102 و بزرگترین 999 است. تعداد کل: $\lfloor \frac{999}{3} \rfloor - \lfloor \frac{99}{3} \rfloor = 333 - 33 = 300$. (چون اعداد دو رقمی و کوچکتر حذف میشوند.)
حال این 300 عدد را به دو حالت تقسیم میکنیم:
- حالت الف: اعداد با ارقام غیرتکراری (همه ارقام متمایز).
- حالت ب: اعداد با حداقل یک رقم تکراری (مطلوب مسئله).
اگر تعداد حالت الف را پیدا کنیم، با کم کردن آن از کل، جواب حالت ب به دست میآید. برای شمارش اعداد سه رقمی بخشپذیر بر 3 با ارقام متمایز، باید حالتهای بیشتری را در نظر گرفت (مثلاً بر اساس رقم صدگان و...). اما همین جا قدرت روش تقسیمبندی را میبینیم: ما مسئله را به دو بخش بزرگ تقسیم کردیم و کار را سادهتر نمودیم.
| روش تقسیمبندی | مثال ساده | نوع حالتها |
|---|---|---|
| بر اساس یک ویژگی (مثلاً زوج یا فرد) | مجموع تاسها فرد باشد | دو حالت مجزا |
| بر اساس مکان (مثلاً دهگان یا یکان) | اعداد شامل رقم ۷ | سه حالت با دقت در اشتراک |
| تفاضل از کل (متمم) | اعداد با حداقل یک رقم تکراری | دو حالت مکمل |
۵. چالشهای مفهومی
❓ چالش ۱: چرا در تقسیمبندی حالتها حتماً باید حالتها «متقابل» باشند؟ اگر متقابل نباشند چه اتفاقی میافتد؟
پاسخ اگر حالتها متقابل نباشند، برخی از راهحلها در بیش از یک حالت شمرده میشوند و در نتیجه هنگام جمع، تعداد واقعی بیشتر از مقدار درست محاسبه میگردد (شمارش مضاعف). برای جلوگیری از این خطا، باید اشتراک حالتها را خالی کنیم.
❓ چالش ۲: چگونه بفهمیم که یک مسئله را باید با تقسیمبندی حالت حل کنیم یا با اصل ضرب؟
پاسخ اگر مسئله چندین شرط «یا» داشته باشد (یعنی راهحلها به چند دستهٔ متفاوت تقسیم شوند)، معمولاً از تقسیمبندی حالت (اصل جمع) استفاده میکنیم. اگر شرایط به صورت زنجیرهای و «و» دار باشند (انتخابهای پشت سر هم)، از اصل ضرب استفاده میکنیم. بسیاری از مسائل پیچیده ترکیبی از این دو هستند.
❓ چالش ۳: آیا میتوان یک مسئله را به چند روش مختلف تقسیمبندی کرد؟ کدام روش بهتر است؟
پاسخ بله، بسیاری از مسائل چندین روش تقسیمبندی دارند. روشی بهتر است که اولاً سادهتر باشد (تعداد حالتها کمتر یا شمارش درون هر حالت آسانتر باشد) و ثانیاً احتمال خطا (مانند شمارش دوباره یا جاماندن برخی حالتها) را کاهش دهد. انتخاب روش مناسب با تمرین و تجربه به دست میآید.
پاورقیها
[1] اصل جمع (Addition Principle): اگر راههای انجام یک کار به چند دستهٔ جدا از هم تقسیم شوند، تعداد کل راهها برابر مجموع راههای هر دسته است.
[2] متقابل (Mutually Exclusive): دو حالت که هیچ عضو مشترکی ندارند و وقوع همزمان آنها غیرممکن است.
[3] پوشش کامل (Complete Coverage): مجموعهای از حالتها که همهٔ اعضای فضای نمونه را در بر میگیرند.
[4] جایگشت (Permutation): ترتیب قرار گرفتن اشیا در کنار یکدیگر.
