المپدیا

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

ابزار کاربر

ابزار سایت


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

سوال ۲۶

می‌خواهیم در عبارت زیر سه تا از ‎۶‎ علامت ضرب را به جمع تبدیل کنیم، به طوری که مقدار ‎$A$‎ مینیمم شود. ‎$$A=5\times6\times4\times3\times2\times7\times8$$‎ حداقل مقدار ‎$A$‎ چه قدر خواهد بود؟ ‎

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

پاسخ

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

مینیمم مقدار $A$ برابر $5\times6+4\times3+2\times7+8$ یعنی ۶۴ است.

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

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


ابزار صفحه