المپیاد سری سوال های آمادگی مرحله دوم

[erfan_ashorian]

سلام ! خو این انجمن سابقه برگزاری ازمون آزمایشی مرحله اول ناموفق و داره حالا میخوایم ببینیم با این که خیلی نمونده به مرحله دوم بازم این تاپیک ناموفق میشه یا نه
خو من یه سری سوال میزارم و بچه ها جواب بدن اگه کسی سوالی چیزی داره بزاره و هیچ قانونی هم نسبت به ترتیب جواب دادن نیست یعنی هر وقت فکر کردین سوال خوبی دارین بزارین چرا که نه :)
و البته این سوال پیش میاد که چرا سوال ها رو تو تاپیک مخصوص به خودش نزاشتم که دلیلشو بعدن میگم :)
سوال اول ) در یک مهمانی n نفر حضور دارند که از ۵ نفر بیشترند در بین هر سه نفر حداقل دو تا با هم دوستند ثابت کنید میتوان حداقل n/2نفر انتخاب کرد و ان ها را دور یک میز نشاند به طوری که هر فرد کنار دوستان خود باشد . . .

 

[rezaezio]

پاسخ : سری سوال های آمادگی مرحله دوم

سلام !‌

اولا، کافیه واسه n های فرد مساله رو ثابت کنیم، چون هر n زوجی از روی فرد قبلیش ثابت میشه !

حالا استقرا میزنیم روی n
پایه استقرا که بدیهیست ( اصلا هم بدیهی نیست )
گام
دو راس که به هم وصل نیستند رو در نظر بگیرید ! اگه چنین جفتی پیدا نشه، گراف کامل هست و دور به طول n داره‌!
با A و B نامگذاریشون میکنیم‌! خُب حالا این دور راس رو حذف کنید، طبق فرض استقرا برای n-2، بین اون n-2 راس باقی مانده، یه دور به طول حداقل نصفشون داریم ! حالا کافیه یکی از A و B رو به این دور اضافه کنیم تا حکم ثابت بشه !
از اونجا که A و B به هم وصل نیستن، هر راس از دور مورد نظر،‌ به حداقل یکی از این دو راس یال دارن !
لم ستاره :‌ اگه دو راس متوالی از دور به A وصل باشن، یا به B وصل باشن،‌ میتونیم دور رو افزایش بدیم و مساله حل هست !!
اگه طول دور اولیه فرد باشه، واضحه که شرایط لم ستاره برقرار میشه و مساله حل میشه ! پس طول اون دور زوج هست و می دونیم حداقل 4 هست ! حالا راس ها رو سیاه سفید میکنیم‌ و دسته سفید رو به A و بقیه رو به B وصل میکنیم ! از اونجا که B به هیچکوم از راس های دسته سفید وصل نیست،‌ پس دسته سفید یه گراف کامل هست ! همین شرایط واسه دسته سیاه هم برقرار هست ! پس زیرگراف A + دسته سفید یه زیر گراف کامل هست، و زیر گراف B + دسته سیاه هم زیر گراف کامل هست !!
حالا دو تا گراف کامل داریم، که هر گراف حداقل سه راس داره، و به جز یکی از راس ها در هر گراف، بقیه به حداقل دو راس در زیر گراف مقابل یال دارن ! واضحه که یه دور داریم که کل راس های دو زیر گراف رو در بر میگیره ! اگه کسی با این تیکه آخر مشکل داره، بگه ثابت کنم !

پ.ن :‌ امیدوارم فهمیده باشید چی گفتم و اینکه درست گفته باشم !

 

[erfan_ashorian]

پاسخ : سری سوال های آمادگی مرحله دوم

خو جوابت درسته البته اگه اون اخراشو درست فهمیده باشم ! به هر حال من که خودم راهم شبیهه توعه و وقتی دور زوجه ثابت میکنم کله اون دوره و راس های a , b تو دورند . . . خو سوال بعدی‌:
ثابت کنید افرازی از مجموعه ی
۱ و۲ و۳ و . . . .۲^n (
(۱ و ۲ و ۳ تا دو به توان ان!!) وجود دارد به طوری که در هیچ دسته ای تصاعدحسابی به طول 2n وجود نداشته باشد . . .

 

[Fliqpy]

پاسخ : سری سوال های آمادگی مرحله دوم

فک کنم اشتباه فهمیدم ولی مگه تک عضوی ها افراز نیستن? تصاعدی هم وجود نداره
در ضمن برای سوال قبل همون تیکه ای که سیاه سفید کردیم اگه 1234 تو دور چهار تا راس متوالی باشن,
نمیتونیم این,مسیر رو به دور اضافه کنیم و طولش رو زیاد کنیم?
1A32B4

 

[mrym_msb]

پاسخ : سری سوال های آمادگی مرحله دوم

خو سوال بعدی‌:
ثابت کنید افرازی از مجموعه ی
۱ و۲ و۳ و . . . .۲^n (
(۱ و ۲ و ۳ تا دو به توان ان!!) وجود دارد به طوری که در هیچ دسته ای تصاعدحسابی به طول 2n وجود نداشته باشد . . .

سلام!

تعداد کل تصاعد های حسابی به طول 2n رو با انتخاب عضو اول و دوم حساب میکنیم (تقریبی البته!) این خودش 2 حالت داره که تو کدوم دسته باشه بقیه اعضام هرکدوم 2 انتخاب دارن بعد معلومه که اینا تعدادشون از کل افراز های مجموعه به در دسته کمتره

 

[erfan_ashorian]

پاسخ : سری سوال های آمادگی مرحله دوم

شرمنده ی همه این مجموعه باید به دو دسته تقسیم بشه ها!! افراز به دو مجموعه. . . .

 

[فات]

پاسخ : سری سوال های آمادگی مرحله دوم

خب سوال بزار بازم

 

[erfan_ashorian]

پاسخ : سری سوال های آمادگی مرحله دوم

سلام! با این که پست استقبال نشذ ولی چشم‌:)
سوال باحال‌ : برای بازی نیم یک استراتژی برد پیدا کنید :) البته اگه شنیدید که هیچی

 

[فات]

پاسخ : سری سوال های آمادگی مرحله دوم

اول میخوای یه خلاصه از نیم بزارم؟

 

[مهدی]

پاسخ : سری سوال های آمادگی مرحله دوم

متاسفانه طبق حرفی که نیما زد طرح شکست خورد . #شت مثلا
البته فعلا تو بخش کامپیوتر مسابقه ای داره برگزار میشه
احتمالا یه طرح دیگه ای بذاریم برای انجمن ریاضی