سوال ۱۳

فرض کنید $\langle a_1,a_2,...,a_{14}\rangle$ رشته‌ای از ارقام ۰ و ۱ باشد. به تعدادی رقم متوالی و برابر، یک زنجیره می‌گوییم. زنجیرەای که بخشی از یک زنجیرەی بزرگتر نباشد، بلوک نامیده می‌شود. برای مثال، رشته‌ی زیر از ۴ بلوک ساخته شده است:

$$\langle 0,0,0,1,1,0,0,1,1,1,1,1,1,1 \rangle$$

الگوریتم زیر را اجرا می‌کنیم:

برای مثال، رشته‌ی بالا پس از یک مرحله به رشته‌ی $\langle 0,0,0,0,0,1,1,1,1,1,1,1 \rangle$ تبدیل می‌شود. در میان تمام حالات ممکن برای رشته‌ی ۱۴ رقمی آغازین، کمینه‌ی تعداد ارقام رشته‌ی نهایی (پس از اجرای کامل الگوریتم مذکور) چیست؟

  1. ۲
  2. ۴
  3. ۶
  4. ۵
  5. ۳

راهنمایی

حداقل طول رشته اولیه را با توجه به طول رشته نهایی محاسبه کنید.

راهنمایی

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