المپیاد سوالات ترکیبیات و مباحث ویژه !

[ghazal.k]

پاسخ : استقرا

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

×کیارش : نه نباید برگرده

اثبات کردین چی غلطه؟!

جواب سوال بله میشه هست!
الان شما باید اثبات کنی میشه
اونم با استقرا

بعد من به راه هر زهرا خانم گفتم که شبیه است اما کامل نیست

 

[zahra.k]

پاسخ : استقرا

این واسه نقض کردنش کافیه که! برای اثبات کردن اینکه می تونه شرط لازمه ولی کافی نیست!
یه سؤال: آخرش باید برگرده به خونه ای که ازش شروع کرده؟

خوب ما كه نميخوايم واسه همه اعداد بگيم كه كافي نباشه
فقط واسه يه جدول خواسته سوال

اثبات کردین چی غلطه؟!

جواب سوال بله میشه هست!
الان شما باید اثبات کنی میشه
اونم با استقرا

بعد من به راه هر زهرا خانم گفتم که شبیه است اما کامل نیست

من گفتم تو اثبات كه همشو ننوشتم
بايد طرز چرخيدن اسب تو خونه ها رو با اون چيزا ك من گفتم بفهميد بقيش هم همون جوريه ك من ديگه ننوشتمش

 

[mahtab.f]

پاسخ : استقرا

نه درسته ببخشید
من فک کردم اولش که قراره برگرده
ولی تو 49*49 درسته دیگه نه ؟

 

[ghazal.k]

پاسخ : استقرا

:-\

دوستان میشه یا نقل قول کنید یا تعیین کنید دارید از کی سوال میپرسید؟! #

 

[zahra.k]

پاسخ : استقرا

نه درسته ببخشید
من فک کردم اولش که قراره برگرده
ولی تو 49*49 درسته دیگه نه ؟

طبق اثبات بله امكان داره

 

[zahra.k]

پاسخ : سوالات ترکیبیات

چرا تاپيك هي ميخوابه؟؟؟
بچه ها چرا ديگه سوال نميزاريد؟؟؟
يكم فعال باشيم خو

علي الحساب يه سوال ميزارم
عدد 1996^7داده شده در هر مرحله ميتوانيم رقم يكان را با عدد باقيمانده جمع كنيم اين عمل را تا جايي ادامه ميديم ك ب يك عدد10رقمي برسيم ثابت كنيد اين عدد 2رقم برابر دارد

 

[mahtab.f]

پاسخ : استقرا

تاپیک باز خوابید
سوال قبلی رو وقتی کسی نیست که واسش ایده داشته باشه
پس بیاین یه سوال جدید بذاریم همه
× انقدر که تاپیک میخوابه واسه اینه که علاقه ی زیادی به این موضوع ندارین ایا ؟
می تونیم واسه یه مبحث جدید تاپپیک بزنیم اگه استقرا تکراری شده !

 

[informatic]

پاسخ : استقرا

سوال قبلی زیاد قشنگ نیست فکـــ کنم توی الفبا بود حَلــِـش ...

برای این کــه تاپیک نخوابــه ، فعلـا یه سوال می‌ذارم بچــه‌هـا گرم شـَـن ...


فرض کنید

عددی طبیعی باشد . یک مجموعه از افراد را

متعادل می‌نامیم ، اگر در بین هر 3 نفر ، دو نفر وجود داشته باشند کـه یکدیگر را بشناسند و در بین هر

نفر ، دو نفر وجود داشته باشند کــه یکـــدیگر را نشناسند . ثابت کنید یک مجموعه‌ی

متعادل ، حداکثر

عضو دارد .

 

[informatic]

پاسخ : سوالات ترکیبیات

سوالِ قبلــی هم میشه گفت آسونـه !!! اگـه اشتباه نکنم سوالِ استراتژی بود .... معمولـا تو این جور مسئلــه‌هــا پیمــانه‌ی 9 چیــز ِ خوبیـــه ... !!!!

یه سوالِ قشنگ ولی ســــاده !!!!!

فرض کنید یه مربع به ضلع ِ 1 داریم . روی این مربع

لَـکــه مشــاهده میشــه !!! (شکل ِ لکــه هـا هم اصلا مهم نیست !!!) ... می‌دانیم مساحت هر لکــه از 1 کمتر است و مجموع ِ مساحت‌هــای این

لکــه از

بیشتر است . ثابت کنید نقطـــه‌ای درونِ این مربع وجود دارد کــه اون نقطــه در همــه‌ی لکـــه‌هـا وجــود دارد .

 

[informatic]

پاسخ : سوالات ترکیبیات

آقــا این سوالــه خیلــی آسونــه هـــــا .... !!!! خوب یه نظری ، چیزی !؟!؟


خوب به جــای این کــه این همــه تاپیکــ ُ ایده‌هــای جدید بزنید ، خوب رو این سوالــا فِکـــ کـنید !!! ( ) (البتــه خودمَــم ، موقعــی کــه المپ میخوندم تقریبــاً اینجوری بودم !!!! ولــی کلــا سعــی کنــید تو حاشـــیه ُ اینــا نباشید !!!!! مثلــا همین تاپیکــی کــه دارین راجــع بـه برگزاری امتحانُ اینــا صحبت می‌کنید ، اصـــاً لازم نیست !!! () ... این همــه سوال ریختـــه !!! .... بشــینید حل کـنید چون تو المپیــاد کام بحثِ زمــان مطرح نیست !!! منظورم اینـــه مثلــاً تو m2 (مرحلـــه 2 !) وقتِ کـــافی دارید کــه رو مسئلــه فکر کنید !!! پس لازم نیست زیاد به دنبال امتحان دادن باشــید !!!!! (فقط چــیزی کــه راجع به امتحــان دادن مستحبــه D) اینــه کــه تو عید یا نزدیکـــای مرحلــه 2 ، امتحــانای سال گذشتــه رو از خودتون امتحـــان بگیرید !!! (اونم تــازه مستحبــه !!! یعنی میتونید همینجوری (دِیــمی !!! ) حلشون کنید !!! ولــی امتحــان دادنشون خیلــــی بهتـــره !!!)) ... فقط باید مسئلــه حل کنید !!! همین .... !)

پ.ن.0 : فکـــ کنم این حرفــا رو نبـــاید تو این تاپیکـــ میزدم !!!! ولـــــــــی مقصودم از این پست همون جملـــه‌ی اول بود ، پس به این تاپیک مربوط میشــه !!!!

پ.ن.1 : چــقد پرانتز در پرانتز شد .... !!!! :)

پ.ن.2 : الــان اینــا نصیحت شد ؟!؟! شمـــا فکـــ کنید پیشنهـــاده ...

پ.ن.3 : رو این سوال فکــ کنید ... اگــه تــا 2 روز دیگـــه حل نشد ، حلِشُ میذارم !!! بعد می‌بینید کــه چقد آسون بوده

پ.ن.4 : رو اون سوالـــی کــه تو تاپیکِ "استقـــرا" گــذاشتم فکـــ کنید !

پ.ن.5 : پــی‌نوشتِ بعــدی وجود نداره !!!

 

[informatic]

پاسخ : سوالات ترکیبیات

خیلــــی ممنون از جواب‌هــایِ مَجــــازی (!!!) کــه برای این سوال گفتید ....


خوب و امــــــا راهِ حل ِ ســوال ... !

×××

فرض کــنید مساحتِ

مین لکـــه برابرِ

باشد ... پس طبق فرضِ مسئلـــه داریم :

و

خوب حــالا یه مربعِ دیگـــه درنظر بگیرید کـــه لکـــه‌هــای روش ، متمم مربع ِ اولـــی باشـــه !!! (یعنی برای هر لکـــه ، متممِشُ در نظر بگیرید ....) حـــالا فرض کنــید در این مربعِ جدید ، مساحتِ

مین لکـــه برابرِ

باشـــه .... در این صورت داریم :

یعنــی مجموع مساحتِ لکـــه‌هـــا در مربع دومی کمتــر از 1 هست ، یعنی در مربع جــدید یک نقطــه وجود دارد کـــه در هیچ کــدام از لکــــه‌هــــا نیست !!!! و طبقِ تعریفِ این مربع ، نتیجــــه می‌گیریم کـــه در مربعِ اولــــی نقطـــه‌ای وجود داره کـــه در همــه‌ی لکـــه هـــا وجود داره ........ !!!!!!!!!!

تمــــــــــــــــام !


×××


دیدید آسون بود .... ؟!؟!؟

پ.ن.0 : لطفــــــــــاً رو سوالـــی کـــه در تاپیکِ "استقرا" گذاشتم ، فِکــــ کنـــید !!!

پ.ن.1 : ...

 

[mahtab.f]

پاسخ : سوالات ترکیبیات

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

 

[informatic]

پاسخ : استقرا

گفتم بیام جوابِ این سوالُ بنویسم ... چون احتمالا (!!!) هم فعالیتم تو این بخش کم میشه هم تو سایت !!!

بازم ممنون از ایده‌هــا و جواب‌هـای مجازیتون !!!


خوب اول یه لم ساده رو تو این مسئله اثبات میکنم ...

لم : هر نفر حداکثـــر n نفر را نمی‌شناسد .... فرض کنید فردی وجود داشته باشد که حداقل n+1 نفر را نمیشناسد ... در این صورت باید یک زیرگراف کامل n راسی وجود داشته باشد که مخالف فرض مسئلــه‌ست ...

بقیش هم آسونــه ... ! :)

 

[عمو ژپتو]

پاسخ : استقرا

حسام جان من هر چی میخونم نمیفهمم چرا
میشه یکم واضح تر بتوضیجی برادر جان

 

[rezaezio]

پاسخ : استقرا

لم : هر نفر حداکثـــر n نفر را نمی‌شناسد .... فرض کنید فردی وجود داشته باشد که حداقل n+1 نفر را نمیشناسد ... در این صورت باید یک زیرگراف کامل n راسی وجود داشته باشد که مخالف فرض مسئلــه‌ست ...

بنده فکر می کنم لم شما اشتباه باشه زیرا :
فرض می کنیم فردی باشه که n نفر رو نشناسه در نتیجه در بین این n نفر ، 2 نفر هستند که همدیگرو نمیشناسند (طبق فرض سوال)
پس خود فرد + این دو نفر میشن : 3 نفر که هیچ کدوم 2 نفر دیگه گروه رو نمیشناسن ( نقض ) ؛ خوب اینجا به تناقض می رسیم

لم درست به نظر بنده اینه : هر نفر حداکثر n-1 نفر را نمی شناسد ....

 

[informatic]

پاسخ : استقرا

بنده فکر می کنم لم شما اشتباه باشه زیرا :
فرض می کنیم فردی باشه که n نفر رو نشناسه در نتیجه در بین این n نفر ، 2 نفر هستند که همدیگرو نمیشناسند (طبق فرض سوال)
پس خود فرد + این دو نفر میشن : 3 نفر که هیچ کدوم 2 نفر دیگه گروه رو نمیشناسن ( نقض ) ؛ خوب اینجا به تناقض می رسیم

لم درست به نظر بنده اینه : هر نفر حداکثر n-1 نفر را نمی شناسد ....

خوب چـرا می‌زنید حالــا ؟!؟! من اینُ خیلــی وقت پیش حل کرده بودم ، یه همچین چیزی تو ذهنم بود .... حرفِ شمــا درستـــه !!! :)

 

[rezaezio]

پاسخ : استقرا

خوب چـرا می‌زنید حالــا ؟!؟! من اینُ خیلــی وقت پیش حل کرده بودم ، یه همچین چیزی تو ذهنم بود .... حرفِ شمــا درستـــه !!! :)

نـــزدم که شما سرور ما هستی

در حال فکر به سوال مطمئن ای که استقرا ئه ؟

 

[عمو ژپتو]

پاسخ : استقرا

یکی بیاد برا منم توضیح بده خوب

 

[informatic]

پاسخ : استقرا

ـــــه ... این سوالــه هنوز حل نشده ؟! خوب احتمالـاً 2000 بار حلـِـش کردید تا الان (!) ولــی برای خـالی نبودنِ عریضـــه (!!!) ادامــه‌ی حل رو میگم :

یک نفر رو در نظر بگیرید و اون رو A بنامید ! دوستای A رو در نظر بگیرید .... اگــه n-1 نفر از دوستای A وجود داشته باشن که همگی با هم دوست باشن ، پس این n-1 نفر با خودِ A ، یک گروه n نفری رو تشکیل میدن که همگی همدیگه رو مشناسن که خلافِ فرض مسئله است ... پس در میانِ دوستای A ، در هر n-1 نفر از اونــا ، دونفر وجود دارن که همدیگه رو نمیشناسن ، وهمچنین برای مجموعه ی دوستای A طبق فرض مسئله میدونیم که از بین هر 3 نفرشون ، دونفر هستن که همدیگه رو میشناسن .... پس میتونیم فرض استقرا رو برای دوستــای A به کار بگیریم ، یعنی تعداد دوستای A حداکثر

هستن و طبق لِمــی که قبلـا گفتم A حداکثر n-1 نفر رو نمیشناسه ، پس تعداد افراد حداکثر

ــــــه !!!!




سوالِ پایینــی هم استقـــرائـــه !!!

ســـوالِ بعـــدی :

در یک صفحــه تعداد محدودی مربع داده شده است که اضلاع آنهـــا با هم موازی هستند . برای هر k+1 تا از این مربع ها ، 2 مربع وجود دارند که نقطــه‌ای مشترک با هم دارند . ثابت کنید که 2k-1 نقطــه وجود دارد که هر یک از مربع‌هـــا حداقل شامل یکــی از آنهـــا باشد.

 

[Dark Eagle]

پاسخ : استقرا

یکی چند تا سوال بده من حل کنم