عدد a را 0 و عدد b را $( 1010101...10101 )$ در مبنای 2 می گذاریم که از 100 تا 1 و 100 تا 0 تشکیل شده.

در اینصورت برای رفتن از a به b لااقل 100 حرکت لازم است. درست راهش رو یادم نمیاد ولی استقرا بود.

تعداد بلوک های یک در نمایش باینری فاصله A با هر عمل جمع یا تفریق یک توان دو حداکثر یکی زیاد میشه پس برای ساخت 101010..10 یعنی 100 بلوک یک .پس 100 حرکت لازمه و اینکه ثابت کنید باهر حرکت بلوک های یک یکی زیاد میشه حداکثر حالت بندی آسونه.

جواب a=0 و b= رشته ای متناوب متشکل از 100 1 و صد 0 در مبنای 2. ابتدا سوال رو به مبنای 2 می بریم و به ببرسی حالت های جمع وتفریق در مبنای 2 می پردازیم. به طور کلی در مبنای 2 4 حالت برای جمع و تفریق وجود دارد:

1. جمع یک رقم 1 با رقم 0: در این حالت صفر جای خود را به 1 می دهد.
2. جمع دو رقم 1: در این حالت رقم مرتبه 0 می شود و رقم قبلی به 1 تبدیل می شو مانند مثال $$ 1000010+10=1000100$$
3. تفریق 2 رقم 1: در این حالت رقم 1 به 0 تبدیل می شود
4. تفریق 2 رقم 0 و 1: در این حالت در جایگاه رقم صفر تولید 1 شود، تا رسیدن به نزدیک ترین رقم 1 سمت راست همه ی 1 ها به 0 تبدیل شوند و خود آن رقم به 0 تبدیل شود مانند مثال: $$10010000 - 1 = 10001111$$

حالا به سراغ پاسخ دادن به سوال می رویم:

از طریق استقرا اثبات می کنیم اگر دنباله ای تناوبی از 0 و 1 در مبنای 2 داشته باشیم و برای رسیدن به آن فقط بتوانیم از جمع و تفریق کردن توان های دو استفاده کنیم حداقل به تعداد یک های دنباله به جمع و تفریق نیاز داریم:( طبق فرض مسءله باید توان ها را به یک عدد پایه ای اضافه کرد)

پایه: برای رسیدن به عدد 1 به یک عمل جمع نیازمندیم

گام فرض کنید حکم به ازای یک دنباله 2n رقمی درست است اثبات می کنیم به ازای که دنباله ی 2n+2 رقمی نیز درست است:

بدیهیس به آخر دنباله ی قبلی یک 10 اضافه شده که طبق توضیحات اولیه سریع ترین کار برای رسیدن به آن درست کردن دنباله ی قبلی و اضافه کردن 2 به توان 2n+2 به آن است زیرا در هر حرکت حداکثر می توان یک 10 به دنباله اضفه کرد.

بدون استفاده از استقرا هم می توان با استفاده از اصل ناوردایی به سوال پاسخ داد که بسیار ساده تر است.

طبق توضیحات اولیه در هر جمع یا تفریق حداکثر می توان یک دنباله 10 درون دنباله ی اصلی درست کرد در این صورت اگر جمله ی آخر یک تناوب شامل صد 1 و صد 0 باشد به حداقل 100 حرکت برای ایجاد عدد از عدد صفر نیازمندیم.