منو
 کاربر Online
765 کاربر online

اصل شمول و طرد

تازه کردن چاپ
علوم ریاضی > علو م رایانه
(cached)



این مطلب از بخش آموزش وب‌سایت المپیاد کامپیوتر رشد،انتخاب شده که با فرمت pdf نیز در وب‌سایت المپیاد رشدموجود می‌باشد. برای مشاهده این موضوعات در وب‌سایت المپیاد، به آدرس فهرست مطالب کامپیوتر مراجعه کنید. همچنین می‌توانید با کلیک اینجا‌ ، با ویژگی‌های بخش آموزش این وب‌سایت آشنا شوید.


اصل شمول و عدم شمول

مقدمه

همان طور که در قبل دیدیم، در حل مسایلی شمارشی، مجموعه اشیایی را که باید شمرده شوند، می توان به چند زیرمجموعه قابل شمارش جدا از هم تقسیم کرد و با استفاده از اصل جمع، جواب مساله را به دست آورد. اما تقسیم یک مجموعه به چند زیرمجموعه قابل شمارش جدا از هم، همیشه کار ساده ای نیست. در این فصل با اصل شمول و عدم شمول آشنا می شویم؛ سپس یاد می گیریم چگونه این مشکل را حل کنیم.
اگر و دو مجموعه متناهی جدا از هم باشند، . حال اگر و جدا از هم نباشند، را چگونه حساب کنیم؟
img/daneshnameh_up/2/2d/com0019a.jpg

اگر و دو مجموعه متناهی باشند داریم:


مثال

در یک کلاس 30 نفری، 21 نفر به زبان انگلیسی، 17 نفر به زبان فرانسه و 10 نفر به هر دو زبان می توانند صحبت کنند. در این کلاس چند نفر هستند که به هیچ یک از این دو زبان صحبت نمی کنند؟
حل.
فرض کنید و مجموعه ی افرادی باشند که به ترتیب به زبان انگلیسی و فرانسه صحبت می کنند. با استفاده از فرمول(1)داریم . بنابراین
2 = 28 – 30 نفر به هیچ یک از دو زبان انگلیسی و فرانسه صحبت نمی کنند.

مثال

چند عدد طبیعی مانند n وجود دارد که مقسوم علیه یا باشد؟
حل.
فرض کنید و به ترتیب مجموعه ی مقسوم علیه های و باشند. مساله را می خواهد. و، بنابراین و. همچنین می دانیم هر مقسوم علیه مشترک و، مقسوم علیه می باشد. پس . پس عدد طبیعی وجود دارد که مقسوم علیه یا می باشند.

اصل شمول و عدم شمول

در بخش قبل دیدیم چگونه تعداد اعضای اجتماع دو مجموعه را حساب می کنیم. حال اگر بخواهیم تعداد اعضای اجتماع سه مجموعه را حساب کنیم، چه کار باید بکنیم؟
فرض کنید سه مجموعه متناهی باشند.




بنابراین داریم


مثال

چند عدد طبیعی کوچک تر یا مساوی 1000 وجود دارد که بر 2، 3 یا 5 بخش پذیر است؟
قبل از این که به حل مسئله بپردازیم سه نکته را که در حل مسئله به ما کمک می کنند یادآوری می کنیم.
تعداد مضارب طبیعیکه کوچک تر یا مساوی با است برابر است با.
1.تعداد اعداد طبیعی بزرگ تر از و کوچک تر یا مساوی که بر بخش پذیرند برابر است با
.

2.عدد طبیعی بر دو عدد و بخش پذیر است اگر و فقط اگر بر ک. م. م و ، ،بخش پذیر باشد.

حل.


به ازای هر عدد طبیعی ، تعریف می کنیم:

پس در این مثال را می خواهیم حساب کنیم.







حال طبق فرمول 2 داریم:


پس جواب مسآله برابر است با 734.

مثال

در یک مدرسه 100 دانش آموز در سه امتحان فیزیک، شیمی و ریاضی شرکت کرده اند. هر نفر در هر سه امتحان شرکت کرده است. در بین آنها 92 نفر در امتحان فیزیک، 75 نفر در امتحان شیمی، 63 نفر در امتحان ریاضی قبول شده اند. حداکثر 65 نفر در هر دو امتحان فیزیک و شیمی، 54 نفر در ریاضی و فیزیک، و 48 نفر در امتحان های شیمی و ریاضی قبیول شده اند. دانش آموزانی که در هر سه درس قبول شده اند حداکثر چند نفر می توانند باشند؟
حل
. فرض کنید ، و ، به ترنیب مجموعه ی افرادی که در امتحان های فیزیک، شیمی و ریاضی قبول شده اند، باشند. مساله حداکثر مقدار را می خواهد.


بنابراین حداکثر 37 نفر در هر سه آزمون قبول شده اند.

مثال

معادله ی، چند جواب صحیح دارد به طوری که،، و؟
حل.
فرض کنید به ترتیب شرط های باشند. همچنین مجموعه ی جواب های معادله ی با شرایط باشد. مساله مقدار را می خواهد.
می دانیم:




همچنین امکان ندارد بیش از دو شرط با هم اتفاق بیفتند. بنابراین

قبل از حل چند مثال دیگر، چند نماد برای ساده تر بیان کردن اصل شمول و عدم شمول معرفی می کنیم. می نویسیم



و به طور کلی،

که در آن مجموع روی همه ی انتخاب های تایی از گردایه ی شرط مفروض انجام می گیرد. بنابراین حاوی جمعوند است.


پیوند های خارجی

http://Olympiad.roshd.ir/computer/content/pdf/0036.pdf

همچنین ببینید




تعداد بازدید ها: 32219


ارسال توضیح جدید
الزامی
big grin confused جالب cry eek evil فریاد اخم خبر lol عصبانی mr green خنثی سوال razz redface rolleyes غمگین smile surprised twisted چشمک arrow



از پیوند [http://www.foo.com] یا [http://www.foo.com|شرح] برای پیوندها.
برچسب های HTML در داخل توضیحات مجاز نیستند و تمام نوشته ها ی بین علامت های > و < حذف خواهند شد..