المپدیا

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

ابزار کاربر

ابزار سایت


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

سوال ۱۰

فرض کنید تعدادی سنگ‌ریزه روی میز است. دو نفر باهم این بازی را ‎(نوبتی)‎ انجام می‌دهند: هرکس در نوبت خودش می‌تواند ‎$d$‎ سنگ‌ریزه از روی میز بردارد، به‌این شرط که تعداد سنگ‌ریزه‌های روی میز بر‎$d$‎ بخش‌پذیر باشد واز ‎$d$‎ بزرگ‌تر باشد. هر کس با حرکتش باعث شود ‎۱‎ سنگ‌ریزه باقی بماند برنده می‌شود. اگر تعداد سنگ‌ریزه‌های اولیه در ‎۹‎ بازی انجام شده به‌ترتیب ۳٬۲،… و ‎۱۰‎ باشد، در چند تا از این بازی‌ها نفر اول می‌تواند برنده شود؟

  1. ۳
  2. ۴
  3. ۵
  4. ۶
  5. ۷

پاسخ

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

کسی که در نوبتش با ۲ سنگ‌ریزه روبه‌رو شود یکی از آن دو را برداشته و برنده می‌شود. بنابراین به ازای $n=2$ نفر اول برنده می‌شود. به ازای $n=3$ نفر اول به نا‌چار ۱ سنگ‌ریزه برداشته و نفر دوم با ۲ سنگ‌ریزه مواجه شده و برنده می‌شود. به‌ازای $n=4$ نفر اول ۱ سنگ‌ریزه برداشته و نفرد دوم با ۳ سنگ‌ریزه مواجه شده و بازنده می‌شود. به ازای $n=5$ نفر اول ۱ سنگ‌ریزه برداشته و نفر دوم با ۴ سنگ‌ریزه مواجه شده و برنده می‌شود. به همین ترتیب معلوم می‌شود که اگر تعداد سنگ‌ریزه‌ها زوج باشد نفر اول و در غیر این صورت نفر دوم برنده خواهد شد.


ابزار صفحه