**

حل بخش الف)

(ویرایش شد و پاسخ کامل شد)

لم 1) اول ثابت می کنم اگه k>1 باشه به ازای هیچ n فردی این بازی تموم نمیشه: تمام مهره های ورودی و خروجی به تمام نفرات رو در 2 دور اول در نظر می گیریم. در دور اول به تمام نفرات زوج یک مهره اضافه می شود و از تمام نفرات فرد به جز شماره 1 یک مهره کم می شود. در دور دوم چون n فرد بوده نفر شماره 1 باید 2 مهره به نفر بعد بدهد بنابراین جای این اضافه و کم شدن ها عوض میشه و به تمام نفرات فرد به جز شماره 1 یک مهره اضافه می شود و از تمام نفرات زوج یک مهره کم می شود. بنابراین در یک دور بینهایت می افتیم. در ضمن چون k>1 هیچ شخصی از دور مسابقه بیرون نمیره چون همه در هر حالت حداقل 1 مهره دارند.

لم 2) حالا ثابت می کنم که اگه k>1 باشه به ازای هر n زوجی بعد از چند دور بازی n نصف و k دو برابر میشه: در هر دور چون نفرات فرد باید 1 مهره به نفر بعد بدهند و نفرات زوج باید 2 مهره به نفرات بعدی بدهند پس همواره مهره های نفرات فرد زیاد و مهره های نفرات زوج کم میشود. بنابراین بعد از k دور بازی تمام نفرات زوج کنار می روند و تعداد نفرات بازی نصف و k دو برابر می شود.

3) اولا بنا بر لم 1 n باید زوج باشد. ثانیا بنابر لم 2 و لم 1، n/2 باید زوج باشد تا با هر بار کم شدن تعداد نفرات هنوز امکان پایان بازی برقرار باشد(وقتی k>1 پس k*2>1). پس n باید توانی از 2 باشد تا بازی تمام شود.

دیگه حال فکر کردن رو بخش ب نیست. نصف شبه.

خوش باشین. شب خوش.

پ.ن.: ببخشید دیگه نصف شب بود خیلی حواسم جمع نبود. الان اثبات رو کامل می کنم. بنابر استدلالات لم 2 در هر دور، نفراتی که شماره زوج دارند حذف می شوند. چون نفر اول هیچ وقت حذف نمی شود و همواره شماره اش 1 است پس در نهایت او باقی می ماند.

خوش باشین.