تعدادی کارت داریم که روی هر یک، یک عدد نوشته شده است. دستگاه کارت برگردان دستگاهی است که اگر دو کارت با عددهای $a$ و $b$ به آن بدهیم، آنها را نابود کرده و یک کارت با عدد $2b$ + $2a$ تولید میکند. (یعنی دو کارت را به یک کارت تبدیل میکند.) ۷ تا کارت با شمارهی ۱ داریم. میخواهیم با چند بار استفاده از دستگاه کارت برگردان بیشترین عدد ممکن را تولید کنیم.این عدد چند است؟
پاسخ
گزینه (۲) درست است.
اگر اعداد $a \leq b \leq c \leq d$ مفروض باشند معلوم است بعد از سه مرحله به یک عدد خواهیم رسید که در بین همه ترکیبهای قابل ساخت٬ ترکیب $8c+8d+4b+2a$ از همه بزرگتر( در عدد حاصل ابتدا دو عدد $d$ و $c$ باهم ترکیب شدهاند و سپس عدد حاصل با $b$ و در نهایت عدد جدید با $a$ ترکیب شده اند).
بنابراین الگوریتم مناست برای ساختن بزرگترین عدد ممکن به شکل زیر میباشد:
$$1,1,1,1,1,1,1 \longrightarrow 1,1,1,1,1,4 \longrightarrow 1,1,1,1,10 \longrightarrow 1,1,1,22 \longrightarrow 1,1,46 \longrightarrow 1,94 \longrightarrow 190$$