سوال ۳

سعی کنید پایان‌پذیری بیابید که در هر عملیات افزایش یابد.

می‌توان دوران دنباله را به صورت انتخاب یک بخش آخر دنباله و انتقال آن به اول دنباله در نظر گرفت.

چهار متغیر $L_0$, $L_1$, $R_0$, $R_1$ را به ترتیب تعداد صفر‌های بخش چپ، تعداد یک‌های بخش چپ، تعداد صفر‌های بخش راست و تعداد یک‌های بخش راست پیش از عملیات در نظر گیرید. (راست انتهای دنباله و چپ ابتدای دنباله است.) در چه صورتی عمل دوران انجام می‌شود؟

عمل دوران زمانی انجام می‌شود که $$L_1 \times R_0 > R_1 \times L_0$$

متغیر پایان‌پذیر $S$ را برابر مجموع شماره‌ی ستون ۱ ها در نظر بگیرید.

متغیر $S$ پس از هر عمل افزایش می‌یابد. تغییرات آن را بر اساس چهار متغیر معرفی شده در راهنمایی‌های پیشین بنویسید.

مقدار تغییر $S$ پس از یک گام برابر است با $$L_1 \times (R_0 + R_1) - R_1 \times (L_0 + L_1)$$

بر حسب نامعادله‌ای که پیشتر در راهنمایی‌ها دیدیم، مقدار تغییرات $S$ همواره مثبت خواهد بود.