قسمت اول:

لم۱: اگه اول دنباله یه سری b داشته باشیم، اونارو حذف کنیم، مراحل و ... هیچ تغییری نمی‌کنه، چون ما کلا روی ab می‌تونیم کار انجام بدیم، حالا اگه یه سری b اول کار داشته باشیم، با حذفشون هیچ یک از مراحل قابل انجام، غیرقابل انجام نمی‌شن و حرکتی رو هم اضافه نمیکنه پس کلا مهم نیستن و می‌تونیم حذفشون کنیم.

روی طول دنباله استقرا می‌زنم، اگه برابر با ۱ یا ۲ باشه رو می‌گیرم پایه و همه‌ی ۶ حالتو می‌نویسم براش تا اوکی بشه.

فرض می‌کنم برای طول $n < k $ ، مسئله پایان پذیر باشه. حالا ثابت می‌کنم برای $n=k$ نیز پایان پذیره،

اگه اول دنباله یه b باشه، که طبق لم۱ حذفش می‌کنم و فرض استقرا....

ارزش یه دنباله رو تعداد a‌هایی که اول دنباله قرار گرفتن تعریف می‌کنم.، اگه ارزش دنباله صفر باشه که میشه خط بالا.

اگه ارزش دنباله صفر نباشه، عضو ارزش‌ام دنباله رو در نظر بگیر، یا طی تعداد محدودی حداقل یکبار روش حرکت انجام می‌شه یا نمیشه، اگه بشه، این عضو با عضو بعدیش تبدیل می‌شن به bba، یعنی aهای کنار هم اول آرایه یکی کم شدن و ارزش آرایه یکی کم شد، اگه روی این کار انجام نشه، انجام شدن یا نشدن قسمت سمت راست این ربطی به این نداره و طبق فرض استقرا پایان پذیره. پس یا پایان پذیره یا طی تعداد محدودی مرحله، ارزش دنباله حداقل یکی کم میشه، پس این ارزش اینقد کم میشه تا برسه به صفر، وقتی رسید به صفر هم اول آرایه b هست، می‌تونیم حذفش کنیم و فرض استقرا...

برای قسمت دوم:

این پایان پذیر نیست، مثلا رشته‌ که زیررشته‌ی aab رو داره در نظر بگیر، ادعا می‌کنم هرکاری کنی، یه زیررشته (زیردنباله‌ی متوالی) aab توش می‌مونه، اگر حرکت روی این زیررشته انجام نشه که میمونه، اگه حرکت روی ab اش انجام بشه میشه: abbaab که توی اینم یه aab هست. پس این aab عه همیشه می‌مونه، پس پایان پذیر نیست.

پ.ن: حسش نبود آدم‌وار بنویسم، یه کمی شهودی‌منطقی‌وار نوشتم.