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

[sara.a1999]

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

 

[sara.a1999]

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

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

 

[Fliqpy]

پاسخ : سوالات مرحله 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 رو حذف كنين و ببينين باقيش مثل حالت ديگس.

 

[sara.a1999]

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

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