المپدیا

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

ابزار کاربر

ابزار سایت


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

سوال ۲

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

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

پاسخ

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

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


ابزار صفحه