منو
 کاربر Online
1022 کاربر online
تاریخچه ی: دوگونه شمردن II

نگارش: 2



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


مثال

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

img/daneshnameh_up/8/83/com0038a.jpg

حالت تعداد رابطه های آشنایی (یال های) بین مجموعه افراد (رئوس) و مجموعه افراد (رئوس) را به دو طریق می شماریم.
فرض کنید یک رأس دلخواه از مجموعه ی باشد. طبق فرض مسئله تعداد همسایه های (آشناهای) مشترک و ، برابر است. پس تعداد یال های یک همسایه ی مشترک و می باشد و بالعکس. در نتیجه تعداد یال های بین مجموعه ی و برابر است با

حال فرض کنید یک رأس دلخواه از مجموعه ی باشد. طبق فرض مسئله تعداد همسایه های (آشناهای) مشترک و ، برابر است. پس تعداد یال های بین رأس و مجموعه ی برابر است. ولی طبق فرض مسئله تعداد کل یال های مجاور رأس (مجموع یال های بین و مجموعه ی و یال های بین و مجموعه ی برابر می باشد. در نتیجه تعداد یال های بین مجموعه ی و برابر است با

حال چونو برابر تعداد یال های بین مجموعه و هستند، پس داریم:




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

اثبات نامساوی های ترکیباتی



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

مثال

فرض کنید مجموعه ای از نقطه در صفحه باشد به طوری که
•هیچ سه نقطه ای بر یک استقامت نیستند.
•به ازای هر نقطه ی از مجموعه ی ، حداقل نقطه از یافت می شوند که از به یک فاصله اند.
ثابت کنید.
حل
تعداد کل پاره خط هایی که از دو نقطه از نقاط می گذرند را به دو طریق می شماریم. چون به ازای هر دو نقطه ای دقیقاً یک پاره خط وجود دارد، پس تعداد این پاره خطوط برابر است با.
حال برای هر نقطه مانند از این نقطه، حداقل نقطه وجود دارد که از آن به یک فاصله اند. پس این نقطه روی دایره ای به مرکز قرار دارند و پاره خط را مشخص می کنند. حال چون به ازای هر نقطه حداقل پاره خط وجود دارد، پس تعداد پاره خط ها حداقل است. اما در این بین از طرف دیگر هر خط را حداکثر دوبار شمرده ایم. زیرا اگر یک پاره خط را بیش از دوبار شمرده باشیم باید دوسر این پاره خط روی حداقل سه دایره قرار گرفته باشند. از طرف دیگر می دانیم که مرکز این دایره ها روی عمود منصف این پاره خط قرار دارد. پس سه نقطه پیدا کردیم که بر یک استقامتند. ولی این با فرض مسئله در تناقض است. در نتیجه هر پاره خط را حداکثر دوبار شمرده ایم. پس داریم:






مثال

فرض کنید یک گراف ساده با رأس و یال باشد. اگر باشد، ثابت کنید دوری به طول 4 دارد.
حل
از برهان خلف استفاده می کنیم. فرض کنید این گراف هیچ دوری به طول 4 نداشته باشد. حال برای حل این مسئله و دسیدن به تناقض تعداد جفت های متمایز رئوس را به دو طریق می شماریم. از یک طرف این مقدار برابر است با.
از طرف دیگر فرض کنید مجموعه رئوس متصل به رأس (مجموعه ی همسایه های ) باشد. واضح است که. حال به ازای هر دو رأس دلخواه و ،. زیرا اگر دو رأس و ، دو همسایه مشترک مانند و داشته باشند، دورxuyvx یک دور به طول 4 است و این برخلاف فرض است. پس هر د رأسی حداکثر یک همسایه ی مشترک دارند. حال به ازای هر رأس دلخواهی مانند ، تعداد جفت رأس های همسایه ی برابر است با و چون هیچ دو رأسی بیش از یک همسایه ی مشترک ندارند، پس تعداد جفت رأس های متمایز این گراف حداقل برابر است با. حال با توجه به این که تعداد جفت رأس های متمایز برابر است داریم:



حال با استفاده از نامساوی «ین سن» داریم:




و این برخلاف فرض مسئله است و به تناقض رسیدیم. پس این گراف دوری به طول 4 دارد.

مثال

فرض کنید یک گراف ساده با رأس و یال باشد. ثابت کنید این گراف حداقل مثلث (دور به طول 3) دارد.
حل
در این مسئله، به جای شمردن مستقیم تعداد مثلث ها، سعی می کنیم مثلث هایی را که به صورت اجباری به وجود می آیند بشماریم.
فرض کنید تعداد مثلث های گراف باشد. اگر مجموعه ی همسایه های رأس باشد، به ازای هر یال دلخواه داریم:

بنابراین به ازای هر دو رأس مجاور در ، حداقل رأس داریم که همسایه ی مشترک و هستند. در نتیجه تعداد مثلث هایی که شامل یال هستند حداقل خواهد بود. حال چون هر مثلث سه یال دارد، در نتیجه

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


مثال



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

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


با استفاده از نامساوی کوشی- شوارتز داریم:





مثال



در یک ضلعی محدب، تمام قطرها را رسم کرده این. اگر هیچ سه قطری همرس نباشند، ضلعی به چند ناحیه تقسیم می شود؟
حل
روش اول این مسئله، یکی از زیباترین مسایلی است که با استفاده از این تکنیک حل می شود. در این مسئله، ضلعی را به نواحی ای تقسیم کرده این. حال فرض کنید که تعداد سه ضلعی های به دست آمده را، تعداد چهار ضلعی های به دست آمده را و ... و بالاخره به تعداد ضلعی های به دست آمده را بگیریم. (حداکثر چه مقداری می تواند باشد؟) بنابراین مسئله از ما خواسته است که مقدار را به دست آوریم. ابتدا تعداد نقطه های داخلی را- که محل برخورد قطرهای ضلعی محدب می باشند- تعیین می کنیم. به ازای هر چهار رأس از رئوس ضلعی دقیقاً یک نقطه ی تقاطع داخلی وجود دارد. بنابراین تعداد نقطه های داخلی برابر است با. حال مجموع زوایای داخلی را به دو روش می شماریم؛ از یک طرف، این مقدار برابر است با مجموع زوایای داخلی تمام نواحی ایجاد شده:

و از طرف دیگر، می توان گفت که هر نقطه ی داخلی، به اندازه ی 360 درجه به مجموع زوایا اضافه می کند و علاوه بر نقاط داخلی، رئوس ضلعی نیز مجموعاً به اندازه ی درجه در مجموع زوایا سهم دارند. بنابراین، مجموع زوایای نواحی برابر است با:

در نتیجه:
(1)

حال مجموع رئوس تمام نواحی از یک طرف برابر با خواهد بود، و از طرف دیگر می توان گفت که رئوس داخلی، در 4 ناحیه و رئوس ضلعی در ناحیه شمرده می شوند. (چرا؟) بنابراین:
(2)

حال از روابط (1) و (2) به دست می آوریم که:

روش دوم. تعداد نقاط تلاقی قطرها داخل ضلعی برابر است با. پس یک گراف مسطح رأسی داریم که درجه ی رأس آن برابرو درجه ی رأس دیگر آن برابر 4 است. پس تعداد یال های این گراف برابر است با.
حال طبق قضیه ی اویلر در گراف های مسطح می دانیم. پس


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

مثال. قضیه ی sperner



فرض کنید که یک مجموعه ی عضوی و یک خانواده از زیر مجموعه های باشد، به طوری که برای هر داشته باشیم:img/daneshnameh_up/5/5d/com0038aa.jpg . ثابت کنید که حداکثر برابر است با.
اثبات
دنباله ی از زیر مجموعه های را، یک زنجیره به طول می نامیم هرگاه:

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

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



و چون بیش ترین مقدار، برابر است با. بنابراین:

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

مثال

فرض کنید عددی اول باشد و داشته باشیم:
img/daneshnameh_up/7/7d/com0038b.jpg


ثابت کنید که رابطه ی هم نهشتی زیر برقرار است:

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


img/daneshnameh_up/6/6b/com0038c.jpg

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

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

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

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





تاریخ شماره نسخه کاربر توضیح اقدام
 یکشنبه 14 آبان 1385 [11:42 ]   3   زینب معزی      جاری 
 یکشنبه 19 شهریور 1385 [11:14 ]   2   زینب معزی      v  c  d  s 
 پنج شنبه 16 شهریور 1385 [07:49 ]   1   زینب معزی      v  c  d  s 


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