Processing math: 100%

المپدیا

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

ابزار کاربر

ابزار سایت


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

سوال ۲

اعداد 1,2,,n را در نظر بگیرید. دو نفر بازی زیر را انجام می‌دهند: هر کس در نوبت خود عدد 1in را انتخاب می‌کند و سپس i و تمام مضارب آن (که از n بیشتر نیستند) را روی تخته می‌نویسد. هر عدد باید حداکثر k بار نوشته شود. کسی که در نوبت خود نتواند عددی انتخاب کند (برای هر عدد i خود i یا حداقل یکی از مضاربش k بار نوشته شده ‌باشند)، می‌بازد. فرض کنید n=2014 است. به ازای چند مقدار k از بین مجموعه‌ی اعداد {13,21,34,55} نفر اول می‌تواند برنده‌ی بازی باشد؟

  1. ۱
  2. ۲
  3. ۳
  4. ۴
  5. صفر

پاسخ

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

به ازای اعداد فرد نفر اول و به ازای اعداد زوج نفر دوم استراتژی برد دارد. به ازای اعداد زوج: نفر دوم هر عددی که نفر اول انتخاب کرد را دوباره انتخاب می‌کند. در نتیجه همواره نفر دوم می‌تواند عدد انتخاب کند و نفر اول بالاخره خواهد باخت. به ازای اعداد فرد: نفر اول ابتدا عدد 1 را انتخاب می‌کند و در بازی جدید همانند نفر دوم در بازی قبل عمل خواهد کرد.


ابزار صفحه