Processing math: 100%

المپدیا

دانش‌نامه‌ی المپیاد کامپیوتر ایران

ابزار کاربر

ابزار سایت


سوالات المپیاد:مرحله ی اول:دوره ی ۸:سوال ۲۶

سوال ۲۶

می‌خواهیم در عبارت زیر سه تا از ‎۶‎ علامت ضرب را به جمع تبدیل کنیم، به طوری که مقدار ‎A‎ مینیمم شود. ‎A=5×6×4×3×2×7×8‎ حداقل مقدار ‎A‎ چه قدر خواهد بود؟ ‎

  1. ۶۰
  2. ۸۴
  3. ۷۹
  4. ۶۹
  5. ۶۴

پاسخ

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

مینیمم مقدار A برابر 5×6+4×3+2×7+8 یعنی ۶۴ است.

ابتدا فرض کنید دو عدد انتهایی یعنی ۷ و ۸ در هم ضرب شوند تا ۵۶ حاصل شود. در این صورت حتی اگر اعداد قبلی را با ۵۶ جمع بزنیم حاصل بیش‌تر از ۶۴ خواهد بود. پس در جواب بهینه بین ۷ و ۸ از علامت جمع استفاده می‌شود.

حال نشان می‌دهیم در بین اعداد قبلی هیچ ۳ تایی متوالی نباید در هم ضرب شوند. دفت کنید که به غیر از ۴*۳*۲ و ۳*۲*۷ حاصل ضرب هر ۳ عدد متوالی از ۶۴ بزرگ‌تر است. حال اگر بین ۷ و ۲ و ۳ فقط از ضرب استفاده شود چون حاصل‌ضرب آن‌ها ۴۲ است حتی با جمع کردن بقیه‌ی اعداد با ۴۲، به ۴۲+۶+۴+۵+۸ یعنی ۶۵ می‌رسیم. هم‌چنین اگر بین ۷ و ۲ و ۳ فقط از ضرب استفاده شود چون می دانیم قبل از ۸ هم از علامت جمع استفاده شده، پس مجموع به صورت یکتا برابر ۵*۶+۴*۳*۲+۷+۸ می‌شود که از ۶۴ بیش‌تر است. پس هیچ ۳ عدد متوالی در جواب بهینه در هم‌ ضرب نشده‌اند.


ابزار صفحه