متمم در شمارش: روش حل با حالات نامطلوب
یادگیری روش مکمل یا متمم؛ از کل حالات ممکن، حالات نامطلوب را حذف کن تا پاسخ دقیق و سریع بگیری.
در شمارش ترکیبیاتی[۱]، گاهی مستقیماً شمردن حالتهای مطلوب دشوار است. روش متمم (تکمیل) پیشنهاد میکند ابتدا کل حالات ممکن را بدون قید و شرط بشماریم، سپس حالات نامطلوب (آنهایی که شرط مسئله را نقض میکنند) را محاسبه کرده و از کل کم کنیم. این تکنیک در مسائل احتمال، رمزگذاری، چیدمان صندلی و انتخاب اعضای گروه کاربرد گستردهای دارد و سرعت حل را بهشدت افزایش میدهد.
۱. تعریف و منطق روش متمم
فرض کنید مجموعهای از تمام حالتهای ممکن یک آزمایش (فضای نمونه) بهنام S داریم. میخواهیم تعداد حالتهای یک پیشامد A را پیدا کنیم. گاهی اوقات شمردن مستقیم اعضای A پیچیده است، اما شمردن اعضای متمم آن (A' یا Ac) آسانتر است. در این صورت:
$n(A) = n(S) - n(A')$
این همان اصل متمم در شمارش است. بهعنوان یک قانون کلی، هرگاه در صورت سؤال کلماتی مانند «حداقل»، «حداکثر»، «بهجز»، «هیچکدام» یا «نباشد» ظاهر شود، روش متمم اولین گزینهای است که باید به ذهن خطور کند.
$n(A) = n(S) - n(A')$
این همان اصل متمم در شمارش است. بهعنوان یک قانون کلی، هرگاه در صورت سؤال کلماتی مانند «حداقل»، «حداکثر»، «بهجز»، «هیچکدام» یا «نباشد» ظاهر شود، روش متمم اولین گزینهای است که باید به ذهن خطور کند.
۲. کاربرد عملی: رمز عبور و چیدمان
مثال ۱ (رمز عبور): فرض کنید میخواهیم تعداد رمزهای ۴ رقمی (از 0000 تا 9999) را که حداقل یک رقم 7 دارند، حساب کنیم.
- کل حالات ممکن: برای هر یک از ۴ خانه، ۱۰ انتخاب داریم: $10^4 = 10000$
- حالات نامطلوب: رمزهایی که هیچکدام از ارقامشان 7 نباشد: برای هر خانه ۹ انتخاب (0-6,8,9) داریم: $9^4 = 6561$
- حالات مطلوب:$10000 - 6561 = 3439$
مثال ۲ (چیدمان کنار هم): چند روش میتوان ۵ کتاب متفاوت را در یک قفسه چیدمان کرد بهطوری که دو کتاب خاص (مثلاً ریاضی و فیزیک) کنار هم نباشند؟
- کل حالات: جایگشت ۵ کتاب: $5! = 120$
- حالات نامطلوب: حالتی که دو کتاب خاص کنار هم هستند. این دو کتاب را یک «بسته» در نظر میگیریم. با احتساب ترتیب داخلی آنها (2!) و جایگشت ۴ شی (بسته + ۳ کتاب دیگر): $2! \times 4! = 2 \times 24 = 48$
- حالات مطلوب:$120 - 48 = 72$
۳. کاربرد در انتخاب گروه (ترکیب)
در مسائل انتخاب اعضای گروه که ترتیب مهم نیست، روش متمم با استفاده از ترکیبات[۲] بسیار کارآمد است.
مثال ۳: از بین ۱۰ دانشآموز، میخواهیم یک گروه ۴ نفره تشکیل دهیم. بهشرطی که دو دانشآموز خاص (علی و زهرا) هر دو با هم در گروه نباشند.
مثال ۳: از بین ۱۰ دانشآموز، میخواهیم یک گروه ۴ نفره تشکیل دهیم. بهشرطی که دو دانشآموز خاص (علی و زهرا) هر دو با هم در گروه نباشند.
- کل حالات: تعداد انتخاب ۴ نفر از ۱۰ نفر: $C(10,4) = \binom{10}{4} = 210$
- حالات نامطلوب: گروههایی که هم علی و هم زهرا در آنها هستند. اگر این دو نفر حتماً باشند، باید ۲ نفر دیگر را از بین ۸ نفر باقیمانده انتخاب کنیم: $C(8,2) = \binom{8}{2} = 28$
- حالات مطلوب:$210 - 28 = 182$
۴. کاربرد در احتمال: پرتاب تاس و سکه
در نظریه احتمال نیز روش متمم یکی از قویترین ابزارهاست، بهویژه وقتی با عبارت «حداقل یک بار» مواجه میشویم.
مثال ۴: یک تاس سالم را ۳ بار میاندازیم. احتمال اینکه حداقل یک بار عدد ۶ بیاید چقدر است؟
مثال ۴: یک تاس سالم را ۳ بار میاندازیم. احتمال اینکه حداقل یک بار عدد ۶ بیاید چقدر است؟
- کل حالات ممکن:$6^3 = 216$ (چون هر پرتاب ۶ حالت دارد).
- حالات نامطلوب: هیچکدام از پرتابها ۶ نباشند (یعنی هر پرتاب یکی از اعداد ۱ تا ۵ باشد): $5^3 = 125$
- احتمال مطلوب:$\frac{216 - 125}{216} = \frac{91}{216} \approx 0.42$
| نوع مسئله | کل حالات (S) | حالت نامطلوب (A') | نتیجه مطلوب (A) |
|---|---|---|---|
| رمز ۴ رقمی شامل رقم ۷ | 104=10000 | 94=6561 | 3439 |
| چیدمان ۵ کتاب (دو کتاب کنار هم نباشند) | 5! = 120 | 2!×4! = 48 | 72 |
| انتخاب گروه ۴ از ۱۰ (دو نفر با هم نباشند) | C(10,4)=210 | C(8,2)=28 | 182 |
| ۳ بار تاس (حداقل یک ۶) | 63=216 | 53=125 | 91 |
۵. چالشهای مفهومی
❓ چالش ۱: آیا روش متمم همیشه جواب میدهد؟
پاسخ: خیر، این روش وقتی کارآمد است که شمردن «حالات نامطلوب» سادهتر از شمردن مستقیم «حالات مطلوب» باشد. اگر حالات نامطلوب خود به چند دستهی پیچیدهتر تقسیم شوند، ممکن است روش متمم کمکی نکند. برای مثال، در مسائلی که شرط «حداقل دو تا از ویژگیها» مطرح است، گاهی محاسبهی متمم (حالات فاقد آن ویژگیها) میتواند با اصل شمول و عدم شمول[۳] پیچیده شود.
پاسخ: خیر، این روش وقتی کارآمد است که شمردن «حالات نامطلوب» سادهتر از شمردن مستقیم «حالات مطلوب» باشد. اگر حالات نامطلوب خود به چند دستهی پیچیدهتر تقسیم شوند، ممکن است روش متمم کمکی نکند. برای مثال، در مسائلی که شرط «حداقل دو تا از ویژگیها» مطرح است، گاهی محاسبهی متمم (حالات فاقد آن ویژگیها) میتواند با اصل شمول و عدم شمول[۳] پیچیده شود.
❓ چالش ۲: تفاوت متمم در شمارش با متمم در احتمال چیست؟
پاسخ: در هر دو، اصل یکسان است. در شمارش، تعداد حالتها را از هم کم میکنیم (n(A) = n(S) - n(A')). در احتمال، اگر فضای نمونه همشانس باشد، احتمال متمم بهصورت $P(A) = 1 - P(A')$ نوشته میشود. هر دو از یک منطق پیروی میکنند.
پاسخ: در هر دو، اصل یکسان است. در شمارش، تعداد حالتها را از هم کم میکنیم (n(A) = n(S) - n(A')). در احتمال، اگر فضای نمونه همشانس باشد، احتمال متمم بهصورت $P(A) = 1 - P(A')$ نوشته میشود. هر دو از یک منطق پیروی میکنند.
❓ چالش ۳: چرا در برخی مسائل «حداقل یک» مستقیماً به سراغ متمم میرویم؟
پاسخ: چون متمم «حداقل یک»، حالت «هیچکدام» است که معمولاً شمردنش بسیار سادهتر است. برای مثال، در پرتاب یک سکه ۱۰ بار، «حداقل یک شیر» متمم اش «هیچ شیری (همه خط)» است که فقط 1 حالت دارد. اگر بخواهیم مستقیم حالات ۱ شیر، ۲ شیر، ... را بشماریم، کار بسیار دشوار میشود.
پاسخ: چون متمم «حداقل یک»، حالت «هیچکدام» است که معمولاً شمردنش بسیار سادهتر است. برای مثال، در پرتاب یک سکه ۱۰ بار، «حداقل یک شیر» متمم اش «هیچ شیری (همه خط)» است که فقط 1 حالت دارد. اگر بخواهیم مستقیم حالات ۱ شیر، ۲ شیر، ... را بشماریم، کار بسیار دشوار میشود.
? در یک نگاه: روش متمم یک میانبر هوشمندانه در ترکیبیات است. با تبدیل مسئله از حالت «مطلوب» به «نامطلوب»، مسیر حل را هموارتر میکند. کلید موفقیت در این روش، تشخیص موقعیتی است که حالات نقضکننده (نامطلوب) ساختاری ساده و یکپارچه دارند. این روش در مسائل رمزگذاری، چیدمان، انتخاب گروه و محاسبات احتمال، یک ابزار ضروری برای هر دانشآموز دبیرستانی محسوب میشود.
پاورقی
1ترکیبیات (Combinatorics): شاخهای از ریاضیات که به مطالعه روشهای شمارش، ترکیب و چیدمان اعضای مجموعههای گسسته میپردازد.
2ترکیب (Combination): انتخابی از چند شیء بدون در نظر گرفتن ترتیب آنها. نماد C(n,r) یا \(\binom{n}{r}\).
3اصل شمول و عدم شمول (Inclusion-Exclusion Principle): روشی برای شمارش اعضای اجتماع چند مجموعه که با احتساب اشتراکها، از شمارش مضاعف جلوگیری میکند.
2ترکیب (Combination): انتخابی از چند شیء بدون در نظر گرفتن ترتیب آنها. نماد C(n,r) یا \(\binom{n}{r}\).
3اصل شمول و عدم شمول (Inclusion-Exclusion Principle): روشی برای شمارش اعضای اجتماع چند مجموعه که با احتساب اشتراکها، از شمارش مضاعف جلوگیری میکند.
