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

[rezaezio]

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

خوب فرض استقرا قوی بود دیگه فرض کن A برشی باشه ، نتیجه میگیریم که نا متناهی بار به A میایم پس وارد یکی دیگه از مولفه ها میشیم و دوباره از فرض استفاده می کنیم !

مسئله 2 دوره 16 ! جوش کاری

 

[عمو ژپتو]

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

چرا یه حسی بهم میگه که این سوال کپی یه سوال sgu هه
فکر کنم رابطه بازگشتیش خیلی طولانی میشد اون سواله
خوب این شد رابطه
Ci,j=min ((Ci,i+1 +Ci+2,j),(Ci,i+2 +Ci+3,j).....,(Ci,j-1 +cj,j),(Ci,i +Ci+1,j))+ye عدد ثابت که میشه جمع همه با هم که برای همشون این رو داریم
من سوال پیشنهادی بعدیم رو هم میگم کسی هم رو این سوال مشکلی داشت یا خواست جوابی بده بده
سوال 4 روز اول دوره 13:صندوقچه های پر رمز و راز.

 

[smartgirl]

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

کسی جواب سوالای مرحله دوی چن سال اخیرو نداره؟
اگه کسی داره لطفا بهم پی ام بده!!!

 

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

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

چرا یه حسی بهم میگه که این سوال کپی یه سوال sgu هه
فکر کنم رابطه بازگشتیش خیلی طولانی میشد اون سواله
خوب این شد رابطه
Ci,j=min ((Ci,i+1 +Ci+2,j),(Ci,i+2 +Ci+3,j).....,(Ci,j-1 +cj,j),(Ci,i +Ci+1,j))+ye عدد ثابت که میشه جمع همه با هم که برای همشون این رو داریم
من سوال پیشنهادی بعدیم رو هم میگم کسی هم رو این سوال مشکلی داشت یا خواست جوابی بده بده
سوال 4 روز اول دوره 13:صندوقچه های پر رمز و راز.

اول یه گراف جهت دار براش تعریف میکنیم که طوقه هم میتونه داشته باشه این شکلی که راس متناظر با هر صندوقچه رو با یه یال جهت دار به راس متناظر با صندوقچه ای میبریم که عددش زیرش نوشته شده

خب این جا یه سری مسیر به وجود میاد و یه سری دور که حد اکثر طول یه مسیر هم n هست پس با n بار باز هردن هر کدوم از صندوقچه ها مسیر ها از بین میرن .
لم ۱ : در گراف حاصل نهایی یک سری دور جهت دار مجازا یال وجود داره .
اثبات : چون زیر هر صندوقچه دقیقا یک عدد نوشته شده پس هر راس دارای درجه خروجی دقیقه یکه حالا فرض کنیم دو تا دور وجود دارن که دارای حداقل یک راس مشترک هستن پس بلند ترین مسیر مشترکشون رو در نظر میگیریم و راس پایانی این مسیر باید حداقل دارای درجه خروجی ۲ باشه که تناقضه .

حالا هر بار یک صندوقچه رو انتخاب میکنیم بازش میکنیم اگر دو باره بازش میکنیم بعد از اون هر کردوم از n - 1 صندوقچه دیگه رو یه بار باز میکنیم بعد این صندوقچه رو باز میکنیم اگه مقدارش تغییر کرده بود یعنی یه یال بین این دو تا صندوقچه هست و اگر در پایان هیچ یالی پیدا نشد یعنی این صندوقچه به خودش میره یا جز یک مسیر بوده

این کار رو ادامه میدیم تا زمانی که تمام دور ها مشخص شن بعد هم تعداد یاقوت ها رو به دست میاریم

سوال پیشنهادی بعدی همین دوره ۱۳سوال دومش لدفن

 

[rezaezio]

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

دوره 13 - سوال 2
من قبلا اینو حل کرده بودم ؛ ولی جوابم رو نمی تونم تایپ کنم !
مثالم رو برای n=9 میزارم ، حتما میفهید که روش چیه و اثبات درستیش هم کشکه


مساله درخواستی : دوره 17 - روز اول - سوال 4 - کشور برهوت

 

[عمو ژپتو]

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

آقا من یه جواب میگم ولی خوب خیلی اثبات دقیق نمینویسم .
برا آلفا بین 0-1 گراف کامل
و برای آلفا بزرگتر از 1 ستاره .
اگه دقت کنید وقتی آلفا بین 0-1 خوب هزینه ساخت یه جاده کمتر از اینه که بخوایم از یه شهر به یه شهر دیگه با بیش از یه جاده بریم پس بجاش جاده میکشیم بینشون خیلی راحت
و برا آلفا بزرگتر از یک.
حداقل که گرافمون باید همبند باشه (بدیهیه .بینهایت خیلی بزرگ )
خوب
بعد تو ستاره شما از هر راس به هر کدوم دیگه با حداکثر 2 تا میری
خوب آقا واقعا به صرفه نیست بخوای بینشون جاده بکشی
تازشم از راس مرکزی به همه با یکی میری خداییش خیلی خوبه
خوب سوال بعد .

 

[rezaezio]

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

بسیار خوب
مسئله 4 دوره 16 - خط ارتباطی

 

[مهسا.ق]

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

تاپیک هم پیشنهاد MeC بود من هیچ ادعایی رو ایده تاپیک ندارم

 

[most wanted]

پاسخ : سوال های مرحله 2 تستی

1)

گزینه د
استقرا می زنیم:
فرض: برای n-1 خط این تعداد برابر 1 +3*(n-1) است.
گام: حالت n خط را فرض کنید،بالاترین خط را ( برای راحتی) کنار بگذارید.طبق فرض استقرا تعداد نواحی مشخص است. خط جدید را که اضافه کنیم.همه ی ناحیه های قبل را داریم،چون اگر خطی میان راه به خط جدید برخورد کرده باشد ناحیه باز هم ساخته میشه ( نیاز به شکل داره دست به قلم شید واضح میشه) و این 2 خط عمودی جدید ناحیه ای با ضلع بالایی می سازند و دو ناحیه با خطوط سمت راست و چپ ـِشان.
و برای پایه ام که مستطیل بدون خط 1 ناحیه دارد.
از گام میتوان برداشت کرد که اگر دوتا از خط های عمودی اشتراک داشته باشند،تعداد نواحی بیشینه نمیشود.

پ.ن.: می دونم شکل برای توضیح میخواد ولی شکل کشیدن از سایز من خارجه.

 

[Dark Eagle]

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

آقا من یه جواب میگم ولی خوب خیلی اثبات دقیق نمینویسم .
برا آلفا بین 0-1 گراف کامل
و برای آلفا بزرگتر از 1 ستاره .
اگه دقت کنید وقتی آلفا بین 0-1 خوب هزینه ساخت یه جاده کمتر از اینه که بخوایم از یه شهر به یه شهر دیگه با بیش از یه جاده بریم پس بجاش جاده میکشیم بینشون خیلی راحت
و برا آلفا بزرگتر از یک.
حداقل که گرافمون باید همبند باشه (بدیهیه .بینهایت خیلی بزرگ )
خوب
بعد تو ستاره شما از هر راس به هر کدوم دیگه با حداکثر 2 تا میری
خوب آقا واقعا به صرفه نیست بخوای بینشون جاده بکشی
تازشم از راس مرکزی به همه با یکی میری خداییش خیلی خوبه
خوب سوال بعد .

این که ستاره بهترینه رو با استقرا باس ثابت کنی................
راحت ثابت میشه.................
آقا کسی سوال 2 دوره 17 کلاس ب رو حل کرده ؟؟؟؟..................>>مهمان نوازی افراطی<<
B-)

 

[عمو ژپتو]

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

کدوم سسوال میشه دقیقا ؟

 

[Dark Eagle]

پاسخ : سوال های مرحله 2 تستی

2+4+8+16+32+64+128+256+512=1023
درنتیجه بزرگترین عددی که میتوان بدان دست یازید 2 به توان 1398 است.
و ما هم چنان 990 عدد دیگر داریم که با آن ها می توان نمام ارقام عدد حاصل را یک کرد.
و چون 2 به توان 1398 دارای 1399 رقم می باشد جواب برابر 1399 است.
B-)
3-در داخل هر وجه خانه وسط مربع 3*3 را رنگ می کنیم.
حا هر مکعب 2*2*1 که انتخاب نماییم دارای یک خانه ی سیاه می باشد.
B-)

* پستت ادغام شد ، پشت ِ سر هم پست نده .

 

[most wanted]

پاسخ : سوال های مرحله 2 تستی

4)
بر اساس 4 خطی که از نقطه وسط می گذرند حالت بندی می کنیم.(خطوط مشکی یکتا تعیین شده و رنگی ها به جز قرمز نشانه حالت های مختلف است.


پ.ن.:عکس ها روشون کلیک کنید بزرگ ام میشن.
سوال 2 رو میشه بیشتر توضیح بدی؟

 

[rezaezio]

پاسخ : سوال های مرحله 2 تستی

5-


اثبات کمینه بودن عدد 10
فرض کنید می خوایم بزاریمشون تو دو دسته A و B ! پس اولش 20^2 حالت داریم
خب واضحه با هر نتیجه ای که به دست بیارید ، تعداد جواب مسئله رو تقسیم به 4 کردید
یعنی قدرت تفکیکمون 4 هست
پس واضحه برای اینکه به 1 حالت درست مسئله برسیم باید 10 مرحله حداقل کارمون رو انجام بدیم !

و میمونه راهی با 10 مرحله : اولش 6 دسته 3 تایی درست می کنیم و یک دسته 2 تایی
حالا تو 6 مرحله هر کدوم از اون 6 دسته رو از هم جدا میکنیم و در 3 مرحله با هم ادغام
حالا هم اون 2 تای بیرونی رو با یکی از 18 تای بقیه در نظر میگیریم و 2 دستمون درست میشه #

 

[most wanted]

پاسخ : سوال های مرحله 2 تستی

6)

حالت رو آمدن سکه را با یک و پشت آمدن را با صفر متناظر می کنیم.در این صورت ممکن است تمام اعداد 4 رقمی در مبنای 2 ساخته شود.که تعدادشان 16تاست.
حالت های مطلوب آنهایی اند که هیچ دو 1 و هیچ دو 0 ای پشت سر هم نیایند،یعنی:1010 ، 0101
و کل حالات هم 16 تاست;پس احتمال اینکه بعد از 4 حرکت هیچ 2 تایی مثل هم نباشند برابر است با:یک هشتم یعنی گزینه 1

واسه سوال 5 یه مسال 10 تایی دیگه: اول 3 تا رو به دلخواه می دیم به دست گاه هر نتیجه ای که داد از یکی از دسته ها یکی ور میداریم،بعد بقیه رو 9 دسته دوتایی می کنیم و دوتا دوتا با این سکه می دیم به دستگاه که این سکه بقیه رو تفکیک کنه.
در ضمن سوال ها متفاوت اند واسه شکل تاپیک ام که شده نباید تفکیک شه.

 

[crazyboy]

پاسخ : سوال های مرحله 2 تستی

1)

گزینه د
استقرا می زنیم:
فرض: برای n-1 خط این تعداد برابر 1 +3*(n-1) است.
گام: حالت n خط را فرض کنید،بالاترین خط را ( برای راحتی) کنار بگذارید.طبق فرض استقرا تعداد نواحی مشخص است. خط جدید را که اضافه کنیم.همه ی ناحیه های قبل را داریم،چون اگر خطی میان راه به خط جدید برخورد کرده باشد ناحیه باز هم ساخته میشه ( نیاز به شکل داره دست به قلم شید واضح میشه) و این 2 خط عمودی جدید ناحیه ای با ضلع بالایی می سازند و دو ناحیه با خطوط سمت راست و چپ ـِشان.
و برای پایه ام که مستطیل بدون خط 1 ناحیه دارد.
از گام میتوان برداشت کرد که اگر دوتا از خط های عمودی اشتراک داشته باشند،تعداد نواحی بیشینه نمیشود.

پ.ن.: می دونم شکل برای توضیح میخواد ولی شکل کشیدن از سایز من خارجه.

استقراتو کامل نخوندم ولی خیلی خرکاری داره با فرمول اویلر 3 سوت به دست میاد!

 

[rezaezio]

پاسخ : سوال های مرحله 2 تستی

7- گزینه ج - 9


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


8- گزینه ب - 1391


در پایان تمامی سکه ها به رو هستند پس هر سکه زوج بار برگشته است
n سکه داریم که هر کدام زوج بار برگشته هستند پس در کل ما به تعداد زوج بار وضعیت سکه ها را عوض کرده کرده ایم !
می دانیم ما در کل به اندازه مجموع 1 تا n سکه ها را تغییر داده ایم ، پس 1 تا n باید زوج باشد و با بررسی گزینه ها میبینیم که فقط گزینه ب است که این ویژگی را دارد.

 

[rezaezio]

پاسخ : سوالات مرحله 2 - تشریحی

مهمان نواز افراطی ! هنوز در درک این سوال مشکل دارم من ، بیاید بگذریم از این سوال

اینو حل کنید ، سخته یکم : مسئله 5 - دوره بیست - دنباله - قسمت ب

 

[Dark Eagle]

پاسخ : سوالات مرحله 2 - تشریحی

یک خبر :
سوال مهمان نوازی افراطی غلطه................ B-)
روش فکر نکنید ..............
گوینده خبر :طلای پارسال (تو حلی 1 عکسشو زدن اون وسطیه رو میگم)
B-)

 

[Elham :)]

پاسخ : سوالات مرحله 2 - تستی

9.
با بررسی حالت هایی که کلید ها میتونن داشته باشن متوجه میشیم کلید ها از یه حالت خارج نیستن :
دوتاشون مثل همن اون یکی عدد مخالف اونه . اگه غیر از این باشه لامپ روشن میشه .(ما به حالت کلید ها رو درنظر میگیریم AAB)
حالا ما تصادفی یک کلید رو فشار میدیم ، دوحالت به وجود میاد :
*کلیدی که متفاوته عوض میشه یعنی AAB به AAA تغییر کرده که دراین صورت کارمون تمومه #
*کلید دیگری رو انتخاب کردیم که جفت بودن : AAB به ABB تغیییر میکنه .
واسه مرحله بعد کلید دیگری رو انتخاب میکنیم :
*اگه دوباره کلید تک رو انتخاب کنیم که کار حلّه . . .(ABB به BBB )
*اگه دوباره یکی از کلید های تکراری رو انتخاب کنیم حالت از ABB به ABA تغییر میکنه ) [ دقت کنید که نباید کلید تکراری رو بزنیم ]
وحالا اگه دوباره همون کلیدی رو مرحله اول زده بودیم بزنیم لامپ روشن میشه (از ABA به AAA) :)
اثبات :
تو مرحله ی اول وقتی که کلیدی رو میزنیم و روشن نمیشه یعنی این که اون دو تای دیگه با هم متفاوت هستن .
میدونیم وقتی دوتا کلید متفاوت هستن ، با فشار دادن کلید هر کدوم یکسان میشن . حالا ما تو مرحله دوم دو تای دیگه رو مطمئنا یکسان کردیم پس اونی که متفاوته ؛ کلیدیه که مرحله اول فشارش دادیم .

جوابش : 3