سوال ۱۹

همان سوال قبلی را با این فرض که در ابتدا ۴۰ سکه‌ی ۱ تومانی در اختیار داریم در نظر بگیرید. برای تبدیل این سکه‌ها به یک سکه‌ی ۴۰ تومانی حداقل چند نوع سکه‌ی مختلف تولید می‌شود؟ برای مثال٬ برای تولید یک سکه‌ی ۸ تومانی ۴ نوع سکه‌ی مختلف ۴٬۲٬۱ و ۸ تومانی تولید می‌شود.

  1. ۷
  2. ۸
  3. ۹
  4. ۱۰
  5. ۱۱

پاسخ

گزینه (۱) درست است.

برای تبدیل سکه‌های ۱ تومانی به یک سکه ۴۰ تومانی ٬ در هر یک از بازه‌های $[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$