بحث پیرامون حل مسئله دوم مرحله دو ششمین المپیاد کامپیوتر - سال 1375

pooya.1999

New Member
ارسال ها
119
لایک ها
46
امتیاز
0
#1
سلام دوستان،داشتم سوالاتو نگاه می کردم که به این مسئله بر خوردم.خودم یه یه ساعتی بهش فکر کردم؛یه چندتا ایده پیدا کردم ولی زیاد به کارم نیومده.برای همین شما هم بیاید ببینید ایده ای به نظرتون میاد.

خواهشا هرگز راه حل کامل این مسئله رو ننویسید.بعد از جمع بندی ایده ها مسئله رو کامل حل کنیم بهتره شاید یکی (از جمله من) بخواد خودش مسئله رو حل کنه.

صورت مسئله:

A و B دو مجموعه متناهی و جدا از هم از اعداد صحیح اند بطوریکه به ازای هر x عضو
یا x+1 عضو A است یا x-2 عضو B.ثابت کنید |A| = 2|B|.
 

sa1378

New Member
ارسال ها
1,403
لایک ها
1,077
امتیاز
0
#2
پاسخ : بحث پیرامون حل مسئله دوم مرحله دو ششمین المپیاد کامپیوتر - سال 1375

استقرای ضعیف روی تعداد اعضای b
 
آخرین ویرایش توسط مدیر

TheOverlord

New Member
ارسال ها
159
لایک ها
282
امتیاز
0
#3
پاسخ : بحث پیرامون حل مسئله دوم مرحله دو ششمین المپیاد کامپیوتر - سال 1375

اين مساله تعميم داره كه در مسابقه BWM آلمان هم اومده:
فرض كنيد
دو مجموعه متناهي باشند و
بطوري كه براي هر
يا
يا

ثابت كنيد :
 

pooya.1999

New Member
ارسال ها
119
لایک ها
46
امتیاز
0
#4
پاسخ : بحث پیرامون حل مسئله دوم مرحله دو ششمین المپیاد کامپیوتر - سال 1375

بله منم ایده استقرا رو فهمیدم چون غیر از استقرا،اگه بخوایم مسئله رو با استدلال پله ای و مرحله به مرحله پیش ببریم واقعا سخت میشه.

ولی متاسفانه نتیجه گرفتن حکم به ازای k+1 از k اونقدر ها هم آسون نیست.

اين مساله تعميم داره كه در مسابقه BWM آلمان هم اومده:
فرض كنيد
دو مجموعه متناهي باشند و
بطوري كه براي هر
يا
يا


ثابت كنيد :
تعمیم زیباییه.ممنون.
مطمئنا بعد از حل این مسئله سعی می کنم اونو حل کنم.
 

sa1378

New Member
ارسال ها
1,403
لایک ها
1,077
امتیاز
0
#5
پاسخ : بحث پیرامون حل مسئله دوم مرحله دو ششمین المپیاد کامپیوتر - سال 1375

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

pooya.1999

New Member
ارسال ها
119
لایک ها
46
امتیاز
0
#6
پاسخ : بحث پیرامون حل مسئله دوم مرحله دو ششمین المپیاد کامپیوتر - سال 1375

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

توجه داشته باشید که ترکیبیات المپیاد کامپیوتر قوی تر از ترکیبیات المپیاد ریاضیه،ایده دیگه ای سراغ ندارید؟

ما یه عضو دیگه ای رو به b اضافه می کنیم حالا باید نتیجه بگیریم باید دو تا عضو به a اضافه کنیم؛من احتمالات گوناگون برای این عضو جدید رو تا سه چهار مرحله رفتم چیزی دستگیرم نشد.
 

sa1378

New Member
ارسال ها
1,403
لایک ها
1,077
امتیاز
0
#7
پاسخ : بحث پیرامون حل مسئله دوم مرحله دو ششمین المپیاد کامپیوتر - سال 1375

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

توجه داشته باشید که ترکیبیات المپیاد کامپیوتر قوی تر از ترکیبیات المپیاد ریاضیه،ایده دیگه ای سراغ ندارید؟

ما یه عضو دیگه ای رو به b اضافه می کنیم حالا باید نتیجه بگیریم باید دو تا عضو به a اضافه کنیم؛من احتمالات گوناگون برای این عضو جدید رو تا سه چهار مرحله رفتم چیزی دستگیرم نشد.
باید کوچکترین عضو مجموعه b رو بگیرین...
بعد اینو با دوتا عضو از a رو حذف کنین(باید فکر کنین که چجوری حذف کنین)
بعد بیاین بگین اگه اینا رو حذف کنیم هنوز شرط مسئله برقراره(اینم باید فکر کنین چجوری بگین که هنوز شرط برقراره)
پس حکم اثبات میشه
 
بالا