مجاور را پاک کنید و اختلافشان را بنویسید

از shaazzz
پرش به ناوبری پرش به جستجو

دنباله ای از اعداد را داریم. در هر مرحله می توانیم دو عدد مجاور را پاک کرده و را بنویسیم. ( دقت کنید که قدر مطلق ندارد ) این کار را آن قدر ادامه می دهیم تا به یک عدد برسیم. عدد نهایی چند حالت دارد؟

پاسخ

عدد نهایی حالت دارد.

ابتدا می دانیم که عدد نهایی برابر است که هر کدام از e ها به جز می توانند یک یا منفی یک باشند اما فقط می تواند ۱ باشد و فقط می تواند منفی یک باشد. پس تعداد حالات نهایی کمتر مساوی است.

حال ثابت می کنیم به ازای هر دنباله e که شرایط مذکور را داشته باشد می توانیم طوری عملیات انجام دهیم که عدد نهایی برابر آن شود. این حکم را با استقرا ثابت می کنیم:

حکم به ازای n=2 بدیهی است.

یک دنباله خوب به طول n را در نظر بگیرید.

  • اگر عدد سوم این دنباله مثبت باشد، قرینه دنباله 2 تا n، یک دنباله خوب برای n-1 است. عملیات هایی که آن را به وجود می آورد را انجام می دهیم تا عدد نهایی آن بماند. سپس عدد اول را از آن کم می کنیم. دنباله بدست آمده، همان دنباله مطلوب ماست.
  • در غیر این صورت اگر منفی باشد، در اولین گام عدد اول را از عدد دوم کم می کنیم. الآن دنباله ای به طول n-1 به وجود آمده است که عدد اولش که عدد اول اصلی منهای عدد دوم است باید در نهایت ضریبش مثبت باشد و عدد دومش که عدد سوم اصلی است طبق حالت بندی باید منفی باشد. یعنی دنباله ضرایب دنباله ای خوب است و طبق فرض استقرا می توان طوری عمل کرد که عدد نهایی برابر با عدد آن دنباله شود.