دنباله‌ی $\left< 0,0,0,0,0,0 \right>$ بر روی کاغذ نوشته شده است. در هر مرحله می‌توان یکی از تغییرات زیر را روی دنباله اعمال کرد:
کم‌ترین تعداد مرحله برای رسیدن به دنباله‌ی $\left< 7,11,5,1,3,8 \right>$ چند است؟
راهنمایی
چگونه می‌توان یک عدد دلخواه را با اعمال تعریف شده ساخت؟
راهنمایی
ساختار دودویی اعداد را در نظر بگیرید. در هر مرحله، چه تغییری در ساختار دودویی هر عدد ایجاد می‌شود؟
راهنمایی
ساختار دودویی اعداد را طوری تغییر دهید که تعداد ارقام همه‌ی اعداد در ساختار دودویی یکسانی باشد. سپس در هر مرحله سعی کنید رقم یکسانی از اعداد را مشخص کنید.
راهنمایی
برای اثبات بهینگی روش خود، حداقل تعداد عمل‌های ضرب در دو و حداقل تعداد عمل‌های افزودن یک را محاسبه کنید.
راهنمایی
انجام دادن کدام عمل‌ها کاملا از هم مستقل هستند؟
پاسخ
گزینه‌ی ۲ درست است.
کم‌ترین مرحله برابر است با مجموع تعداد بیت‌های ۱ در نمایش دودویی اعداد دنباله به علاوه‌ی بزرگ‌ترین xای که بزرگ‌ترین عدد دنباله از $2^{x}$ بزرگ‌تر مساوی است. روش ساخت هم این‌گونه است که در مرحله‌ی اول اعداد که بیت x-ام آن‌ها یک است را به‌علاوه‌ی یک می‌کنیم و سپس کل اعداد را در دو ضرب می‌کنیم، در مرحله دوم اعدادی که بیت x-1-ام آن‌ها یک است را به‌علاوه‌ی یک می‌کنیم و سپس کل اعداد را در دو ضرب می‌کنیم. به همین ترتیب این کار را x بار انجام می‌دهیم. در آخر نیز اعدادی که بیت ۰-ام آن‌ها یک است، به‌علاوه‌ی یک می‌شوند. دقت کنید که بعد از آخرین مرحله‌ی اضافه کردن دیگر اعداد را در دو ضرب نمی‌کنیم.