آرشیو - گفت و گو ها پیرمون مراحل مختلف ، دوران مختلف

[arvin.a]

پاسخ : نتایج مرحله اول المپ کام

سایت باشگاه که باز نمیشه اه

 

[most wanted]

پاسخ : نتایج مرحله اول المپ کام

سایت باشگاه که باز نمیشه اه

یکم سنگینه نمدونم چرا
واس من 1 دقیقه طول کشید. :)

 

[crazyboy]

پاسخ : سوالات مرحله 2 (فقط 2)

ثابت کنید اگه گراف کامل n راسی رو بشه به تعدادی مثلث افراز کرد گراف کامل n × 2 + 1 راسی رو هم میشه کرد!

 

[Dark Eagle]

پاسخ : سوالات مرحله 2 (فقط 2)

n تا تو دسته 1 و n تا تو دسته 2.
طبق فرض استقرا هر دسته را می افرازیم.
سپس یک راس باقی مانده را در نظر میگیریم.
سپس یک راس از دسته 1 و یک راس از دسته 2 انتخاب میکنیم.
این 3 راس تشکیل یک مثلث جدید می دهند این کار را تا تمام شدن راس های انتخاب نشده از هر دسته ادامه می دهیم.
تعتداد راس های دسته 1 و 2 برابر است.
◘

 

[kia.celever]

پاسخ : سوالات مرحله 2 (فقط 2)

یه سری مثلث هستن که مثلاً 2 تا رأس تو دسته 1 دارن و یه رأس تو دسته 2. اونارو چیکار می کنیم؟

 

[علــی[میم]]

پاسخ : سوالات مرحله 2 (فقط 2)

اگر بخوایم این شکلی تقسیم کنیم تو هر دسته که نصف n^2 - n یال وجود داره که رو هم میشه n^2 - n یال و آخر بار هم 3n تا یال استفاده میشه کلا میشه n^2 + 2n اما کل یال ها 4n^2 + 2n تاست جواب این 3n^2 تا یال باقی مونده رو کی میخواد بده آخه ؟

 

[kia.celever]

پاسخ : سوالات مرحله 2 (فقط 2)

بعد نکته اینجاست که اون گرافی که باقی می مونه دو بخشیه. یعتی مثلث نداره اصن و راه حل به بن بست می خوره!

 

[crazyboy]

پاسخ : سوالات مرحله 2 (فقط 2)

n تا تو دسته 1 و n تا تو دسته 2.
طبق فرض استقرا هر دسته را می افرازیم.
سپس یک راس باقی مانده را در نظر میگیریم.
سپس یک راس از دسته 1 و یک راس از دسته 2 انتخاب میکنیم.
این 3 راس تشکیل یک مثلث جدید می دهند این کار را تا تمام شدن راس های انتخاب نشده از هر دسته ادامه می دهیم.
تعتداد راس های دسته 1 و 2 برابر است.
◘

جوابت پر از سوراخه! :)

اینم یه سوال دیگه رو اینم فکر کنید :‌
ثابت کنید هر گراف رو میتونیم راس هاشو به دو مجموعه افراز کنیم که درجه جدید هر راس (تعداد یال هایی که به راس های مجموعه خودش وصله) زوج باشه!

 

[عمو ژپتو]

پاسخ : سوالات مرحله 2 (فقط 2)

بچه ها من الان یه چیز جالب که متوجه شدم این سوال گراف همین Kn سوال دوره 2 سال پیش برا جدا کردن برنز ها بوده زود نیست یکم
ینی شما مرحله 2 های خودمون رو خوردید دیگه که رفتید سراغ سوالات دوره ها
ماشاالله بر شما

 

[rezaezio]

پاسخ : سوالات مرحله 2 (فقط 2)

بچه ها من الان یه چیز جالب که متوجه شدم این سوال گراف همین Kn سوال دوره 2 سال پیش برا جدا کردن برنز ها بوده زود نیست یکم
ینی شما مرحله 2 های خودمون رو خوردید دیگه که رفتید سراغ سوالات دوره ها
ماشاالله بر شما

بعضی از سوال های دوره ، از سوالای مرحله 2 آسون ترن

 

[مهسا.ق]

پاسخ : سوالات مرحله 2 (فقط 2)

بعضی از سوال های دوره ، از سوالای مرحله 2 آسون ترن

ببین حرفت درسته ولی موضوع سختی یا آسونی نیس موضوع یه تیپ خاصیه که مرحله 2 داره
نمی گم فقط مرحله 2 کار کنید و اینا و اصلا سوالای دیگه رو حل نکنید این دید خیلی اشتباهه ولی کلا دارم می گم به سختی و آسونیش الان نیگاه نکن
سوال های مرحله 2 یه تیپ خاصی دارن یه سری ایده ریز می خورن راحت حل می شن! توصیه می کنم بیشتر تو این تاپیک سوال های مرحله 2 بذاریم تا با تیپ مرحله 2 آشنا شیم
سوال های قشنگی رو که پیدا کردیم رو هم می تونیم اینجا بذاریم

 

[rezaezio]

پاسخ : سوالات مرحله 2 (فقط 2)

امروز این انجمن , جون گرفته
خب پس مسئله 4 ؛ دوره 14 رو حل کنید ( خاطره نویسی بارون ) !
اینم لینکه تصویر سوال ؛ دانلود کنید که همیشه بتونید سوالو ببینید
Khatere nevisi Baron.png - 192 KB

 

[عمو ژپتو]

پاسخ : سوالات مرحله 2 (فقط 2)

آقای بیا و مردونگی کن از این سوال بگذر
این تن بمیره
آخه مرد مومن آدم میاد با سخت ترین سوال تو تمامی مرحله 2 ها شروع میکنه
این همه سوال آسون و خوشکل
اصلا من سوال اول رو بگم با اجازه
سوال 4 دوره 20 ام

 

[rezaezio]

پاسخ : سوالات مرحله 2 (فقط 2)

آقای بیا و مردونگی کن از این سوال بگذر
این تن بمیره
آخه مرد مومن آدم میاد با سخت ترین سوال تو تمامی مرحله 2 ها شروع میکنه
این همه سوال آسون و خوشکل
اصلا من سوال اول رو بگم با اجازه
سوال 4 دوره 20 ام

چون در هر مرحله دقیقا به یک شهر می تونیم بریم ، پس مراحل ما نا متناهی هستند.

لم : تابع تعداد شهر هایی که از آن ها گذر کرده ایم ، صعودی است.
اثبات : فرض کنید صعودی نباشد ، یعنی بعد از اینکه k شهر را دیدیم دیگر به هیچکدام از n-k شهر دیگر نرویم.
راس A را که یکی از n-k راس است را در نظر بگیرید.
اگر در مراحلمان به شهر A رفتیم ؛ انگاه تابع ما صعودی بوده است و فرض خلف ما غلط است.
ولی اگه هرگز به شهر A نرویم می توانیم شهر A را از کشورمان حذف کنیم و از فرض استقرای زیر استفاده کنیم.
فرض استقرا : اگر n-1 شهر داشته باشیم ، تابع تعداد شهر های دیده شده صعودی است.
پس طبق فرض استقرا n-1 شهر به غیر از A را میبینیم ؛ پس تابع صعودی بوده است.

در مرحله ای که n-1 شهر را دیده باشیم و یک شهر مانده باشد ( شهر B ) ؛ گام استقرا جواب نمی دهد.
شهر B به یکی از شهر های دیگر وصل است ( شهر C )

طبق استدلالمان ما شهر یک بار C را میبینیم حال وقتی شهر C را دیدیم فرض می کنیم هیچ شهری را تا کنون ندیده ایم و دوباره از فرض استقرایمان استفاده می کنم و می دانیم دوباره شهر C را میبینیم و اگر این کار را ادامه دهیم میبینیم تعداد نا متناهی بار از شهر C گذشته ایم و چون ساعت گرد می چرخد یکی از متناهی بار از C به B می رویم و شهر B رو هم میبینیم !

کلا خودم با جوابم حال نکردم

 

[Dark Eagle]

پاسخ : سوالات مرحله 2 (فقط 2)

یک سوال:
مگه مثلث بندی استفاده از تمامی یال ها نیست ؟؟؟.
(در مثلث های گوناگون)
؟؟؟
B-)
فهمیدم جوابم غلطه//.....
B-)

 

[rezaezio]

پاسخ : سوالات مرحله 2 (فقط 2)

مگه مثلث بندی استفاده از تمامی یاب ها نیست ؟؟؟.
(در مثلث های گوناگون)
؟؟؟
B-)

نیما یه توضیحاتی در مورد این پستت بده

 

[Dark Eagle]

پاسخ : سوالات مرحله 2 (فقط 2)

هیچی فهمیدم .
نت قاطی کرده یهو صفحه میپره میره یه جا دیگه....
آقا میشه سوال فلش های دوره ی 8 رو حل کنید.؟
دو ماه روش فکر کردم حل نشد....
(و این داستان ادامه دارد)
B-)

 

[عمو ژپتو]

پاسخ : سوالات مرحله 2 (فقط 2)

چون در هر مرحله دقیقا به یک شهر می تونیم بریم ، پس مراحل ما نا متناهی هستند.

لم : تابع تعداد شهر هایی که از آن ها گذر کرده ایم ، صعودی است.
اثبات : فرض کنید صعودی نباشد ، یعنی بعد از اینکه k شهر را دیدیم دیگر به هیچکدام از n-k شهر دیگر نرویم.
راس A را که یکی از n-k راس است را در نظر بگیرید.
اگر در مراحلمان به شهر A رفتیم ؛ انگاه تابع ما صعودی بوده است و فرض خلف ما غلط است.
ولی اگه هرگز به شهر A نرویم می توانیم شهر A را از کشورمان حذف کنیم و از فرض استقرای زیر استفاده کنیم.
فرض استقرا : اگر n-1 شهر داشته باشیم ، تابع تعداد شهر های دیده شده صعودی است.
پس طبق فرض استقرا n-1 شهر به غیر از A را میبینیم ؛ پس تابع صعودی بوده است.

در مرحله ای که n-1 شهر را دیده باشیم و یک شهر مانده باشد ( شهر B ) ؛ گام استقرا جواب نمی دهد.
شهر B به یکی از شهر های دیگر وصل است ( شهر C )

طبق استدلالمان ما شهر یک بار C را میبینیم حال وقتی شهر C را دیدیم فرض می کنیم هیچ شهری را تا کنون ندیده ایم و دوباره از فرض استقرایمان استفاده می کنم و می دانیم دوباره شهر C را میبینیم و اگر این کار را ادامه دهیم میبینیم تعداد نا متناهی بار از شهر C گذشته ایم و چون ساعت گرد می چرخد یکی از متناهی بار از C به B می رویم و شهر B رو هم میبینیم !

کلا خودم با جوابم حال نکردم

آقا یه حسی به من میگه خیلی بد گفتیا ینی افتضاح
نمدونم والا
کسی دیگه هم توضیح بده خوشحال میشیم با این وضعیت م2 نمره میدن جدی
اصلا این حل هیچیش به هیچ جا نبود

 

[rezaezio]

پاسخ : سوالات مرحله 2 (فقط 2)

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

فرض استقرا : اگر کمتر از n شهر داشته باشیم , با هر وضعیت اولیه خروجی ها می توانیم از همه شهر ها دیدن کنیم.
گام استقرا : حال n شهر داریم ؛ اگر به همه شهر ها رسیدیم که حکم بر قرار است .
فرض کنید به شهر A نرسیم ! حال از فرض استقرا استفاده می کنیم ؛ می دانیم که چون n-1 شهر باقی مانده است و از هیچ کدام به شهر A نرفته ایم پس می توان فرض کرد که شهر A وجود ندارد.حال n-1 شهر داریم و طبق فرض استقرا از همه آن ها دیدن کرده ایم.
حال فقط کافیست ثابت کنیم از شهر A هم عبور می کنیم.
شهر A به حداقل یکی از n-1 شهر دیگر وصل است , نام آن شهر را شهر B می گذاریم.
چون شهر A به B وصل است پس پس از K مرحله میدان شهر B به سمت A باز می شود , حال کافیست ثابت کنیم k بار به شهر B می رویم.

لم : وقتی n-1 شهر داشته باشیم ، به هر کدام می توان نامتناهی بار سفر کرد.
طبق فرض استقرا می توان به هر کدام از آن ها 1 بار سفر کرد.حال زمانی که هر کدام را یک بار دیدیم را در نظر بگیرید ؛ فرض کنید در شهر C باشیم ؛ حال می توان فرض کرد که هیچ شهر را تا کنون ندیده ایم و داریم از شهر C شروع می کنیم ، پس دوباره طبق فرض استقرا از همه شهر ها دیدن می کنیم ، و این روند ادامه دارد ...

لم ثابت شد پس K بار به شهر B وارد می شویم و در K امین بار از B به A می رویم ، حال میبینیم که به n شهر رفته ایم !

( این دیگه آخر مهارتم تو نوشتن پشت PC بود )

 

[عمو ژپتو]

پاسخ : سوالات مرحله 2 (فقط 2)

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