المپدیا

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

ابزار کاربر

ابزار سایت


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

سوال ۲۶

در یک کشور با واحد پول «تورو» دو نوع سکه‌ی پول خرد وجود دارد: ۱ تورویی و $x$ تورویی. مقدار $x$ چقدر باشد تا اگر همه‌ی مبالغ ۱ تورو تا ۱۰۲۴ تورو را به سکه‌های پول خرد تبدیل کنیم٬ مجموع تعداد سکه‌های حاصل کمینه شود؟ فرض می‌کنیم که در هر خرد کردن کم‌ترین تعداد سکه را به دست می‌آوریم.

  1. ۲
  2. ۱۰
  3. ۳۲
  4. ۱۲۸
  5. ۵۱۲

پاسخ

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

فرض می‌کنیم $x$ توانی از ۲ به صورت $x=2^t$ باشد در این صورت اعداد از ۱ تا ۱۰۲۳ را به $\frac{1024}{x}$ دسته $x$ عضوی تقسیم می‌کنیم(دسته اول ($x-1$) عضوی است). در هر دسته به تعداد $1+2+3+...+(x-1)$ یعنی $\frac{x(x-1)}{2}$ سکه«۱» تورویی وجود دارد که تعداد کل آن‌ها $\frac{1024}{2}\times \frac{x(x-1)}{2}$ می‌شود. هر یک از اعضای دسته دوم شامل ۱ سکه $x$ تورویی٬ هر یک از اعضا دسته سوم شامل ۲ سکه $x$ تورویی٬…و بالاخره هر یک از اعضای دسته $\frac{1024}{x}$ شامل $(\frac{1024}{x}-1)$ سکه $x$ تورویی می‌باشند که تعداد کل آن‌ها $(1+2+3+...+(\frac{1024}{x}-1))$ یا $512\frac{1024}{x}-1$ می‌باشد که با احتساب $\frac{1024}{x}$ سکه $x$ تورویی مربوط به خود ۱۰۲۴ ریال٬ تعداد کل سکه‌ها به شکل زیر به‌دست می‌آید:

$m=\frac{1024}{x} \times \frac{x(x-1)}{2} + 512(\frac{1024}{x}-1) + \frac{1024}{x}=512(x-2+ \frac{1026}{x})$ حاصل عبارت قبل به ازای ۱۲۸٬۳۲٬۲ و ۵۱۲ برای $x$ برابر ۶۸۶۱۶٬۳۱۷۷۶٬۲۶۲۶۵۶ و ۲۶۲۱۴۶ می‌باشد که به ازای ۳۲ برای $x$ مینیمم است.

اگر $x$ برابر ۱۰ باشد٬ آن‌گاه تعداد سکه‌های ۱ تورویی برابر $102\times(1+2+3+...+9)+(1+2+3+4)$ یعنی ۴۶۰۰ می‌شود٬ تعداد سکه‌های ۱۰ تورویی نیز برابر $10\times(1+2+3...+101)+5\times102$ یعنی ۵۲۰۲۰ می‌باشد که در کل٬ تعداد همه سکه‌ها برابر ۵۶۶۲۰ می‌شود.


ابزار صفحه