فهرست مندرجات
اصل ضرب
ترکیبیات شمارشی، قسمتی از ترکیبیات است که در آن، با شمردن تعداد حالت‌های یک چیز سر و کار داریم. اصول اولیه‌ی شمارش، پایه‌ای‌ترین و پرکاربردترین مبحث‌ها در ترکیبیات شمارشی هستند. اصل ضرب یکی از اصول اولیه‌ی شمارش است.
یک مثال
فرض کنید به رستوران رفته‌اید و این رستوران ۳ غذای چلوکباب، جوجه کباب و قرمه‌سبزی دارد. همچنین نوشیدنی‌های آن نوشابه و دوغ هستند. شما به چند طریق می‌توانید غذای امروز خود را سفارش دهید؟
برای پاسخ به این سؤال تمام حالت‌های ممکن را می‌نویسیم:
| نوشیدنی | غذای اصلی | حالت |
| نوشابه | چلو کباب | ۱ |
| دوغ | چلو کباب | ۲ |
| نوشابه | جوجه کباب | ۳ |
| دوغ | جوجه کباب | ۴ |
| نوشابه | قرمه‌سبزی | ۵ |
| دوغ | قرمه‌سبزی | ۶ |
بنابراین ۶ حالت برای غذای ما وجود دارد. اما اگر کمی با دقت نگاه کنیم، می‌بینیم به ازای هر غذا، ۲ حالت برای نوشیدنی وجود دارد و از آن‌جایی که ۳ نوع غذا داریم، در کل $3\times2$ حالت برای تهیه‌ی غذای خود داریم.
تعریف
اصل ضرب در ریاضیات به صورت زیر تعریف می‌شود:
اگر کار ۱ به $a$ طریق قابل انجام باشد و به ازای هر حالت انجام کار ۱، کار ۲ به $b$ طریق قابل انجام باشد، تعداد روش‌های انجام این ۲ کار با هم، $a \times b$ است.
مثال:
راه‌های ارتباطی بین سه شهر سمرقند، بخارا و بلخ به صورت زیر است:
به چند روش با این راه‌های ارتباطی می‌توان از بخارا به بلخ رفت؟
پاسخ
ابتدا باید از بخارا به سمرقند برویم که ۵ حالت دارد. به ازای هر حالت از انجام این کار، ۲ حالت برای رفتن از سمرقند به بخارا داریم. پس طبق اصل ضرب، پاسخ برابر $5 \times 2 = 10$ است.
تعمیم
اصل ضرب را می‌توان برای $n$ کار نیز تعریف کرد. در واقع اگر کار ۱ به $a_1$ طریق قابل انجام باشد و به ازای هر حالت انجام کار ۱، کار ۲ به $a_2$ طریق قابل انجام باشد و به ازای هر حالت انجام کارهای ۱ و ۲، کار ۳ به $a_3$ طریق قابل انجام باشد و … و به ازای هر حالت انجام کارهای ۱ تا $n-1$، کار $n$ به $a_n$ طریق قابل انجام باشد، تعداد روش‌های انجام این $n$ کار با هم، $$\prod_{i=1}^{n}a_i=a_1\times{}a_2\times{}...{}\times{}a_n$$ است.
مثال: فرض کنید در یک مدرسه ۵ کلاس وجود دارد که هر کدام از آن‌ها، ۲۰ دانش‌آموز دارند. می‌خواهیم یک شورای دانش‌آموزی برای این مدرسه انتخاب کنیم؛ طوری که از هر کلاس ۱ نفر در این شورا باشد. این کار به چند طریق ممکن است؟
پاسخ
فهرست کردن تمام کارها در این مثال بسیار زمان‌گیر است و تعداد حالت‌ها بسیار زیاد است. بنابراین بهتر است به دنبال روشی بهتر باشیم.
انتخاب نماینده از کلاس شماره ۱، ۲۰ حالت دارد. به ازای هر حالت انتخاب نماینده از کلاس شماره ۱، ۲۰ حالت برای انتخاب نماینده از کلاس شماره ۲ وجود دارد و به همین ترتیب هر کدام از نماینده‌های کلاس‌های شماره ۳ و ۴ و ۵ نیز ۲۰ حالت دارند. بنابراین در کل $$20\times20\times20\times20\times20=20^5$$ حالت برای انجام این کار وجود دارد.
چند مثال
مثال:
راه‌های ارتباطی بین چهار شهر کرج، تهران، ورامین و سمنان، مانند شکل زیر است (جاده‌ها، دوطرفه هستند):
به چند طریق می‌توان با استفاده از این جاده‌ها، از کرج به سمنان رفت و به کرج برگشت؛ طوری که از هیچ جاده‌ای دو بار عبور نکنیم؟
پاسخ
ابتدا به ۴ حالت از کرج به تهران می‌رویم. سپس با ۲ حالت از تهران به ورامین و با ۳ حالت از ورامین به سمنان می‌رویم. در راه بازگشت، از ۳ جاده‌ی بین سمنان و ورامین، از یکی حق نداریم استفاده کنیم. پس ۲ حالت دارد. به همین ترتیب بازگشت از ورامین به تهران، ۱ حالت و بازگشت از تهران به کرج، ۳ حالت دارد. پس طبق اصل ضرب پاسخ برابر $$4 \times 2 \times 3 \times 2 \times 1 \times 3 = 144$$ است.
مثال:
- چند ۴ رقمی داریم؟
- چند عدد ۴ رقمی زوج داریم؟
- چند عدد ۴ رقمی داریم که رقم تکراری نداشته باشد؟
- چند عدد ۴ رقمی فرد داریم که رقم تکراری نداشته باشد؟
پاسخ
قسمت ۱: یک راه این است که بگوییم اعداد ۴ رقمی از ۱۰۰۰ تا ۹۹۹۹ هستند؛ پس ۹۰۰۰ تا هستند. اما با اصل ضرب هم می‌توانیم مسئله را حل کنیم.
برای هر رقم، یک جایگاه، مانند شکل زیر، در نظر می‌گیریم و تعداد حالات آن رقم را می‌نویسیم. رقم هزارگان، ۹ حالت دارد (۰ نمی‌تواند باشد) و هر کدام از ارقام یکان، دهگان و صدگان، ۱۰ حالت دارند؛ بنابراین $9\times10\times 10\times10=9000$ عدد ۳ رقمی داریم.
قسمت ۲:
باز هم برای هر رقم، یک جایگاه، مانند شکل زیر در نظر می‌گیریم و تعداد حالات آن رقم را می‌نویسیم. رقم هزارگان ۹ حالت دارد (۰ نمی‌تواند باشد). رقم دهگان ۱۰ حالت، رقم صدگان نیز، ۱۰ حالت و رقم یکان ۵ حالت دارد (باید زوج باشد). بنابراین تعداد اعداد ۴ رقمی زوج، $9\times10\times 10\times5=450$ است.
قسمت ۳:
فرض کنید یک نفر با حالت‌بندی روی رقم یکان حل مسئله را آغاز کند. این فرد با خود می‌گوید رقم یکان ۱۰ حالت دارد. رقم دهگان ۹ حالت (برابر رقم یکان نمی‌تواند باشد) و رقم صدگان ۸ حالت (برابر ارقام یکان و دهگان نمی‌تواند باشد) دارد. اما این فرد در شمردن تعداد حالت‌های رقم هزارگان به مشکل می‌خورد؛ زیرا اگر در ارقام یکان، دهگان یا صدگان رقم ۰ موجود باشد، رقم صدگان ۷ حالت و در غیر این صورت ۶ حالت دارد. پس این راه حل به مشکل می‌خورد.
برای ارائه‌ی یک راه حل خوب، از رقم صدگان شروع می‌کنیم و مسئله را حل می‌کنیم. رقم هزارگان ۹ حالت دارد (۰ نمی‌تواند باشد). رقم صدگان ۹ حالت دارد (برابر رقم هزارگان نمی‌تواند باشد) و به همین ترتیب، رقم دهگان، ۸ و رقم یکان، ۷ حالت دارد. پس طبق اصل ضرب در کل $9\times9\times8\times7$ عدد ۴ رقمی با ارقام متمایز داریم.
بنابراین بسیار مهم است حل مسئله را از کجا شروع می‌کنیم. معمولن بهتر است از جاهایی شروع کنیم که محدودیت بیش‌تری دارند. برای مثال در این مسئله شروع از رقم هزارگان منطقی است؛ زیرا علاوه بر این که باید با بقیه‌ی ارقام متفاوت باشد، این شرط را دارد که نباید ۰ باشد.
قسمت ۴:
از رقم یکان شروع می‌کنیم. این رقم باید فرد باشد؛ پس ۵ حالت دارد. حال سراغ رقم هزارگان می‌رویم. این رقم باید رقمی مخالف صفر و مخالف رقم یکان باشد؛ پس ۸ حالت دارد. رقم صدگان نیز باید مخالف ارقام یکان و هزارگان باشد؛ پس ۸ حالت دارد. به همین ترتیب رقم دهگان ۷ حالت دارد. پس طبق اصل ضرب در کل $8 \times 8 \times 7 \times 5$ عدد ۴ رقمی با خواص گفته شده داریم.
مثال:
- به چند روش می‌توان ۴ مهره‌ی رخ متفاوت را در یک جدول $4\times4$ قرار داد؛ طوری که یک‌دیگر را تهدید نکنند؟
- به چند روش می‌توان ۴ مهره‌ی رخ یکسان را در یک جدول $4\times4$ قرار داد؛ طوری که یک‌دیگر را تهدید نکنند؟
توجه: دو مهره‌ی رخ در صورتی یک‌دیگر را تهدید می‌کنند که هم‌سطر یا هم‌ستون باشند.
پاسخ
قسمت ۱: رخ‌ها را با شماره‌های ۱ تا ۴ نام‌گذاری می‌کنیم. رخ شماره ۱ برای قرار گرفتن در جدول، ۱۶ حالت دارد. با قرار گرفتن رخ شماره ۱، ۹ خانه برای قرار گرفتن دیگر رخ‌ها می‌ماند (طبق شکل زیر).
پس از قرار دادن رخ شماره ۱، رخ شماره ۲، ۹ حالت برای قرار گرفتن در جدول دارد. به همین ترتیب رخ‌های بعدی به ترتیب ۴ و ۱ حالت برای قرار گرفتن در جدول خواهند داشت. پس طبق اصل ضرب پاسخ برابر $$16\times9\times4\times1$$ است.
قسمت ۲: در این قسمت رخ‌ها با یک‌دیگر تفاوتی ندارند و نباید آن‌ها را شماره‌گذاری کنیم. در هر سطر باید دقیقن یک رخ قرار بگیرد. قرار دادن رخ در سطر اول، ۴ حالت دارد. حال یکی از خانه‌های سطر دوم مورد تهدید است و قرار دادن رخ در آن ۳ حالت دارد. به همین ترتیب قرار دادن رخ در سطرهای سوم و چهارم، به ترتیب ۲ و ۱ حالت دارد. پس پاسخ برابر $$4\times3\times2\times1=24$$ است.
مثال:
- ثابت کنید تعداد زیرمجموعه‌های یک مجموعه‌ی $n$ عضوی، $2^n$ است.
- در چند زیرمجموعه از مجموعه‌ی $\{1, 2, ..., 10\}$، عضو ۱ وجود دارد و بزرگ‌ترین عضو زیرمجموعه، ۷ است؟
- یک زیرمجموعه را فرد می‌نامیم، اگر تعداد اعضای آن فرد باشد. تعداد زیرمجموعه‌های فرد یک مجموعه‌ی $n$ عضوی را بشمارید.
راهنمایی
بر اساس آمدن یا نیامدن هر عضو در زیرمجموعه، حالت‌بندی کنید.
پاسخ
قسمت ۱:
از اصل ضرب استفاده می‌کنیم. هر عضو از مجموعه ۲ حالت دارد (یا در زیرمجموعه می‌آید یا در زیرمجموعه نمی‌آید). پس تعداد زیرمجموعه‌های یک مجموعه‌ی $n$-عضوی،
است.
قسمت ۲:
اعداد بزرگ‌تر از ۷ نباید در زیرمجموعه بیایند و اعداد ۱ و ۷ هم حتمن باید در زیرمجموعه باشند؛ پس هر کدام از این اعداد، ۱ حالت دارند. بقیه‌ی اعداد برای بودن یا نبودن در زیرمجموعه، هر کدام ۲ حالت دارند. پس پاسخ برابر
است.
قسمت ۳:
عضو اول مجموعه ۲ حالت دارد. یا در زیرمجموعه می‌آید یا در زیرمجموعه نمی‌آید. به همین ترتیب عضوهای دیگر به جز عضو آخر، هر کدام ۲ حالت دارند. حال اگر تاکنون فرد عضو آمده باشند، عضو آخر نباید بیاید و اگر زوج عضو آمده باشند، عضو آخر باید بیاید؛ بنابراین عضو آخر در هر صورت ۱ حالت دارد. پس در کل
حالت داریم.
مثال: فرض کنید تجزیه‌ی عدد طبیعی $n$ به عوامل اول، به صورت $n=p_1^{a_1}\times{}p_2^{a_2}\times{}...\times{}p_k^{a_k}$ باشد. ثابت کنید تعداد مقسوم‌علیه‌های مثبت $n$ برابر $(a_1+1)(a_2+1)...(a_k+1)$ است.
پاسخ
عامل اول $p_i$ را در نظر بگیرید. توان این عامل در یک مقسوم‌علیه مثبت از $n$، یا ۰ است، یا ۱ است، … یا $a_i$ است. بنابراین توان این عامل در یک مقسوم‌علیه مثبت از $n$، $a_i+1$ حالت دارد. پس طبق اصل ضرب، پاسخ برابر با $(a_1+1)(a_2+1)...(a_k+1)$ است.
مثال: $2n$ نفر در یک گروه داریم. به چند طریق می‌توان این افراد را به $n$ گروه دو نفره تقسیم کرد؟
پاسخ
یک نفر را در نظر می‌گیریم. هم‌تیمی این فرد، $2n-1$ حالت دارد. پس یکی از تیم‌ها مشخص شد. از $2n-2$ نفر باقی‌مانده، یک نفر را در نظر می‌گیریم. هم‌تیمی این فرد، $2n-3$ حالت دارد. پس یک تیم دیگر هم مشخص شد و به همین ترتیب ادامه‌ی کار را انجام می‌دهیم. پس طبق اصل ضرب، پاسخ برابر $(2n-1)\times(2n-3)\times...\times1$ است.
توجه کنید در این مسئله، گروه‌ها با یک‌دیگر تفاوتی نداشتند و در واقع این طور نبود که بگوییم گروه ۱، گروه ۲ و … . اگر به پاسخ دیگری رسیده‌اید، چک کنید که این مشکل را نداشته باشید که گروه‌ها را متمایز گرفته باشید. در مباحث بعدی، راه حل‌های دیگری نیز برای این مسئله خواهید دید.
مسائل نمونه از المپیادهای کامپیوتر ایران
منابع و مراجع
- Chen Chuan-Chong, Koh Khee-Meng (1992), Principles and Techniques in Combinatorics, Singapore, World Scientific
- Arthur Engel (1998), Problem Solving Strategies, New York, Springer
خواننده‌ی گرامی، لطفا در صورت داشتن پیشنهاد یا مشاهده‌ی مشکل (علمی، تایپی و …) در این صفحه، به ما اطلاع دهید:
ابزار صفحه
کلیه‌ی حقوق این سایت متعلق به کمیته‌ی ملی المپیاد کامپیوتر ایران است.
نظرات
سلام با تشکر از سایت خوبتان صورت سوال مثال اول را اشتباه نوشتید باید بنویسید: «به چند روش با این راه‌های ارتباطی می‌توان از سمرقند به بلخ رفت؟» اما شما نوشتید: «به چند روش با این راه‌های ارتباطی می‌توان از بخارا به بلخ رفت؟»
همچنین در پاسخش نیز به اشتباه نام شهر ها را نوشتید و با شکل تطابق ندارند….
awesome
سلام خسته نباشید.
مرسی بابت این مطالب
من یک اشکال تایپی در بخش اصل شمول و عدم شمول پیدا کردم
در پاسخ به یکی از مثال ها نوشتید : «23 به علاوه 12 منهای 4 برابر با 41 است.» که در اصل باید برابر با 31 باشد.
سلام و خسته نباشید خیلی خوب بود و متشکر امیدوارم روز به روز المپدیا غنی تر بشه.
در مسئله ی دوم نمونه از المپیاد کامپیوتر (که در این لینک است) عبارت «مجموع اعضای نصف آن‌ها زوج» در پاسخ سوال دوبار تکرار شده.
بازهم متشکر وظیفه ی خودم دیدم که این ایراد تایپی را به اطلاعتون برسونم :)
ممنون. تصحیح شد.