جواب های قشنگ!!!

ابتدا به خانه ها وزن مى دهیم وزن خانهِ اى برابر (F(i است(که (F(i تابع فیبوناچی هست) 
متغیر W را مجموع وزن ها تعریف میکنم !
ثابت میکنم که W همواره ثابت است و برابرِ سیگما F(i) i=0 تا i=n
در حرکتِ نوع اول که بدیهى است که ثابت میماند چون تعریف فیبوناچی است

F(i)=F(i-1)+F(i-2)l

در حرکتِ دوم کافیست ثابت کنیم که

2F(i)=F(i-2)+F(i+1)l
از طرف چپ شروع میکنیم !

2F(i)=F(i)+F(i)=[F(i+1)-F(i-1)]+[F(i-1)+F(i-2)]=F(i+1)+F(i-2) :D
خوب پس W همواره ثابت است !

حالا که ثابت کردیم W ثابت است کافیست ثابت کنیم که

sigma F(i)i=0 ta i=n

استقرا میزنیم روى n براى n=۰ که بدیهى است !
حالا از t=>t+1
میدانیم 

 sigma F(i) i=0 ta i=t

به طرفین معادله (F(t+۱ اضافه میکنیم و اثبات می شود! 
پس هیچ وقت مهره ای در خانهِ n+۲ قرار نمیگیرد چون مجموع تغییر خواهد کرد !

۲-------------------->

اگر گراف لوپ (یالی که دو سر آن یک راس باشد ، یا دوری به طول یک) یا یالهای موازی(دو یال که دو راس های مجاور مشترک دارند یا دوری به طول 2) داشته باشد که دوری که طول آن بر 3 بخشپذیر نباشد را یافته ایم ، پس فرض کنیم گراف ساده است.مسیر ماکسیمالی در گراف که راسaیک انتهای آن است را در نظر می گیریم.aباید حداقل با دو راس دیگر به جز راس مجاورش در مسیر ماکسیمال همسایه باشد زیرا مسیر ماکسیمال است و مسیر نمی تواند از طرفaبزرگ شود ، این دو راس را به ترتیب از طرفaبه انتهای دیگر گراف ،xوyمی نامیم . سه دور را در نظر می گیریم، دوری که شامل مسیرaxویالaxمی باشد ، دوری که شامل مسیرxy و دو یالay وaxاست .و دوری که شامل مسیرayو یالayاست. فرض کنیم که طول دور اولی بر 3 بخشپذیر باشد پس طول مسیرaxبرابر3k-1است.همچنین فرض کنیم طول دور سوم نیز برابر3k*است ، پس طول مسیرxy برابر3k*-2است . طول مسیرayبرابر است با مجموع طول این دو مسیر ، پس بر 3 بخشپذیر است ، پس طول دوری که شامل مسیر و یالayاست بر 3 بخشپذیر نیست (برابر3i+1است )پس چنین دوری در گراف وجود دارد.

۳----------------->
به صورتِ دلخواه یال ها را جهت دار می کنیم چون زوج یال داریم میتوانیم بگوییم که زوج راس داریم که درجهِ خروجی آنها فرد است چون سیگما درجه خروجی انها برابرِ تعداد یال هاست
حالا ۲ راس را در نظر میگیریم که درجهِ خروجی ان ها فرد است چون گراف همبند است پس مسیرى بین این ۲ راس وجود دارد (نه لزوما جهت دار)
تمام جهت هاى یال های این مسیر را بر عکس میکنیم ! 
راس هایی که در وسط مسیر هستند که زوجیت درجه خروجی شان تغییر نمى کند(بدیهى است خود تون اثبات کنین)
۲ رأس انتهایی هم تغییر می کند یعنى از فرد تبدیل به زوج میشوند !
پس هر مرحله ۲ تا از راس هاى بد تبدیل به خوب می شوند و چون تعداد آنها زوج تا است زمانى تعداد راس های بد ۰ میشود.
۴--------------------->

ثابت میکنم که یک بازه سفید وجود درِ که همه سیاه ها را در بر می گیرد و براى سیاه ها هم به طورِ مشابه است (فقط جاى سیاه و سفید عوض میشود)
اولین بازه ی سیاه که بسته میشود و آخرین بازه ی سیاهى که شروع میشود را در نظر بگیرین!
چون این ۲ تا بازه هر کدام با k تا بازه ی سفید اشتراک دارند پس یک بازه هست که با جفت بازه هاى در نظر گرفته شده اشتراک دارد(این را انتخاب میکنیم). اگر همچین بازه ای نباشه باید حداقل 2*k بازه سفید داشته باشیم !
ثابت میکنیم بازه ای که انتخاب کردیم با همه بازه هاى سیاه اشتراک دارد!
بدیهى است که همه بازه ها یک نقطه بین اولین پایان و آخرین شروع را دارد اگر نداشته باشد این ۲ نقطه تغییر میکند !(اثباتش به عهدۀ خود تون دیگه خیلى بدیهیه)

۵------------------>

الف)
جعبه با بزرگترین سیب را بر میداریم و سپس بر اساسِ تعداد سیب ها جعبه ها را مرتب میکنیم !
حالا فرض کنید جعبه ی شماره ۱ کمترین سیب را دارد و به ترتیب تا ۹۸   تعداد سیب ها افزایش مى یابد !
جعبه ها را دست بندى میکنیم و جعبه ی 2*i و1+ ( 2*i)  را در یک بسته میگذریم !
حالا ۴۹ بسته داریم و میخواهیم ۴۹ جعبه انتخاب کنیم!
از هر بسته جعبه ای را انتخاب میکنم که بیشترین پرتقال را دارد!
این یک جعبه بر داشتن خوب هستش چون بدیهى است بیشتر از نصف پرتقال ها را dadad و در بد ترین حالت جعبه ۱،۳،۵،۹۷ انتخاب شده به همراه 99!
که چون ۹۹ بیشتر از ۹۸ ، سیب دارد و ۹۷>۹۶ ،۹۵>۹۴ ،….. ۳>۲ و ۱>=1
پس نصف سیب ها برداشتِ شده’اند!
ب) به شکل بالا بر میداریم اما این بر بعد از بر داشتن جعبه با بیشترین سیب دست ها را ۳ تایى در نظر میگیریم و در هسته جعبه با بیشترین پرتقال را بر میداریم !
باز هم درست میشود!

J)ابتدا جعبه با بیشترین سیب را بر میدارم و سپس جعبه با بیشترین پرتقال !
حالا ۹۸ جعبه دارم و میخواهم ۴۹ جعبه بر دارم!
A=بیش ترین سیب B=بیش ترین  پرتقال !
خوب میام میگم اگه من بتونم جعبه ها رو ۲ دسته بکنم که اختلافِ سیب هاى ۲ طرف کوچیک تر مساوىِAباشد و اختلافِ پرتقال این دست کم تر مساوىِ Bباشد مسأله حل است!
چون اون دسته با بیشترین موز رو بر میداریم و با اون ۲ تا جعبه !
موز ها که بیشترن و سیب ها هم بیشترن چون در بد ترین حالت  ما کمترین سیب رو بر میداریم که چون اختلافشون از A کمترِه با اون آمدنِ جعبه با بیشترین سیب جبران میشه و براى پرتقال ها هم همین طور!
از این به بعد a_i میشه سیب جعبه i و b_i میشه پرتقال  جعبه i.
پس کافیه ثابت کنیم اگر 2x جعبه داشته باشیم و میخواهیم x جعبه انتخاب کنیم که همه a_i ها ازA  کوچیکترند وb_i ها از B کوچیکترند میتوان دستi ها را به ۲ قسمت تقسیم کرد که اختلافِ سیب ها حد اکثر A باشد و پرتقال ها B باشد !
این حکم را با استقرا ثابت میکنیم
استقرا میزنیم روى که. از که به k+۲ میرسیم!
همین !
استقرا به عهدۀ خودتون( خیلى هم بدیهى نیست پس یه کم فکر کنید ،نگید چون نگفته خیلى بدیهیه )

۶----------------------------->

مسأله را با استقرا روى تعداد یال ها حل میکنیم

پایه استقرا( m=2 تعداد یالها)
چون گراف همبند است پس میتوانیم بگوییم که خود گراف حداکثر ۳ راس دارد و کمتر هم ندارد! خود گراف P-۳ است
فرض استقرا :گرافی با زوج یال و همبند را میتوان به P-۳ افراز کرد!
گام استقرا:m==>m+2
مسیرِ ماکسیمم را در نظر میگیریم !
فرض کنید که راس ها به ترتیب در مسیر a1,a2،….،ax باشد (به بدیهیت x>=۳ است زیرا اگر کمتر باشد آنگاه بزرگترین مسیر به طول ۱ است و چون گراف همبند است پس گراف حداکثر ۲ راس دارد و گراف میتوانند حداکثر ۱ یال داشته باشد !)

1)اگر a2 همسایه به غیر از a1 و a3 داشته باشد آنگاه اون راس را u مینامیم
ثابت میکنم اگر ما یال (a1-a2) و (a2- u) را بر داریم گراف هنوز همبند خواهد ماند!( در اینجا تعریف از همبندی بدون در نظر گرفتن راس های درجه ۰ است)
اگر درجهِ a1 صفر شود که مشکلى نیست و با تعریف همبندى تناقص ندارد!
اما اگر درجه یه a1 بیشتر از صفر باشد آنگاه میدانیم تمام همسایه هاى a1 در مسیر هستند چون اگر همسایه ای بیرون از مسیر داشته باشد میتوانیم طول مسیر را افزایش بدیم که با ماکسیمم بودنش تناقص دارد!
پس هنوز a1 به a2 مسیر دارد چون اگر a1 به یک راسى مثل at برود و سپس به a_t-1 سپس به a_t-2 ...
به a2 میرسد.
براى رأس u هم همین اثبات کافیست چون رأس u اگر ۰ شود که با تعریف همبندی تناقص ندارد اگر هم همسایه داشته باشد باز هم همسایه هایش در مسیر هستند چون اگر نباشند آنگاه مسیر ماکسیمم نبوده !

2)اگر a2 همسایه ای به غیر از a1 و a3 نداشته باشد مسیر a1-a2-a3 را حذف میکنیم. a2 که درجه ۰ میگیرد ،a3 هم که به مسیر وصل است.
فقط مى ماند a1:
اگر درجهِ a1 صفر شود که حله
اگر هم ۰ نشود آنگاه همسایه در مسیر دارد که باز هم گراف همبند مى ماند!

پس گراف هم چنان همبند است و m یال دارد ! (طبق فرض استقرا مسأله حل است)