بر روی یک خط مستقیم دو قورباغه در دو نقطه به فاصلهی ۶۹۵۰ سانتیمتر از هم نشستهاند. در هر «مرحله» هر قورباغه در یکی از دو جهت راست یا چپ و بر روی خط میجهد. میدانیم که طول جهش دو قورباغه در هر مرحله یکسان و برابر توانی از دو است (مثل ۴٬۲٬۱،…) و جهش آنها ممکن است در یک جهت نباشد. حداقل پس از چند مرحله، دو قورباغه در یک نقطهی مشترک فرود میآیند؟
پاسخ
گزینه (۲) درست است.
برای آنکه دو قورباغه به هم برسند لازم است برایند حرکت هر یک از آن دو ۳۴۷۵ سانتیمتر به سمت دیگری باشد. عدد ۳۴۷۵ در مبنای ۲ به شکل $A=110110010011$ میباشد. در هر جهش قورباغه به اندازهی $2^i$ سانتیمتر جهش میکند و این به آن معناست که به عدد $A$ در مبنای ۲ به اندازهی ۰۰…۱۰۰ اضافه و یا آن اندازه از $A$ کم شده است. عمل موقعی به اتمام میرسد که عدد مورد نظر به ۰ برسد. بهترین الگوریتم به شکل زیر میباشد:
$$A-2^0-2^2-2^4+2^7+2^9-2^{12}$$
الگوریتم فوق پس از ۶ مرحله قورباغهها را به هم خواهد رساند.