====== سوال ۳۱ ======

بر روی یک خط مستقیم دو قورباغه در دو نقطه به فاصله‌ی ‎۶۹۵۰‎ سانتی‌متر از هم نشسته‌اند.
در هر ‎«مرحله»‎ هر  قورباغه در یکی از دو جهت راست یا چپ و بر روی خط می‌جهد. می‌دانیم که طول جهش دو قورباغه در هر مرحله  یکسان و برابر  توانی از دو است (مثل ‎۴٬۲٬۱،...) و  جهش آن‌ها ممکن است در یک جهت نباشد. حداقل پس از چند مرحله، دو قورباغه در یک نقطه‌ی مشترک فرود می‌آیند؟
‎
  - ۵
  - ۶
  - ۷
  - ۸
  - ۱۰‎

<پاسخ>
گزینه (۲) درست است.


برای آن‌که دو قورباغه به هم برسند لازم است برایند حرکت هر یک از آن دو ۳۴۷۵ سانتی‌متر به سمت دیگری باشد. عدد ۳۴۷۵ در مبنای ۲ به شکل $A=110110010011$  می‌باشد. در هر جهش قورباغه به اندازه‌ی $2^i$  سانتی‌متر جهش می‌کند و این به ‌آن معناست که به عدد $A$  در مبنای ۲ به اندازه‌ی ۰۰...۱۰۰ اضافه و یا  آن اندازه از  $A$ کم شده است. عمل موقعی به اتمام می‌رسد که عدد مورد نظر به ۰ برسد. بهترین الگوریتم به شکل زیر می‌باشد:

$$A-2^0-2^2-2^4+2^7+2^9-2^{12}$$

الگوریتم فوق پس از ۶ مرحله قورباغه‌ها را به هم خواهد رساند.



</پاسخ>
  * [[سوال ۳۲|سوال بعد]]
  * [[سوال ۳۰|سوال قبل]]