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