دنباله‌ای از اعداد طبیعی داریم. هر مرحله دو عدد ابتدای دنباله را در نظر می‌گیریم و عدد کوچک‌تر را با یک جمع کرده وبه انتهای دنباله می‌فرستیم. اگر هم دو عدد برابر بودند،‌ یکی را به دلخواه به عنوان عدد کوچک‌تر می‌گیریم و کار را انجام می‌دهیم.

1. ثابت کنید پس از متناهی گام، بالأخره تمام اعداد برابر می‌شوند.
2. فرض کنید از ورودی $n$ (تعداد اعداد دنباله) و سپس خود اعداد دنباله به شما داده شود. الگوریتمی از $O(n)$ ارائه دهید که تعداد مراحل تا رسیدن به وضعیت قسمت آ (برابر شدن تمام اعداد) را پیدا کند.

• سوال قبل