پارت ۱۲ اصل متمم

سلام مجدد! 👋

پارت قبل با یه ایده‌ی جدید آشنا شدیم:

اصل متمم

ایده‌ش خیلی ساده‌ست:

گاهی شمردن چیزی که می‌خوایم، سخته.

اما شمردن همه‌ی حالت‌ها و بعد کم کردن حالت‌هایی که نمی‌خوایم، خیلی راحت‌تره.

بیا اول با یه مثال ساده ببینیم دقیقاً یعنی چی.

یه سوال ساده

فرض کن با حروف زیر می‌خوایم کلمه‌های ۳ حرفی بسازیم:

A  B  C  D  E

تکرار حروف هم آزاده.

حالا چند کلمه می‌تونیم بسازیم که حداقل یک بار حرف A داخلشون باشه؟

یعنی مثلاً:

ABC ✅

DAA ✅

EBA ✅

ولی:

BCD ❌

مستقیم بشماریم؟

می‌تونیم شروع کنیم به بررسی حالت‌هایی که A دارن…

ولی یه راه ساده‌تر داریم.

اول همه‌ی کلمه‌ها رو بشماریم.

برای هر جایگاه ۵ انتخاب داریم:

_  _  _

پس:

۵ × ۵ × ۵ = ۱۲۵

در مجموع ۱۲۵ کلمه داریم.

حالا به جای شمردن کلمه‌هایی که A دارن، بیایم ببینیم چند کلمه اصلاً A ندارن.

برای هر جایگاه دیگه A قابل استفاده نیست.

پس برای هر جایگاه:

B , C , D , E

یعنی ۴ انتخاب.

بنابراین:

۴ × ۴ × ۴ = ۶۴

پس ۶۴ کلمه اصلاً A ندارن.

حالا چی می‌مونه؟

همه‌ی حالت‌ها:

۱۲۵

منهای حالت‌هایی که نمی‌خواستیم:

۶۴

پس:

۱۲۵ - ۶۴ = ۶۱

بنابراین:

۶۱ کلمه حداقل یک A دارن. 🎉

دیدی چه اتفاقی افتاد؟

ما اصلاً حالت‌های دارای A رو مستقیماً نشمردیم.

اول چیز ساده‌تر رو شمردیم:

همه‌ی حالت‌ها

بعد چیزی که نمی‌خواستیم رو حذف کردیم:

حالت‌های بدون A

حالا برگردیم به سوال خودمون

۵ نفر داریم:

علی — رضا — سارا — مریم — نیما

و می‌خوایم بدونیم:

چند صف مختلف داریم که علی و رضا کنار هم نباشن؟

این بار مستقیم سراغ حالت‌های «کنار هم نبودن» نمی‌ریم.

اول همه‌ی صف‌ها رو می‌شماریم.

۵ نفر داریم:

۵!

یعنی:

۵ × ۴ × ۳ × ۲ × ۱ = ۱۲۰

پس در مجموع:

۱۲۰ صف مختلف

داریم.

حالا حالت‌هایی که نمی‌خوایم رو یادته؟

علی و رضا کنار هم باشن.

پارت قبل حساب کردیم که این حالت‌ها:

۴! × ۲

بودن.

یعنی:

۲۴ × ۲ = ۴۸

پس ۴۸ صف داریم که علی و رضا کنار هم هستن.

حالا از همه‌ی صف‌ها کمشون می‌کنیم:

۱۲۰ - ۴۸ = ۷۲

پس:

۷۲ صف داریم که علی و رضا کنار هم نیستن. 🎉

و این دقیقاً ایده‌ی اصل متممه:

چیزی که می‌خوایم = همه‌ی حالت‌ها − حالت‌هایی که نمی‌خوایم

گاهی مستقیم شمردن سخت میشه؛

اما اگر متممش رو بشماریم، مسئله خیلی ساده‌تر میشه.