Processing math: 100%

سوال ۱۹

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

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

پاسخ

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

برای تبدیل سکه‌های ۱ تومانی به یک سکه ۴۰ تومانی ٬ در هر یک از بازه‌های [3,4],[5,9],[10,19],[20,39] حداقل یک نوع سکه تولید می‌شود. تولید سکه ۲ تومانی در اولین مرحله نیز اجتناب‌ناپذیر است٬ بنابراین تولید حداقل ۷ نوع سکه(با احتساب سکه‌های ۱ و ۴۰ تومانی) مشخص است. با ۷ نوع سکه به یکی از طرق زیر می‌توان به جواب رسید:

124816321248}40

124816124}2040

1248161248}24124816}40