تعداد توپ های کاسه ی اول را i , و دوم را j بنامید میخواهم اثبات کنم که اگه i+j باقیماندش بر 4 برابر 0 یا 1 بود نفر اول و در غیر اینصورت نفر دوم میبرد

استقرای قوی میزنیم روی i+j

i+j)%4==k)

خوب در این صورت هر حرکتی انجام بدیم که البته (نباید حرت هایی انجام بدیم که به صورت (1,m) و (2وm) باشد چون این حالات باعث برد طرف مقابل است (استثناء))

2-i+j)%4==k)

که میشه حالت مقابل طبق فرض استقرا

از آنجا که ما در استقرایی که استفاده کردیم از 2 جمله قبل استفاده کردیم میخواهیم پایه استقرا را حساب کنیم فقط باید حواسمان باشد در حرکات اول زیاد پایه خوب نیست پس پایه را تا 8 مینویسیم(ماتریکس 8*8)

میبینیم برای i>2 و j>2 حرفی که زده بودیم درست است (اثبات پایه استقرا پایین صفحه)

خوب ما این را اثبات کردیم که برای i>2 و j>2 اگر i+j %4 ==1|| 0

نفر اول میبرد خوب در شرط مسئله i=100 و j=100 پس i+j%4==0

پس نفر اول میبرد

پایین صفحه(اثبات پایه):

در این ماتریس اگه در نقطه ی سیاه باشیم و یکی از نقاط قرمز باخت باشن میبریم و در غیر این صورت اگر همه ی نقاط قرمز برد باشن میبازیم(چرا؟) پس میتوانیم ماتریس را بسازیم .

کد:

ساختن ماتریکس:

http://paste.ubuntu.com/9688608/

استقرا میزنیم و میگیم که برای هر k ای که کمتر از n باشه و بزرگتر مساوی با 2 باشه اگه توی یک ظرف k تا توپ باشه و توی اون یکی هم k تا اگه k بخش پذیر بر 2 باشه نفر اول میبره و اگه بخش پذیر بر دو نباشه و باقیمانده 1 بیاره نفر دوم میبره

پایه : برای k == 2 که بدیهیه نفر اول میبره از یکی از ظرف ها دوتا برمیداره . برای k == 3 هم باز بدیهیه اگه نفر اول دوتا از یکی برداره اون یکی هم میتونه از هر دوتا یدونه برداره و یکی از ظرف ها خالی بشه اینجوری و اگه از جفتش یدونه برداره هم میتونه اون از یکی دوتا برداره و برنده بشه.

گام: خب حالا اگه n زوج باشه ما از هر جفتش یدونه برمیداریم تا n بشه n-1 و فرد بشه و ما هم که الان شدیم نفر دوم و طبق فرض برده برنده

اگه هم n فرد باشه اگه نفر اول دوتا برداشت از یکی از ظرف ها ما هم ازون یکی ظرفه دوتا برمیداریم تا همچنان n فرد باشه و طبق فرض چون ما نفر دومیم برنده بشیم و اگه هم که از جتفش یدونه برداشت ما هم از جفتش یدونه برمیداریم تا باز نفر دوم باشیم و n هم فرد و ما برنده

چون 100 زوج هست پس نفر اول میبره!

با استفاده از استراتژی زوجیت هم می توان این مسئله را حل کرد. در صورتی که بازی کن اول 2 توپ از یک کاسه بردارد 98 توپ می ماند اگر بازی کن دوم دو توپ بردار باز هم بازی زوج می شود و به نفع بازی کن اول اما اگر یکی از آن و یکی از این کاسه بردارد تعداد فرد میشود آن وقت در حرکت بعدی بازی کن اول برای حفظ موقعیتش باید استراتژی تکرار را به کار برده و باز هم تعداد توپ های کاسه را زوج کند پس در این حالت که تعداد توپ ها از آغاز زوج بوده بازی کن اول استراتژی برد دارد. امیدوارم درست اثبات کرده باشم اگر ایراد دارد لطفا تصحیح کنید نه بد رفتاری