راهه تهیشونم درسته ولی من یه راه گراف هم بگم...

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

میخوایم ثابت کنیم دور فرد نداریم...و اگه دور فرد نباشه گراف دوبخشیه و یه بخشش حداقل 50 عضو داره...

لم1:دور به طول 3 نداریم.

خب بدیهیه که دور 3تایی نمتونیم داشته باشیم چون در این صورت اگه دور به صورت x1,x2,x3 باشه داریم:

x1+x2=p1, x2+x3=p2------> 2x2+x1+x3=p1+p2------> x1+x3=p1+p2-2x2

پس جمع x1,x3 گنگ میشه و شرط برقرار نیست

لم 2: فرض میکنیم دور به طول 2k+1 داشته باشیم میخوایم ثابت کنیم که در این صورت دور به طول 2k-1 هم خواهیم داشت.

خب اینم با معادله های زیر ثابت میشه:

x1+x2=p1,x2+x3=p2 ---->x1-x3=p1-p2

x3+x4=p3,x1-x3=p1-p2----->x1+x4=p1-p2+p3

پس بین x1,x4 هم یال وجود داره پس دور به طول 2k-1 به طوری که x2,x3 توش نباشن هم داریم

خب پس در آخر اگه بخوایم دور به طول فرد داشته باشیم طبق این لم باید دور به طول 3 هم حتما داشته باشیم...ولی نداریم...پس دور فرد هم کلن نداریم

این راه حلی که می خوام بگم دقیقا می شه با گراف هم پیاده سازی بشه :D منتهی نمی خوام وقتی نیاز نیست از لفظ گراف استفاده کنم :D

اول کار میایم بخش صحیح ۱۰۰ تا عددمون رو حذف می کنیم . چون به کارمون نمیان :D (خوب بعد از اینکه این کار رو انجام دادیم , واضحه که جمع دو تا عدد وقتی گنگ نیست که دقیقا قرینه ی هم باشن , یعنی جمعشون بشه صفر و وقتی گنگ هست که قرینه ی هم نباشن)

بعدش میایم ۱۰۰ تا عدد تبدیل شدمون رو می ریزیم توی لیست B,C به طوری که تعداد اعضای ‌B بیشترین مقدار ممکن باشه و C هم مکمل B هست .

B هم همون مجموعه ای هست که جمع دو به دوی اعضاش باید گنگ باشه

اگر تعداد اعضای B بزرگ تر مساوی ۵۰ بود که حکم ثابت شده و اگر نبود , نتیجه می گیریم تعداد اعضای C بزرگ تر از ۵۰ هست

حالا اتفاقی که اینجا می افته اینه که هر کدوم از اعضای C , قرینه ی حدافل یکی از اعضای B هست , چون اگر اینجوری نبود , می تونستیم اون عضو خاص C رو به B اضافه کنیم ولی طبق فرضمون , ‌B بزرگ ترین لیست ممکن هست

پس از اونجایی که جمع دو به دو ی اعضای B گنگ هست , می شه به راحتی نتیجه گرفت که جمع دو به دوی قرینه ی اعضای B هم گنگ هست ( یعنی اتفاقی که توی C می افته) , پس نتیجه می گیریم که جمع دو به دو ی اعضای C گنگ هست ولی این خلاف فرض اولمون هست ( که تعداد اعضای بزرگ ترین لیست ممکن کوچک تر از ۵۰ هست ) , از این تناقض نتیجه می گیریم که تعداد اعضای بزرگ ترین لیست ممکن بزرگ تر مساوی با ۵۰ هست ... اگر جایی رو اشتباه گفتم حتما بگین :D