همان سوال قبلی را با این فرض که در ابتدا ۴۰ سکهی ۱ تومانی در اختیار داریم در نظر بگیرید. برای تبدیل این سکهها به یک سکهی ۴۰ تومانی حداقل چند نوع سکهی مختلف تولید میشود؟ برای مثال٬ برای تولید یک سکهی ۸ تومانی ۴ نوع سکهی مختلف ۴٬۲٬۱ و ۸ تومانی تولید میشود.
پاسخ
گزینه (۱) درست است.
برای تبدیل سکههای ۱ تومانی به یک سکه ۴۰ تومانی ٬ در هر یک از بازههای $[3,4],[5,9],[10,19],[20,39]$ حداقل یک نوع سکه تولید میشود. تولید سکه ۲ تومانی در اولین مرحله نیز اجتنابناپذیر است٬ بنابراین تولید حداقل ۷ نوع سکه(با احتساب سکههای ۱ و ۴۰ تومانی) مشخص است. با ۷ نوع سکه به یکی از طرق زیر میتوان به جواب رسید:
$\left.\begin{array}{l l}1 \longrightarrow 2 \longrightarrow 4 \longrightarrow8 \longrightarrow 16 \longrightarrow 32 \\ 1 \longrightarrow 2 \longrightarrow 4 \longrightarrow 8 \end{array} \right\} \longrightarrow 40$
$\left. \begin{array}{l l}1 \longrightarrow 2 \longrightarrow 4 \longrightarrow8 \longrightarrow 16 \\1 \longrightarrow 2 \longrightarrow 4 \end{array} \right\} \longrightarrow 20 \longrightarrow 40$
$\left. \begin{array}{l l} {\left. \begin{array}{l l}1 \longrightarrow 2 \longrightarrow 4 \longrightarrow 8 \longrightarrow 16 \\1 \longrightarrow 2 \longrightarrow 4 \longrightarrow 8 \end{array} \right\} \longrightarrow 24} \\1 \longrightarrow 2 \longrightarrow 4 \longrightarrow 8 \longrightarrow 16 \end{array} \right\} \longrightarrow 40$