المپدیا

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

ابزار کاربر

ابزار سایت


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

سوال ۱۸

در ابتدا یک مهره روی نقطه‌ی ‌$(0, 0)$ صفحه‌ی مختصات قرار داده شده است. در هر مرحله می‌توان یک مهره با مختصات $(x, y)$ به همراه یک عدد طبیعی $n$ انتخاب کرده و پس از برداشتن مهره‌ی مذکور، در هر یک از نقطه‌های $$(x, y+1), (x, y+2), \ldots, (x, y+n-1)$$ و هم‌چنین نقطه‌های $$(x-1, y+n), (x+1, y+n)$$ یک مهره قرار داد. گام‌ها باید طوری انجام شود که در هر لحظه در هر نقطه حداکثر یک مهره باشد. برای مثال در گام نخست با انتخاب تنها مهره‌ی موجود و $n=3$، صفحه به شکل زیر در می‌آید:

با انجام تعدادی مرحله، به کدام اشکال زیر می‌توان رسید؟ (محورهای مختصات کشیده نشده است. شکل در هر جایی از صفحه ایجاد شود، قابل قبول است).

  1. شکل ۲
  2. هیچ یک از شکل‌ها
  3. هر سه شکل
  4. شکل‌های ۱ و ۳
  5. شکل ۱

پاسخ

گزینه‌ی ۵ درست است.

به هر نقطه از صفحه با مختصات $(x, y)$ عدد $2^{y}$ را نسبت می‌دهیم. با انجام هر گام، مجموع اعداد نقاط مهره‌دار تغییری نمی‌کند. در ابتدا این مقدار برابر ۱ است، پس در انتها نیز باید برابر ۱ باشد. در شکل‌های ۲ و ۳ مقدار گفته شده نمی‌تواند به صورت $2^{t}$ باشد، پس رسیدن به این دو شکل امکان ندارد. با اعمال زیر می‌توان شکل ۱ را ساخت:

  1. انتخاب مهره‌ی روی نقطه‌ی $(0, 0)$ با $n=2$
  2. انتخاب مهره‌ی روی نقطه‌ی $(0, 1)$ با $n=2$
  3. انتخاب مهره‌ی روی نقطه‌ی $(0, 2)$ با $n=2$
  4. انتخاب مهره‌ی روی نقطه‌ی $(0, 3)$ با $n=2$

ابزار صفحه