المپدیا

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

ابزار کاربر

ابزار سایت


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

سوال ۲۸

در یک ردیف ۱۳۸۷ میله‌ي موازی از راست به چپ با شماره‌های ۱ تا ۱۳۸۷ قرار دارند. در ابتدا ۱۳۸۷ مهره در میله‌ی ۱ قرار دارد. در هر حرکت از یک میله‌ی دل‌خواه ۳ مهره برمی‌داریم و یکی را دور انداخته٬ یکی را به همان میله برمی‌گردانیم و سومی را در میله‌ی سمت چپ می‌اندازیم. این کار را تا جایی تکرار می‌کنیم که در هیچ میله‌ای بیش از دو مهره نداشته باشیم. بیش‌ترین شماره‌ی یک میله‌ی حاوی مهره چند است؟

  1. ۸
  2. ۹
  3. ۱۰
  4. ۱۱
  5. ۱۲

پاسخ

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

اولین نکته‌ای که باید به آن دقت کنیم این است که ترتیب انجام عملیات در حالت نهایی تفاوتی ایجاد نمی‌کند (چرا؟). با این فرض از میله‌ی شماره‌ی یک شروع می‌کنیم تا اینکه دیگر نتوانیم حرکتی روی آن انجام دهیم.

بدین ترتیب پس از تعدادی مرحله در میله‌ی دوم $\frac{1387-1}{2}=693$ مهره خواهیم داشت. همین کار را با میله‌ی بعدی انجام می‌دهیم. تعداد مهره‌های میله‌ها همانند زیر خواهند شد:

$693 \rightarrow346 \rightarrow172 \rightarrow85 \rightarrow42 \rightarrow20 \rightarrow9 \rightarrow4 \rightarrow1$

در نتیجه آخرین میله‌ی حاوی مهره، شماره‌ی دهم است.


ابزار صفحه