المپدیا

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

ابزار کاربر

ابزار سایت


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

سوال ۱۲

اعداد {$۲^i| ۰ \le i \le ۹$} روی تخت نوشته شده‌اند. مولین و مرلون بازی زیر را انجام می‌دهند: در هر مرحله بازیکنی که نوبت اوست٬ دو عدد $x$ و $y$ را انتخاب می‌کند و بعد از پاک کردن آن‌ها عدد $\lceil \frac {x+y}2 \rceil$ یا $\lfloor \frac {x+y}2 \rfloor$ را روی تخته می‌نویسد و این روند ادامه می‌یابد تا فقط یک عدد باقی بماند. هدف مولین بیشینه کردن این عدد و هدف مولون کمینه کردن آن است. اگر هر دو بازیکن بهترین بازی خود را انجام دهند و مولین شروع‌کننده‌ی بازی باشد و عدد نهایی برابر $p$ باشد٬ باقی‌مانده‌ی $p$ بر ۵ برابر چند است؟

  1. ۲
  2. ۰
  3. ۱
  4. ۳
  5. ۴

پاسخ

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

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


ابزار صفحه