المپدیا

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

ابزار کاربر

ابزار سایت


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

سوال ۱۵

اعداد 1 تا 1395 را دور دایره‌ای نوشته‌ایم. دست‌گاه پاک‌کننده‌ای داریم که ابتدا روی عدد 1 قرار دارد. در هر مرحله با فرض این که دست‌گاه روی $i$ اُمین عدد قرار دارد یکی از دو عملیات زیر را انجام می‌دهیم:

  • عدد $i+1$ اُمی را پاک می‌کنیم و دست‌گاه را روی عدد $i+2$ اُم می‌گذاریم.
  • اعداد $i+1$ اُم و $i+2$ اُم را پاک می‌کنیم و دست‌گاه را روی عدد $i+3$ اُم می‌گذاریم.

آن‌قدر این اعمال را انجام می‌دهیم تا تنها یک عدد دور دایره باقی بماند (توجه کنید اگر دو عدد باقی بماند، باید طبق روش اول یکی از اعداد را پاک کنیم). عدد نهایی که دور دایره باقی می‌ماند، چند مقدار مختلف می‌تواند داشته باشد؟

  1. $1$
  2. $697$
  3. $1393$
  4. $1394$
  5. $1395$

پاسخ

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

به‌جز عدد ۲ که در اولین مرحله پاک می‌شود، بفیه اعداد را می‌توان نگه داشت. کافی است که ۲ یا ۳ گام قبل از آن اعداد را طوری پاک کنیم که در گام بعدی به خود این عدد برسیم. در این صورت تمامی اعداد را می‌توان به عنوان عدد نهایی باقی گذاشت.


ابزار صفحه