المپدیا

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

ابزار کاربر

ابزار سایت


سوالات المپیاد:مرحله ی اول:دوره ی ۵:سوال ۱۸

سوال ۱۸

۱۱ سنگ‌ریزه در اختیار داریم. دو بازی‌کن با این سنگ‌ریزه‌ها این بازی را انجام می‌دهند:

هر بازیکن در نوبت خودش ۳٬۲٬۱ یا ۴ سنگ‌ریزه بر می‌دارد. وقتی که سنگ‌ریزه‌ها تمام شد. تعداد سنگ‌ریزه‌هایی که هر یک از بازیکنان برداشته‌اند را می‌شماریم. هر بازیکن که به تعداد زوجی سنگ‌‌ریزه برداشته بود٬ برنده است. آیا بازیکن اول می‌تواند طوری بازی‌ کند که حتما برنده شود؟

پاسخ

مراحل بازی به شکل زیر است:

  1. بازیکن اول ۴ سنگ‌ریزه بر می‌دارد.
  2. بازیکن دوم $i$ سنگ‌ریزه برمی‌دارد.
  3. اگر $i=4$ باشد٬ بازیکن اول ۲ سنگ‌ریزه دیگر بر می‌دارد و برنده می‌شود.
  4. اگر $i=3$ باشد٬ بازیکن اول ۴ سنگ‌ریزه دیگر بر می‌دارد و برنده می‌شود.
  5. اگر $i=2$ باشد٬ بازیکن اول ۴ سنگ‌ریزه دیگر بر ‌می‌دارد و برنده می‌شود.
  6. اما اگر $i=1$ باشد٬ بازیکن اول ۱ سنگ‌ریزه بر می‌دارد. باز متناسب با این‌که بازیکن دوم در مرحله‌ی بعد چند سنگ‌ریزه بر دارد٬ حالات زیر پیش می‌آید:
  • اگر بازیکن دوم ۱ سنگ‌ریزه بر دارد٬ بازیکن اول ۳ سنگ‌ریزه بر داشته و برنده می‌شود.
  • اگر بازکن دوم ۲ سنگ‌ریزه بر دارد٬ بازیکن اول ۳ سنگ‌ریزه‌ی باقی‌مانده را بر داشته و برنده می‌شود.
  • اگر بازیکن دوم ۳ سنگ‌ریزه بردارد٬ بازیکن اول ۱ سنگ‌ریزه بر داشته و برنده می‌شود.
  • اگر بازیکن دوم ۴ سنگ‌ریزه بر دارد٬ بازیکن اول تنها سنگ‌ریزه‌ی باقی‌مانده را بر داشته و برنده‌ می‌شود.

ابزار صفحه