• اگر سمپادی هستی همین الان عضو شو :
    ثبت نام عضویت

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

ghazal.k

کاربر نیمه‌حرفه‌ای
ارسال‌ها
241
امتیاز
208
نام مرکز سمپاد
فرزانگان
شهر
شیراز
مدال المپیاد
کامپیوتر ریاضی نجوم
پاسخ : استقرا

به نقل از mahtab.f :
من نفهمیدم چرا کامل نیست ؟ من اثبات کردم که غلته
درباره این سوال هم خوندم تا یه راه دیگه پیدا کنم توی یه کتاب یکی از راه حل هایی که واسش گفته همینه :-?

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

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

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

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

zahra.k

کاربر فعال
ارسال‌ها
22
امتیاز
66
نام مرکز سمپاد
فرزانگان 1
شهر
همدان
پاسخ : استقرا

به نقل از کیارش :
این واسه نقض کردنش کافیه که! برای اثبات کردن اینکه می تونه شرط لازمه ولی کافی نیست!
یه سؤال: آخرش باید برگرده به خونه ای که ازش شروع کرده؟
خوب ما كه نميخوايم واسه همه اعداد بگيم كه كافي نباشه
فقط واسه يه جدول خواسته سوال
به نقل از ghazal.k :
اثبات کردین چی غلطه؟! :D

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

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

من گفتم تو اثبات كه همشو ننوشتم
بايد طرز چرخيدن اسب تو خونه ها رو با اون چيزا ك من گفتم بفهميد بقيش هم همون جوريه ك من ديگه ننوشتمش
 
  • شروع کننده موضوع
  • #123

mahtab.f

کاربر نیمه‌حرفه‌ای
ارسال‌ها
206
امتیاز
1,413
نام مرکز سمپاد
دبیرستان فرزانگان 1 تهران
دانشگاه
امیرکبیر
رشته دانشگاه
مهندسی کامپیوتر - سخت افزار
پاسخ : استقرا

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

ghazal.k

کاربر نیمه‌حرفه‌ای
ارسال‌ها
241
امتیاز
208
نام مرکز سمپاد
فرزانگان
شهر
شیراز
مدال المپیاد
کامپیوتر ریاضی نجوم
پاسخ : استقرا

:-\

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

zahra.k

کاربر فعال
ارسال‌ها
22
امتیاز
66
نام مرکز سمپاد
فرزانگان 1
شهر
همدان
پاسخ : استقرا

به نقل از mahtab.f :
نه درسته ببخشید
من فک کردم اولش که قراره برگرده :-"
ولی تو 49*49 درسته دیگه نه ؟ :-?

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

zahra.k

کاربر فعال
ارسال‌ها
22
امتیاز
66
نام مرکز سمپاد
فرزانگان 1
شهر
همدان
پاسخ : سوالات ترکیبیات

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

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

mahtab.f

کاربر نیمه‌حرفه‌ای
ارسال‌ها
206
امتیاز
1,413
نام مرکز سمپاد
دبیرستان فرزانگان 1 تهران
دانشگاه
امیرکبیر
رشته دانشگاه
مهندسی کامپیوتر - سخت افزار
پاسخ : استقرا

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

informatic

کاربر فوق‌فعال
ارسال‌ها
109
امتیاز
1,178
نام مرکز سمپاد
شهيد سلطانی
شهر
کرج
مدال المپیاد
کامپیوتر و قبولی مرحله 2 ! (~ناکامی در m3 !!!)
پاسخ : استقرا

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

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


فرض کنید
gif.latex
عددی طبیعی باشد . یک مجموعه از افراد را
gif.latex
متعادل می‌نامیم ، اگر در بین هر 3 نفر ، دو نفر وجود داشته باشند کـه یکدیگر را بشناسند و در بین هر
gif.latex
نفر ، دو نفر وجود داشته باشند کــه یکـــدیگر را نشناسند . ثابت کنید یک مجموعه‌ی
gif.latex
متعادل ، حداکثر
gif.latex
عضو دارد .
 

informatic

کاربر فوق‌فعال
ارسال‌ها
109
امتیاز
1,178
نام مرکز سمپاد
شهيد سلطانی
شهر
کرج
مدال المپیاد
کامپیوتر و قبولی مرحله 2 ! (~ناکامی در m3 !!!)
پاسخ : سوالات ترکیبیات

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

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

فرض کنید یه مربع به ضلع ِ 1 داریم . روی این مربع
gif.latex
لَـکــه مشــاهده میشــه !!! (شکل ِ لکــه هـا هم اصلا مهم نیست !!!) ... می‌دانیم مساحت هر لکــه از 1 کمتر است و مجموع ِ مساحت‌هــای این
gif.latex
لکــه از
gif.latex
بیشتر است . ثابت کنید نقطـــه‌ای درونِ این مربع وجود دارد کــه اون نقطــه در همــه‌ی لکـــه‌هـا وجــود دارد .
 

informatic

کاربر فوق‌فعال
ارسال‌ها
109
امتیاز
1,178
نام مرکز سمپاد
شهيد سلطانی
شهر
کرج
مدال المپیاد
کامپیوتر و قبولی مرحله 2 ! (~ناکامی در m3 !!!)
پاسخ : سوالات ترکیبیات

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


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

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

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

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

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

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

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

informatic

کاربر فوق‌فعال
ارسال‌ها
109
امتیاز
1,178
نام مرکز سمپاد
شهيد سلطانی
شهر
کرج
مدال المپیاد
کامپیوتر و قبولی مرحله 2 ! (~ناکامی در m3 !!!)
پاسخ : سوالات ترکیبیات

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


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

×××

فرض کــنید مساحتِ
gif.latex
مین لکـــه برابرِ
gif.latex
باشد ... پس طبق فرضِ مسئلـــه داریم :
gif.latex
و
gif.latex


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


gif.latex


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

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


×××


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

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

پ.ن.1 : ...
 
  • شروع کننده موضوع
  • #132

mahtab.f

کاربر نیمه‌حرفه‌ای
ارسال‌ها
206
امتیاز
1,413
نام مرکز سمپاد
دبیرستان فرزانگان 1 تهران
دانشگاه
امیرکبیر
رشته دانشگاه
مهندسی کامپیوتر - سخت افزار
پاسخ : سوالات ترکیبیات

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

informatic

کاربر فوق‌فعال
ارسال‌ها
109
امتیاز
1,178
نام مرکز سمپاد
شهيد سلطانی
شهر
کرج
مدال المپیاد
کامپیوتر و قبولی مرحله 2 ! (~ناکامی در m3 !!!)
پاسخ : استقرا

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

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


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

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

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

عمو ژپتو

کاربر خاک‌انجمن‌خورده
ارسال‌ها
1,710
امتیاز
5,695
نام مرکز سمپاد
علامه حلی 1
شهر
کرمان
سال فارغ التحصیلی
93
مدال المپیاد
قبولی در مرحله دوم المپیاد کامپیوتر
دانشگاه
شهید باهنر کرمان / شریف
رشته دانشگاه
ریاضی :x
پاسخ : استقرا

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

rezaezio

کاربر فوق‌حرفه‌ای
ارسال‌ها
1,167
امتیاز
1,956
نام مرکز سمپاد
حلّیِ 2
شهر
تهران
مدال المپیاد
برنز و طلای کامپیوتر !
دانشگاه
شریف
رشته دانشگاه
نرم افزار
پاسخ : استقرا

لم : هر نفر حداکثـــر n نفر را نمی‌شناسد .... فرض کنید فردی وجود داشته باشد که حداقل n+1 نفر را نمیشناسد ... در این صورت باید یک زیرگراف کامل n راسی وجود داشته باشد که مخالف فرض مسئلــه‌ست ...
بنده فکر می کنم لم شما اشتباه باشه زیرا :
فرض می کنیم فردی باشه که n نفر رو نشناسه در نتیجه در بین این n نفر ، 2 نفر هستند که همدیگرو نمیشناسند (طبق فرض سوال)
پس خود فرد + این دو نفر میشن : 3 نفر که هیچ کدوم 2 نفر دیگه گروه رو نمیشناسن ( نقض ) ؛ خوب اینجا به تناقض می رسیم :|

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

informatic

کاربر فوق‌فعال
ارسال‌ها
109
امتیاز
1,178
نام مرکز سمپاد
شهيد سلطانی
شهر
کرج
مدال المپیاد
کامپیوتر و قبولی مرحله 2 ! (~ناکامی در m3 !!!)
پاسخ : استقرا

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

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

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

rezaezio

کاربر فوق‌حرفه‌ای
ارسال‌ها
1,167
امتیاز
1,956
نام مرکز سمپاد
حلّیِ 2
شهر
تهران
مدال المپیاد
برنز و طلای کامپیوتر !
دانشگاه
شریف
رشته دانشگاه
نرم افزار
پاسخ : استقرا

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

نـــزدم که :| شما سرور ما هستی x: :D

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

عمو ژپتو

کاربر خاک‌انجمن‌خورده
ارسال‌ها
1,710
امتیاز
5,695
نام مرکز سمپاد
علامه حلی 1
شهر
کرمان
سال فارغ التحصیلی
93
مدال المپیاد
قبولی در مرحله دوم المپیاد کامپیوتر
دانشگاه
شهید باهنر کرمان / شریف
رشته دانشگاه
ریاضی :x
پاسخ : استقرا

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

informatic

کاربر فوق‌فعال
ارسال‌ها
109
امتیاز
1,178
نام مرکز سمپاد
شهيد سلطانی
شهر
کرج
مدال المپیاد
کامپیوتر و قبولی مرحله 2 ! (~ناکامی در m3 !!!)
پاسخ : استقرا

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

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

gif.latex
ــــــه !!!!




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

به نقل از |H|3$4|M| :
ســـوالِ بعـــدی :

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

Dark Eagle

کاربر حرفه‌ای
ارسال‌ها
403
امتیاز
657
نام مرکز سمپاد
helli 2
شهر
Tehran
مدال المپیاد
کامپیوتر
پاسخ : استقرا

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