همان سوال قبلی را با این فرض که در ابتدا ۴۰ سکهی ۱ تومانی در اختیار داریم در نظر بگیرید. برای تبدیل این سکهها به یک سکهی ۴۰ تومانی حداقل چند نوع سکهی مختلف تولید میشود؟ برای مثال٬ برای تولید یک سکهی ۸ تومانی ۴ نوع سکهی مختلف ۴٬۲٬۱ و ۸ تومانی تولید میشود.
پاسخ
گزینه (۱) درست است.
برای تبدیل سکههای ۱ تومانی به یک سکه ۴۰ تومانی ٬ در هر یک از بازههای [3,4],[5,9],[10,19],[20,39] حداقل یک نوع سکه تولید میشود. تولید سکه ۲ تومانی در اولین مرحله نیز اجتنابناپذیر است٬ بنابراین تولید حداقل ۷ نوع سکه(با احتساب سکههای ۱ و ۴۰ تومانی) مشخص است. با ۷ نوع سکه به یکی از طرق زیر میتوان به جواب رسید:
1⟶2⟶4⟶8⟶16⟶321⟶2⟶4⟶8}⟶40
1⟶2⟶4⟶8⟶161⟶2⟶4}⟶20⟶40
1⟶2⟶4⟶8⟶161⟶2⟶4⟶8}⟶241⟶2⟶4⟶8⟶16}⟶40