رنگ کردن اعضای یک مجموعه با شرط نداشتن زیرمجموعه تکرنگ
انتخاب یک مجموعه از رئوس گراف و یافتن رئوسی که با تعداد فردی از ان ها مجاورند
استقرا در ترکیبیات و رفع ابهام
استقرای ضعیف روی مجموعه متناهی
در یک جمع k نفره ، در بین هر 4 نفر یکی وجود دارد که 3 نفر دیگر را میشناسد . ثابت کنید فردی وجود دارد که همه را بشناسد .
سلام میدونستید انجمن علمی نخبگان دانشگاه صنعتی شریف مسابقه تخصصی مهارت سنجی برنامه نویسی و داده کاوی گذاشته است آدرس سایتش www.fanavard.com
2015-08-06 06:11:42 -0500 امیر شکریسلام میگم یک سر به سایت www.fanavard.ir بزنید. مسابقات برنامه نویسی شون شروع شده. گواهی رسمی از طرف دانشگاه شریف می ده. 50 تا سکه هم جایزشه
2016-10-26 10:10:01 -0500 امیر شکریسلام شب تون ب خیر :)
ما به جای هر نفر یه راس میزاریم و بین دو نفر که همو میشناسن یال میزارم .طبق گفته مسئله فرض بر این است که در هر زیر گراف 4 راسی راس است که به سه راس دیگر متصل است .
استقرا میزنیم روی $k$ :
پایه : برای $k=1$ چنین راسی طبق فرس می باشد.
فرض کن برای $k=n$ درست باشه ما میخوایم برای $k=n+1$ اثبات کنیم .
ابتدا یک راس به نام $v$ را حذف میکنیم و سپس روی$n$ راس باقی مانده استقرا رو عملی میکنیم .خب طبق ان استقرا راسی به نام $u$ در این $n$ تا راس هست که به همه وصل هست. خب ما حالا میایم دو حالت زیر را در نظر میگیم:
1- در این $n$ راس دو راس هسنتد که بینشان هیچ یالی نیست . پس آن دو راس به همراه رئوس $u$ و $v$ در نظر میگیم راسی هست که به 3 راس متصل است این راس قطعا بین $u,v$ است پس باز نیز u جواب است .
2- در این $n$ راس هیچ دو راس که بهم متصل نباشند نداریم. پس سه راس دلخواه را به همراه $v$ میگیم . که جواب دحتما یکی از این سه راس است .
