سوالات مرحله 2 سال 94

  • شروع کننده موضوع
  • #1

sara.a1999

کاربر فعال
ارسال‌ها
70
امتیاز
56
نام مرکز سمپاد
دبیرستان فرزانگان 1
شهر
تهران
مدال المپیاد
یک کوله بار عشق به ریاضی-برنز 95
سلام دوستان،
این روزها که بحث اعتراض و کامل کردن راه حل ها داغه، خوبه که ما هم در این میان راه حل های خلاقانه و جالب خودمون رو (متفاوت با باشگاه)
اینجا ارائه بدیم و کلی ایده خوب از هم یاد بگیریم...
پس لطفا با گذاشتن شماره سوال (یادتون نره!) راه جدیدتون رو بنویسین.
مرسی!
 
  • شروع کننده موضوع
  • #2

sara.a1999

کاربر فعال
ارسال‌ها
70
امتیاز
56
نام مرکز سمپاد
دبیرستان فرزانگان 1
شهر
تهران
مدال المپیاد
یک کوله بار عشق به ریاضی-برنز 95
پاسخ : سوالات مرحله 2 سال 94

سوال 5.
بیاید یک راه حل با استقرا ارائه بدیم.
 

Fliqpy

کاربر نیمه‌حرفه‌ای
ارسال‌ها
181
امتیاز
303
نام مرکز سمپاد
غیر انتفاعی علامه حلی 3
شهر
تهران
مدال المپیاد
هر جوری حساب میکنم افتخار نمیکنم بهش
دانشگاه
شريف
رشته دانشگاه
نرم افزار
پاسخ : سوالات مرحله 2 سال 94

به اين راه حل توسط مصححين دوره،با اعتراض نمره كامل داده شده:
با استقرا حكم قويتري رو ثابت ميكنيم: فرض كنيد بجاي اين كه كمان هامون 1تا n+1 باشن، كمان هامون شامل حداقل يك كمان به طول يك و حداقل سك كمان به طول حداقل n+1 باشه. بديهيه كه حكم مساله رو نتيجه ميده و حالت n=1 هم درسته.
فرض كنيد براي n=k درسته براي n=k+1 ثابت ميكنيم.
دقت كنين كه يك كمان به طول يك داريم و فرض خلف كنين كه هيچ كماني شامل كمان ديگه اي نيست. ميشه مثل راه حل هاي اصلي دو طرف اين كمان رو باز كرد و به يه پاره خط به طول 2n-1 تبديل كرد. نقاط روي اين پاره خط رو از ٠ تا 2n-1 شماره گذاري كنيد از چپ به راست و فرض كنيد منظورمون از آغاز يك كمان، نقطه سمت چپ و از پايان، نقطه سمت راست يك كمانه. يعني مثلا صفر ممكنه آغاز يك كمان باشه ولي پايان هيچ كماني نيست.
حالا دقت كنين اگه آغاز يك كمان صفر و پايان اون 2n-1 باشه حكم مساله بديهيه. چون كه n حداقل دو هست و در نتيجه غير از كمان به طول يك و 2n-1 كمان ديگه اي هم هست پس تو 2n-1 ميفته. همچنين دقت كنين اگه يه نقطه آغاز دو تا كمان باشه ، كماني كه كوچكتر نيست شامل كمانيه كه بزرگتر نيست و اين تناقضه، به طريق مشابه هيچ نقطه اي پايان دو تا كمان هم نيست.
حالا دقت كنين كه يكي از كمانايي كه طولش حداقل n+1 هست رو اگه در نظر بگيريد، نميشه هم آغازش صفر باشه هم پايانش 2n-1. پس حداقل يكي از صفر و 2n-1 از دو سرش نيست، بنا به تقارن 2n-1. حالا چون 2n-1 انتهاي حداكثر يك كمانه، ميشه بازه 2n-1 تا 2n-2 و همه كمانهايي كه باهاش اشتراك به طول ناصفر دارن رو حذف كرد و حداكثر يه كمان حذف شه(اگه هيچ كماني حذف نشد يه كمان دلخواه بجز كماني كه قبلا بهش اشاره كرديم و طولش حداقل n+1 هست رو حذف كنين) پس الان يه خط از ٠ تا 2n-2 داريم كه شامل دقيقا n-1 كمانه كه طول يكيشون حداقل n+1 هستش. دقت كنين اگه تو اين مجموعه يه كمان بيابيم كه شامل يكي ديگس حكممون اثبات ميشه چرا كه تو مجموعه قبلي هم اين كمانا وجود داشتن.
حالا دقت كنين كه اين كمانا مجموعا 2n-2 تا سر و ته دارن. و در مجموع 2n-2 تا بازه داريم . پس يا يه بازه خالي ميمونه يا تو هر بازه حداقل يه سر هست(ميگيم يه سر توي يه بازه س اگر اون سر آغاز باشه و سمت چپ بازه يا پايان باشه و سمت راست بازه، بديهيه كه هر سر تو دقيقا يك بازه س)
اگه يه بازه خالي باشه مثلا بازه i تا i+1 كافيه دو سر بازه رو به هم بچسبونيم. بديهتا با اين كار هيچ تغييري تو شامل شدن كمانها به وجود نمياد و كماني حذف نميشه پس به يه خط به طول 2n-3 با n-1 كمان داريم . همچنين كماني كه قبلا طولش n+1 بود طولش حداكثر يه واحد كم ميشه، پس طولش ميشه حداقل n ولي دقت كنين كه چنين مجموعه اي شرايط فرض استقرا رو داره پس شامل يه بازه س كه شامل يه بازه ديگه س كه اين دو تا بازه قبل از تغييراتي كه ما ايجاد ميكرديم هم بودن كه تناقضه.
براي حالتي كه هر بازه شامل دقيقا يه سرهدقت كنين كه اولين بازه سمت چپ شامل يه آغاز و آخرين بازه سمت راست شامل يه پايانه. پس طبق پيوستگي گسسته دو بازه متوالي هستن كه بازه سمت چپ شامل يه آغاز و بازه سمت راست شامل يه پايانه، مثل i,i+1,i+2 پس كافيه نقطه i+1 رو حذف كنين و ببينين باقيش مثل حالت ديگس.
 
  • شروع کننده موضوع
  • #4

sara.a1999

کاربر فعال
ارسال‌ها
70
امتیاز
56
نام مرکز سمپاد
دبیرستان فرزانگان 1
شهر
تهران
مدال المپیاد
یک کوله بار عشق به ریاضی-برنز 95
پاسخ : سوالات مرحله 2 سال 94

سوال 3.
راه حل غیر راه باشگاه (مسلما!) ارائه بدید.
یک راه عمود کردن از P به AB و استفاده از یک لم در مثلث های PBC , PH2B, PH1C.
سوال 2 خیلی جالب میشه اگر کسی راه دیگه ای داشته باشه!
 
بالا