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

تناظر بین مسائل و شمارش

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



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


تناظر یک به یک و مسائل مربوط به شمارش

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

تعریف

تابع را یک تابع یک به یک می نامیم. اگر

به عبارت دیگر تابع ، به هیچ دو عضو دلخواه ، یک مقدار را نسبت ندهد.
اصل رابطه یک به یک. اگر یک رابطه یک به یک (تابع یک به یک) از مجموعه به مجموعه وجود داشته باشد، آنگاه .

تعریف

تابع را یک تناظر یک به یک می نامیم اگر یک به یک و پوشا باشد.
اصل تناظر یک به یک. اگر یک تناظر یک به یک از مجموعه به مجموعه وجود داشته باشد، آنگاه .
دقت کنید که در اصول فوق لزومی ندارد مجموعه های و متناهی باشد



مثال

با استفاده از تناظر یک به یک ثابت کنید:

حل.
ثابت می کنیم که یک تناظر یک به یک بین تعداد زیر مجموعه های عضوی مجموعه ی و تعداد زیر مجموعه ی عضوی آن وجود دارد؛ در نتیجه تساوی برقرار است.
اگر یک زیر مجموعه ی عضوی مجموعه باشد، آن گاه هم یک زیر مجموعه ی عضوی، مجموعه ی است و برعکس. به عبارت دیگر انتخاب شدن عنصر از بین عنصر مثل انتخاب نکردن عنصر از بین عنصر است. زیرا برای انتخاب عنصر از بین عنصر می توان ابتدا عنصر را انتخاب کرد و با حذف آنها عنصر را به دست آورد.

مثال( مسئله ی مسیر)

شخصی در ساختمانی کار می کند که هفت بلوک در شرق و هشت بلوک در شمال خانه اش قرار دارد. این فرد برای رسیدن به محل کارش هر روز 15 بلوک را طی می کند. این شخص به چند طریق می تواند به محل کارش برود؟
img/daneshnameh_up/b/b3/com0021a.jpg

حل.
مسئله ی مسیر را با تعداد کلمات 15 حرفی با 7 حرف و 8 حرف می توانیم متناظر کنیم. اگر هر حرف نشان گر رفتن به سمت شمال و هر حرف نشان گر رفتن به سمت شرق باشد، واضح است که به ازای هر مسیر، یک کلمه با 7 حرف و 8 حرف وجود دارد و بالعکس. به عنوان مثال مسیر متناظر با شکل بالا، به صورت می باشد. بنابراین یک تناظر یک به یک بین مسیرها و کلماتی که با 7 حرف و 8 حرف ساخته می شوند، وجود دارد. در نتیجه تعداد مسیرهای مورد نظر برابر است با.
به طور کلی اگر بخواهیم در صفحه ی مختصات از نقطه یبه نقطه ی، برویم؛ با این شرط که در هر حرکت از نقطه ی بتوانیم به یکی از نقاط، ، وبرویم، تعداد کوتاه ترین مسیرها از نقطه یبه نقطه ی برابر است با تعداد کلماتی که باتا x وتا ساخته می شوند. در نتیجه تعداد این مسیرها برابر است با.
اگر یک مجموعه باشد، مجموعه ی تمام زیر مجموعه های را مجموعه ی توانی می نامند و بانشان می دهند. به عنوان مثال اگر باشد، مجموعه ی توانی برابر است با:




مثال

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

مجموعه ی تمام مفهوم دنباله های دودویی به طول باشد. تابع یک به یک و پوشای را به این شکل تعریف می کنیم.

به طوری که به ازای هر اگر، آن گاه و در غیر این صورت. به عنوان مثال اگر وباشد؛ آن گاه.
واضح است که تابع فوق یک به یک و پوشا است. بنابراین. ولی می دانیم که، پس تعداد زیر مجموعه های یک مجموعه ی عضوی برابر است با.

مثال

فرض کنید. تعداد زیر مجموعه های عضوی که شامل هیچ دو عضو متوالی نباشند را بیابید.
حل.
بین زیر مجموعه های تای که شامل هیچ دو عضو متوالی نیستند و تعداد زیر مجموعه های عضوی مجموعه ی یک تناظر یک به یک برقرار می کنیم.
فرض کنید یک زیر مجموعه عضوی باشد که شامل هیچ دو عضو متوالی نباشد. بدون کاسته شدن از کلیت مسئله می توان فرض کرد، ولی چون هیچ دو عنصری در متوالی نیستند بنابراین داریم: ،، ... و. در ----



نتیجه


حال اگر قرار دهیم:

به ازای هر مجموعه ای مانند ، یک مجموعه ی عضوی مانند وجود دارد و بالعکس. بنابراین یک تناظر یک به یک بین زیر مجموعه های مورد نظر و زیر مجموعه های عضوی وجود دارد. پس تعداد زیر مجموعه های مورد نظر برابر است با تعداد زیر مجموعه های عضوی ، یعنی برابر است با .

مثال

در یک مسابقه ی تیر اندازی، نه گوی در یک ستون دو تایی، یک ستون سه تایی و یک ستون چهار تایی مانند شکل زیر آویزان شده اند. یک تیرانداز ماهر می خواهد با روش زیر هر نه گوی را بشکند:
•ابتدا او یک ستون را انتخاب می کند تا هدفی از آن را بشکند.
•سپس او پایین ترین گویی را که قبلاً نشکسته است، هدف قرار می دهد.
اگر هیچ کدام از تیرهای این تیرانداز خطا نرود، او به چند طریق می تواند هر نه گوی را بشکند.
img/daneshnameh_up/7/71/com0021b.jpg

حل.
به ستون اول حرف ، به ستون دوم حرف و به ستون سوم حرف را نسبت می دهیم. هرگاه این تیرانداز ستونی را برای هدف گیری انتخاب کرد، حرف متناظر با آن ستون را می نویسیم. به این ترتیب یک تناظر یک به یک بین تعداد راه های تیراندازی و تعداد جایگشت ها کلمه ی برقرار می شود. پس تعداد راه های تیراندازی برابر است با.



مثال

یک مستطیل را با رسم خط هایی موازی عرض و طول آن به مربع واحد تقسیم کرده ایم.
الف.در شکل حاصل چند مستطیل دیده می شود؟
‌ب.در شکل حاصل چند مربع دیده می شود؟
img/daneshnameh_up/c/c7/com0021c.jpg

حل.
الف.می دانیم از تقاطع هر دو خط افقی و دو خط عمودی یک و فقط یک مستطیل ساخته می شود. بنابراین تعداد مستطیل های شکل فوق برابر است با تعداد راه های انتخاب دو خط افقی و دو خط عمودی. پس طبق اصل تناظر یک به یک چونخط افقی وخط عمودی داریم، تعداد مستطیل هایی که در شکل بالا دیده می شود برابر است با.
‌ب. می دانیم که هر مربع در شکل بالا با انتخاب نقطه ی گوشه ی سمت راست بالا (نقطه ) و طول آن مشخص می شود. حال تعداد مربع های به ضلع را می شماریم. نقطه ی روی تقاطع هر یک از خط افقی اول با هر یک ازخط عمودی اول می تواند باشد. پس نقطه ی را بهطریق می توان انتخاب کرد. پس تعداد مربع های به ضلع k در شکل فوق برابر است با. در نتیجه تعداد مربع های موجود در شکل فوق برابر است با.

مثال

جایگشت از مجموعه را در نظر بگیرید. این جایگشت دارای خاصیت است اگر به ازای حداقل یک بین 1 تا داشته باشیم.
ثابت کنید به ازای هر ، تعداد جایگشت های دارای خاصیت از تعداد جایگشت هایی که این خاصیت را ندارند بیش تر است.
به عنوان مثال اگرو مجموعه ی جایگشت های بدون خاصیت و مجموعه ی جایگشت های دارای خاصیت باشد، داریم:


واضح است که


حل.
حالت بدیهی است. پس فرض می کنیم باشد. فرض کنید مجموعه ی همه ی جایگشت های که دارای خاصیت نمی باشند (می باشند) باشد. برای این که نشان دهیم کافی است نشان دهیم تابع یک به یک و غیر پوشا است وجود دارد.
برای سادگی کار، زوج را یک زوج متناظر می نامیم. همچنین اگر زوج در جایگشتی متوالی باشند، آنها را زوج متناظر متوالی می نامیم.
فرض کنید یک عضو باشد. فرض کنید عضو متناظر باشد، چون دارای خاصیت نیست. پس. حال تعریف می کنیم:

تابع ، را دقیقاً قبل از قرار می دهد. واضح است که تنها زوج متناظر ماولی در است. (به عنوان مثال، و ) واضح است که و یک تابع از به می باشد.
حال نشان می دهیم که یک به یک است. فرض کنید


دو عضو باشند که زوج متناظر و زوج متناظر باشند، به طوری که. فرض کنید

واضح است که تنها زوج متناظر متوالی هستند. در نتیجه ،، . پس به ازای هر، . در نتیجه و یک تابع یک به یک است.
ولی مجموعه ی تمام جایگشت های دارای خاصیت است که دقیقاً یک زوج متناظر متوالی دارند. در نتیجه و. پس یک تابع یک به یک و غیر پوشا از به می باشد. پس حکم ثابت شد.



مثال

مجموعه ی را در نظر بگیرید. یک زیر مجموعه ی 31 عضوی خوب نامیده می شود اگر مجموع اعضایش بر پنج بخش پذیر باشد. تعداد زیر مجموعه های 31 عضوی خوب را بیابید.
حل.
فرض کنید مجموعه ی تمام زیر مجموعه های 31 عضوی باشد که باقی مانده ی آنها بر 5 برابر است. ثابت می کنیم یک تناظر یک به یک بین ها برقرار است.
فرض کنید یک عضو باشد. از روی هر، مجموعه را به این شکل می سازیم که، یعنی اگر باشد، و اگر باشد، . در نتیجه داریم:

بنابراین تابع یک به یکی داریم که به هر عضو، یک عضو و به هر عضو یک عضو را نسبت می دهد. در نتیجه

. ولی می دانیم
.

پس
.


مثال

فرض کنید تعداد مفهوم دنباله های دودویی به طول باشد که شامل هیچ زیر رشته ی010 نباشند و تعداد دنباله های دودویی به طول باشد که شامل هیچ زیر رشته ی1100 یا0011، نباشند. ثابت کنید برای هر عدد طبیعی ،.
حل.
به هر دنباله ی دودویی به طول ، دو دنباله ی دودویی به طول مانند و ، به این شکل نسبت می دهیم که،، و . واضح است که این یک تناظر یک به یک بین دنباله های دودویی به طول و دنباله های دودویی به طول که جمله ی اول آنها صفر (یک) است، می باشد. اگر به تناظر بالا نگاه کنیم می بینیم که باقی مانده ی تقسیم و بر دو یکسان است. در نتیجه تناظر یک به یک فوق هر دنباله ی دودویی به طول را که شامل زیر رشته ی010 نمی باشد به یک دنباله ی دودویی به طولکه شامل هیچ زیر رشته ی0011 یا1100 نمی باشد و جمله ی اول آنها صفر (یک) است، متناظر می کند. پس به ازای هر دنباله ی دودویی به طول که شامل زیر رشته ی0011 یا1100 نمی باشد وجود دارد. در نتیجه .



مثال

تعداد ماتریس های با درایه های 1 و 1- را پیدا کنید که حاصل ضرب عناصر هر سطر آن برابر 1- و حاصل ضرب عناصر هر ستون آن نیز برابر با 1- شود. ادعای خود را ثابت کنید.
اثبات.
اگر چنین ماتریسی وجود داشته باشد باید باشد. زیرا از یک طرف حاصل ضرب تمام درایه های این ماتریس برابر است با حاصل ضرب حاصل ضرب درایه های سطرهای آن یعنی و از طرف دیگر برابر است با حاصل ضرب حاصل ضرب درایه های ستون های آن یعنی. پس باید داشته باشیم یعنی و دارای زوجیت یکسانی باشند، دقیقاً ماتریس با شرط فوق وجود دارد. برای این کار نشان می دهیم که یک تناظر یک به یک بین تعداد ماتریس های با درایه های 1 و 1- و این گونه ماتریس ها وجود دارد.
یک ماتریس دلخواه با درایه های 1 و 1- را در نظر بگیرید. حال با سطر (سطر ام) و یک ستون (ستون ام) به آن اضافه می کنیم. حاصل ضرب عناصر سطر ام ماتریس اولیه را با و حاصل ضرب عناصر ستون ام ماتریس اولیه را با و حاصل ضرب تمام عناصر ماتریس اولیه را با

نشان می دهیم. درایه های سطر و ستون آخر ماتریس جدید به شکل زیر ساخته می شوند. درایه‌یبرابر است با. (چرا؟) واضح است که این تناظر یک به یک و پوشا می باشد. بنابراین تعداد ماتریس های مورد نظر برابر است با.


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

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

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




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


ارسال توضیح جدید
الزامی
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 در داخل توضیحات مجاز نیستند و تمام نوشته ها ی بین علامت های > و < حذف خواهند شد..